AVl树
发布日期:2021-09-19 03:18:22
浏览次数:1
分类:技术文章
本文共 5297 字,大约阅读时间需要 17 分钟。
AVL树是高度平衡的二叉搜索树
特征:
1.左右子数的高度差不超过1(因为可能有4个节点)
2.树中每个左子树,右子树都是AVL树
3.每个节点都有一个平衡因子,(每个节点的平衡因子等于右子树的高度减去左子树的高度),每个节点的平衡因子为1/0/-1
效率:
AVL树的高度为N,其高度可以保持在log2^N ,插入,删除,查找等时间复杂度也都是log2^N
因为AVL是高度平衡的二叉搜索树,插入以后就可能会导致它不平衡,所以要进行旋转
1左旋:
void RotateL(Node* parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; parent->_right = SubRL; if (SubRL) { SubRL->_parent = parent; } SubR->_left = parent; Node* ppNode = parent->_parent; parent->_parent = SubR; if (ppNode == NULL) { _root = SubR; SubR->_parent = NULL; } else { if (ppNode->_left == parent) { ppNode->_left = SubR; } else { ppNode->_right = SubR; } SubR->_parent = ppNode; } SubR->_bf = parent->_bf =0 }
2.右旋
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = subL; if (ppNode == NULL) { _root = subL; subL->_parent = NULL: } else { if (ppNode->_right = _root) { ppNode->_right = subL; } else ppNode->_left = subL; subL->_parent = ppNode; } subL->_bf = parent->_bf = 0; }
3.左右双旋
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = parent->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 1) { subL->_bf = -1; parent->_bf = 0 } if (bf == -1) { subL->_bf = 0; parent->_bf = 1; } else { subL->_bf = parent->_bf = 0; } subLR->bf = 0; }
4.右左双旋
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subR->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 1) { parent->_bf = -1; subRL->_bf = 0; } if (bf == -1) { parent->_bf = 0; subRL->_bf = 1; } else { subR->_bf = parent->_bf = 0; } subRL->_bf = 0; }
整体实现:
#includeusing namespace std;template struct AVLTreeNode{ K _key; V _value; AVLTreeNode * _left; AVLTreeNode * _right; AVLTreeNode * _parent; int _bf; AVLTreeNode(const K& k, const V& v) : _key(key) , _value(value) , _left(NULL) , _right(NULL) , _parent(NULL) , _bf(0) {}};template class AVLTree{ typedef AVLTreeNode * Node;public: AVLTree()//构造函数 :_root(NULL) {}
bool Insert(const K& key, const V& value)//插入 { if (_root == NULL) { _root = new Node(key, value); return true; } Node* cur = _root; Node* parent = NULL; while (cur) //二叉搜索树的特性,若key大于cur->_key则为右,小于则为左 { if (cur->_key < key) { parent = cur; cur = cur->_right; } if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; }
//插入后更新bf while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++ } if (parent->_bf == 0)//若bf=0,则平衡
break; if (parent->_bf == 1 || parent->_bf == -1)//等于1的话继续向上调整 { cur = parent; cur=parent->_parent; } else { if (parent->_bf == 2) { if (cur->_bf == 1) { RotateL(parent);//左旋 } else //cur->_bf==-1 { RotateRL(parent);//右左双旋 } } else //parent->_bf = -2 { if (cur->_bf == -1) { RotateR(parent);//右旋 } else { RotateLR(parent);//左右双旋 } } break; } } return true; } void RotateL(Node* parent)//左 { Node* SubR = parent->_right; Node* SubRL = SubR->_left; parent->_right = SubRL; if (SubRL) { SubRL->_parent = parent; } SubR->_left = parent; Node* ppNode = parent->_parent; parent->_parent = SubR; if (ppNode == NULL) { _root = SubR; SubR->_parent = NULL; } else { if (ppNode->_left == parent) { ppNode->_left = SubR; } else { ppNode->_right = SubR; } SubR->_parent = ppNode; } SubR->_bf = parent->_bf =0 } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = subL; if (ppNode == NULL) { _root = subL; subL->_parent = NULL: } else { if (ppNode->_right = _root) { ppNode->_right = subL; } else ppNode->_left = subL; subL->_parent = ppNode; } subL->_bf = parent->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = parent->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 1) { subL->_bf = -1; parent->_bf = 0 } if (bf == -1) { subL->_bf = 0; parent->_bf = 1; } else { subL->_bf = parent->_bf = 0; } subLR->bf = 0; } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subR->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 1) { parent->_bf = -1; subRL->_bf = 0; } if (bf == -1) { parent->_bf = 0; subRL->_bf = 1; } else { subR->_bf = parent->_bf = 0; } subRL->_bf = 0; }protected: void _Inorder(Node* root) { if (root = NULL) { return; } _Inorder(root->_left); cout << root->_key << ; _Inorder(root->right); }private: Node* _root;};
转载地址:https://blog.csdn.net/audience_fzn/article/details/78432936 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年03月24日 15时48分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
chmod 赋权所有_chmod 权限 命令详细用法
2019-04-21
html代码翻译_[译]您知道 HTML 的键盘标签吗?
2019-04-21
html抽奖代码_JavaScript高手之路:封装抽奖效果
2019-04-21
的流程图做完后如何保存_2019超火的半永久眉是哪款?做完后我们如何护理?...
2019-04-21
去除logo 高德地图api_深圳品牌logo升级如何保持原型的同时更具创新?
2019-04-21
二重积分转换成极坐标_二重积分转换极坐标r的范围如何确定?
2019-04-21
python中倒背如流_八字基础知识--倒背如流篇
2019-04-21
以太坊地址和公钥_以太坊地址是什么
2019-04-21
npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题
2019-04-21
vs格式化json 不生效_vs code 格式化 json 配置
2019-04-21
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析
2019-04-21
hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了!
2019-04-21
abp框架 mysql_ABP框架使用Mysql数据库
2019-04-21
mysql树形递归删除_使用递归删除树形结构的所有子节点(java和mysql实现)
2019-04-21
linux mysql 不能连接远程_linux mysql 远程连接
2019-04-21
install python_Install python on AIX 7
2019-04-21