办公室装修设计 公司,优化搜狐的培训,做手表网站用什么源码比较好,贵州省城乡与住房建设部网站文章目录 一、基本概念1.发展背景2.性质 二、实现原理①插入操作1.平衡因子1.1平衡因子的更新1.1.1树的高度变化1.1.2树的高度不变 2. 旋转2.1左旋2.2右旋2.3右左双旋2.4 左右双旋 ②验证1.求二叉树高度2. 判断是否为AVL树 源码总结 一、基本概念
1.发展背景 普通的二叉搜索树… 文章目录 一、基本概念1.发展背景2.性质 二、实现原理①插入操作1.平衡因子1.1平衡因子的更新1.1.1树的高度变化1.1.2树的高度不变 2. 旋转2.1左旋2.2右旋2.3右左双旋2.4 左右双旋 ②验证1.求二叉树高度2. 判断是否为AVL树 源码总结 一、基本概念
1.发展背景 普通的二叉搜索树在极端情况下会退化成类似链表的形状从而使查找的效率降低至O(N)。 在此基础上苏联与以色列数学家Adelson-Velskii 与 苏联数学家Landis发明出了 AVL树或者说平衡二叉搜索树。 注第一张——Adelson-Velskii1922-2014 第二张——Landis1921——1997 2.性质
左右子树的高度差的绝对值不大于1每个子树都是AVL树。
说明这样做的目的就是为了严格控制平衡以便于提高查找效率但是控制高度差一直为0是不可能的至于为什么不能控制成0假设只有两个结点必然存在1的高度差。
二、实现原理
①插入操作
1.平衡因子
英文名balance factor
目的保证左右子树的高度差的绝对值不大于1大多数的实现方式存放的是右子树与左子树的高度差
1.1平衡因子的更新
1.1.1树的高度变化
① 左边新增结点
② 右边新增结点 总结
左边新增根节点的平衡因子减1右边新增根节点的平衡因子加1平衡因子从0变为1或者-1
继续分析 两种情况树的高度增加1也就是平衡因子从0变为1或者-1既然高度变化了可能会导致上面的树不平衡。 如
此时我们需要向上更新平衡因子再根据右边高度变化与左边高度变化决定根的平衡因子加1还是减1。
推论由于可能会向上更新平衡因子那么AVL树是三叉链的结构。
如图
1.1.2树的高度不变
① 左边新增结点 ② 右边新增结点 同理
左边新增根节点的平衡因子减1右边新增根节点的平衡因子加1平衡因子由1或者-1变为0
继续分析这里的根节点的所在树的高度即——左右子树高度的最大值 1根节点的高度
左右子树的高度的最大值不变即这颗树高度不变即不用往上继续更新且达到平衡。
2. 旋转 说明旋转就是让不平衡的树再次平衡的手段。 条件平衡因子为2或者-2即高度差的绝对值为2。 补充若平衡因子大于等于3说明当前树就不是AVL树需要检验之前的代码。
但是我们又得对情况进行分类讨论因为不同情况让树再次平衡的旋转方式不同。
2.1左旋
说明也就是右边高度高需要旋转来降低右边的高度进而达到平衡。
一步一步分析先来个最简单的 此时旋转过后平衡因子全变为0且当前树达到平衡。注意此时3结点的左结点为空(细节)
再举一个例子 此时旋转过后平衡因子1和3的平衡因子变为0且当前树达到平衡此时我们是不用管其它子树的因为子树必然是AVL树要不然更不到根节点就停止了。
最后来一个稍微复杂的例子 此时旋转过后平衡因子-5和0的平衡因子变为0且当前树达到平衡。
这是具体的图便于辅助理解然后我们再画出所有情况的抽象图
总结
只能在c部分上插入结点才可能会引发根节点左单旋,也就是说parent的右边为cur且新增结点在cur的右边。旋转过后cur与parent的平衡因子变为0。
细节
b的父节点连接parent时需要判断b部分是否为空。parent的父节点连接cur时需要保存一下parent的父节点。根据parent的父节点判断是否需要修改根节点若为空则修改若不为空则将cur链接到parent的父节点同时更新parent父节点的指向。
实现代码 void RotateL(Node* parent){//画图分析//操作的结点有cur,cur_left,ppnodeNode* cur parent-_right;Node* cur_left cur-_left;//将parent的右节点改为cur_leftparent-_right cur_left;//改变cur_left父节点的转向//cur_left可能为空if (cur_left ! nullptr){cur_left-_parent parent;}//将parent链接在cur的左边//为了更新cur的parent需要保存parent的父节点Node* ppnode parent-_parent;cur-_left parent;parent-_parent cur;//ppnode可能为空if (ppnode nullptr){//需要修改根节点_root cur;cur-_parent nullptr;}else{//改变ppnode的指向if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}//更新平衡因子cur-_bf parent-_bf 0;}2.2右旋
说明也就是左边高度高需要旋转来降低右边的高度进而达到平衡。
跟左旋的分析方式一样。
先来个简单的感受一下 此时旋转过后平衡因子parent和cur的平衡因子变为0且当前树达到平衡。
再举一个例子 最后来一个稍微复杂的例子
画出所有情况的抽象图 总结
只能在a部分上插入结点才可能会引发根节点右单旋,也就是说parent与cur与高度变化的c树的根节点在同一个方向且在parent的左旋转过后cur与parent的平衡因子变为0。 细节——同左旋
b的父节点连接parent时需要判断b部分是否为空。parent的父节点连接cur时需要保存一下parent的父节点。根据parent的父节点判断是否需要修改根节点若为空则修改若不为空则将cur链接到parent的父节点同时更新parent父节点的指向。
实现代码 void RotateR(Node* parent){//操作的结点Node* cur parent-_left;Node* cur_right cur-_right;//第一步将cur_right链接到parent的leftparent-_left cur_right;//更改cur_right的父节点//注意cur_right可能为空if (cur_right ! nullptr){cur_right-_parent parent;}//第二步将parent链接到cur的右结点。//先保存一下parent的父节点Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;//ppnode为空说明需要修改根节点if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}//更新平衡因子cur-_bf parent-_bf 0;}2.3右左双旋
可以简单理解为需要进行处理的左旋。
说明单旋无法解决问题原因是发生了拐弯需要用右旋讲折线变为直线再进行左旋。
因为情况有点多我们就来个简单的直接化抽象图看结论比较容易理解。
先来个简单的 先右旋之后折线变成了直线变成了左旋的形状再进行左旋最后的cur与cur_left与parent的平衡因子变成了0最终cur_left变成了根节点。
再化抽象图
初始状态 还是一样不过得分两种情况进行讨论
新增结点在c树上会导致parent的平衡因子变为-1cur的平衡因子变为0。新增结点在b树上会导致parent的平衡因子变为0cur的平衡因子变为1不管新增结点在谁上cur_left的平衡因子都为0。 看图分析其实不看新增结点在谁身上两种最终的旋转的结果是一样的那我们其实只需先不看新增结点再画图根据最终的结果再把新增结点添上其实会更加直观。 总结
新增结点在c树上会导致parent的平衡因子变为-1cur的平衡因子变为0。新增结点在b树上会导致parent的平衡因子变为0cur的平衡因子变为1。cur_left为新增结点parent与cur的结点全为0。
实现代码 void RotateRL(Node* parent){Node* cur parent-_right;Node* cur_left cur-_left;//CL——CurLeftint CL_bf cur_left-_bf;RotateR(cur);RotateL(parent);//更新平衡因子if (CL_bf 0){cur-_bf parent-_bf cur_left-_bf 0;//虽然没必要但是起到了解耦的作用。}else if (CL_bf 1){parent-_bf -1;cur-_bf cur_left-_bf 0;}else if(CL_bf -1){cur-_bf 1;parent-_bf cur_left-_bf 0;}else{cout __LINE__ : endl;perror(平衡因子有误);exit(-1);}}2.4 左右双旋
可以理解为需要进行处理的右旋。
说明单旋无法解决问题原因是发生了拐弯需要用左旋讲折线变为直线再进行右旋。 分析方法跟右左双旋一样。 先来个简单的 先左旋之后折线变成了直线变成了右旋的形状再进行右旋最后的cur与cur_left与parent的平衡因子变成了0最终cur_left变成了根节点。
再来个抽象的 还是一样不过得分两种情况进行讨论
新增结点在c树上会导致cur的平衡因子变为-1parent的平衡因子变为0。新增结点在b树上会导致cur的平衡因子变为0parent的平衡因子变为1不管新增结点在谁上cur_right的平衡因子都为0。 总结
cur_right平衡因子为1说明新增结点在b树上会导致cur的平衡因子变为0parent的平衡因子变为1。cur_right的平衡因子为-1新增结点在c树上会导致cur的平衡因子变为-1parent的平衡因子变为0。cur_right的平衡因子为0cur与parent的平衡因子都变为0。不管新增结点在谁上cur_right的平衡因子都为0。
代码实现 void RotateLR(Node* parent){Node* cur parent-_left;Node* cur_right cur-_right;int CR_bf cur_right-_bf;RotateL(cur);RotateR(parent);if (CR_bf 0){parent-_bf cur-_bf cur_right-_bf 0;}else if(CR_bf 1){cur-_bf -1;parent-_bf cur_right-_bf 0;}else if (CR_bf -1){parent-_bf 1;cur-_bf cur_right-_bf 0;}else{cout __LINE__ : endl;perror(平衡因子有误);exit(-1);}} ②验证
说明
根据定义验证每颗子树的高度差需要判断当前的右子树的高度差是否等于平衡因子 直接根据平衡因子进行判断有点监守自盗的感觉你能保证自己更新的平衡因子就是正确的么我都不敢保证。 1.求二叉树高度
后序遍历 size_t Height(Node* root){if (root nullptr){return 0;}int LHeight Height(root-_left);int RHeight Height(root-_right);return max(LHeight, RHeight) 1;}2. 判断是否为AVL树 bool _IsAVLTree(Node* root){if (root nullptr){return true;}int RHeight Height(root-_right);int LHeight Height(root-_left);if (abs(RHeight - LHeight) 1 || root-_bf ! RHeight - LHeight){return false;}return _IsAVLTree(root-_left) _IsAVLTree(root-_right);}优化一下 bool IsAVLTree(){bool is_AVL true;_IsAVLTree(_root, is_AVL);return is_AVL;}int _IsAVLTree(Node* root,bool is_AVL){if (root nullptr){return 0;}int RHeight _IsAVLTree(root-_right, is_AVL);int LHeight _IsAVLTree(root-_left, is_AVL);if (abs(RHeight - LHeight) 1 || root-_bf ! RHeight - LHeight){is_AVL false;}return max(RHeight, LHeight) 1;}源码
#includeiostream
#includeassert.h
using namespace std;
namespace MY_STL
{templateclass Key,class Valstruct AVLTreeNode{typedef AVLTreeNodeKey, Val Node;AVLTreeNode(const pairKey,Val key pairKey,Val()):_key(key.first),_val(key.second),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}Key _key;Val _val;//三叉链的结构Node* _left;Node* _right;Node* _parent;int _bf;};templateclass Key, class Valclass AVLTree{typedef AVLTreeNodeKey, Val Node;public:AVLTree(){}bool insert(const pairKey,Val val){//第一步插入操作//如果根节点为空if (_root nullptr){_root new Node(val);return true;}else{Node* cur _root,*parent _root;while (cur){if (cur-_key val.first){parent cur;cur cur-_left;}else if(cur-_key val.first){parent cur;cur cur-_right;}else{return false;}}cur new Node(val);if (parent-_key val.first){parent-_left cur;}else{parent-_right cur;}//更新新增结点的_parentcur-_parent parent;//第二步更新平衡因子//平衡因子//1. 定义为右子树的高度减去左子树的高度//2. 合法范围为{-1,0,1}//3. 新增结点在左父节点的平衡因子减1//4. 新增结点在右父节点的平衡因子加1//5. 当父节点的平衡因子变为0——由-1变0或者1变0时此时AVL树的高度不变//6. 当父节点的平衡因子变为1或者-1AVL子树的高度变化继续向上变化。//7. 当父节点的平衡因子变为2或者-2时此时需要旋转进行平衡//8. 当父节点为根节点时此时需要结束循环。while (cur ! _root){//更新平衡因子if (parent-_left cur){//左减1(parent-_bf)--;}else{//右加1(parent-_bf);}//判断平衡因子if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent cur-_parent;}else if (parent-_bf 2 || parent-_bf -2){//对旋转进行分类讨论//if (parent-_bf 2 cur-_bf 1)//{// //左单旋// RotateL(parent);//}//else if (parent-_bf -2 cur-_bf -1)//{// //右单旋// RotateR(parent);//}//else if (parent-_bf 2 cur-_bf -1)//{// RotateRL(parent);//}//else if (parent-_bf -2 cur-_bf 1)//{// RotateLR(parent);//}if (parent-_bf 2){//左单旋if (cur-_bf 1){RotateL(parent);}else{RotateRL(parent);}}else{//右单旋if (cur-_bf -1){RotateR(parent);}else{RotateLR(parent);}}//旋转完成树达到平衡break;}}return true;}}//根据定义进行判断bool IsAVLTree(){bool is_AVL true;_IsAVLTree(_root, is_AVL);return is_AVL;//return _IsAVLTree(_root);}void Print(){_InOrder(_root);cout endl;}//根据平衡因子进行判断//bool IsAVLTree()//{// return _IsAVLTree(_root);//}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}//bool _IsAVLTree(Node* root)//{// if (root nullptr)// return true;// if (root-_bf 2 || root-_bf -2)// {// return false;// }// else// {// return _IsAVLTree(root-_left) _IsAVLTree(root-_right);// }//}//bool IsAVLTree()//{// bool is_AVL true;// _IsAVLTree(_root, is_AVL);// return is_AVL;//}size_t Height(Node* root){if (root nullptr){return 0;}int LHeight Height(root-_left);int RHeight Height(root-_right);return max(LHeight, RHeight) 1;}int _IsAVLTree(Node* root,bool is_AVL){if (root nullptr){return 0;}int RHeight _IsAVLTree(root-_right, is_AVL);int LHeight _IsAVLTree(root-_left, is_AVL);if (abs(RHeight - LHeight) 1 || root-_bf ! RHeight - LHeight){is_AVL false;}return max(RHeight, LHeight) 1;}bool _IsAVLTree(Node* root){if (root nullptr){return true;}int RHeight Height(root-_right);int LHeight Height(root-_left);if (abs(RHeight - LHeight) 1 || root-_bf ! RHeight - LHeight){return false;}return _IsAVLTree(root-_left) _IsAVLTree(root-_right);}void RotateLR(Node* parent){Node* cur parent-_left;Node* cur_right cur-_right;int CR_bf cur_right-_bf;RotateL(cur);RotateR(parent);if (CR_bf 0){parent-_bf cur-_bf cur_right-_bf 0;}else if(CR_bf 1){cur-_bf -1;parent-_bf cur_right-_bf 0;}else if (CR_bf -1){parent-_bf 1;cur-_bf cur_right-_bf 0;}else{cout __LINE__ : endl;perror(平衡因子有误);exit(-1);}}void RotateRL(Node* parent){Node* cur parent-_right;Node* cur_left cur-_left;//CL——CurLeftint CL_bf cur_left-_bf;RotateR(cur);RotateL(parent);if (CL_bf 0){cur-_bf parent-_bf cur_left-_bf 0;}else if (CL_bf 1){parent-_bf -1;cur-_bf cur_left-_bf 0;}else if(CL_bf -1){cur-_bf 1;parent-_bf cur_left-_bf 0;}else{cout __LINE__ : endl;perror(平衡因子有误);exit(-1);}}void RotateL(Node* parent){//画图分析//操作的结点有cur,cur_left,ppnodeNode* cur parent-_right;Node* cur_left cur-_left;//将parent的右节点改为cur_leftparent-_right cur_left;//改变cur_left父节点的转向//cur_left可能为空if (cur_left ! nullptr){cur_left-_parent parent;}//将parent链接在cur的左边//为了更新cur的parent需要保存parent的父节点Node* ppnode parent-_parent;cur-_left parent;parent-_parent cur;//ppnode可能为空if (ppnode nullptr){//需要修改根节点_root cur;cur-_parent nullptr;}else{//改变ppnode的指向if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}//更新平衡因子cur-_bf parent-_bf 0;}void RotateR(Node* parent){//操作的结点Node* cur parent-_left;Node* cur_right cur-_right;//第一步将cur_right链接到parent的leftparent-_left cur_right;//更改cur_right的父节点//注意cur_right可能为空if (cur_right ! nullptr){cur_right-_parent parent;}//第二步将parent链接到cur的右结点。//先保存一下parent的父节点Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;//ppnode为空说明需要修改根节点if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}//更新平衡因子cur-_bf parent-_bf 0;}Node* _root nullptr;};
};
总结 AVL树还有删除操作等博主有空再补充对于AVL树一般来说只需要弄懂一种单旋一种双旋再加一些细写处理代码是不难的难就难在了分类讨论画图上。今天的分享就到这里了如果感觉有所帮助不妨点个赞鼓励一下吧
