1. AVL的概念AVL是一颗空树或者具备下列性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树通过控制高度差去控制平衡。AVL树实现这里我们引入一个平衡因子的概念每个结点都有⼀个平衡因子任何结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0/1/-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进性观察和控制树是否平衡。AVL树整体结点数量和分布和完全二叉树类似高度可以控制在logn\log nlogn那么增删查改的效率也可以控制在Olog(n)\log (n)log(n)相比与二叉搜索树有了本质的提升。2.AVL的实现2.1 AVL树的结构templateclassK,classVstructAVLNode{pairK,V_kv;AVLNodeK,V*_parent;AVLNodeK,V*_left;AVLNodeK,V*_right;int_bf;AVLNode(constpairK,Vkv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_bf(0){}};templateclassK,classVclassAVLTree{usingNodeAVLNodeK,V;public:private:Node*_rootnullptr;};2.2 AVL树的插入插⼊⼀个值按⼆叉搜索树规则进行。新增结点以后只会影响祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新从新增结点-根结点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了具体情况我们下面再详细分析。更新平衡因子过程中没有出现问题则插入结束更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后本质调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。平衡因子更新更新原则平衡因子 右子树高度-左子树高度只有子树高度变化才会影响当前结点平衡因子。插入结点会增加高度所以新增结点在parent的右子树parent的平衡因子新增结点在parent的左子树parent平衡因子–parent所在⼦树的⾼度是否变化决定了是否会继续往上更新更新停止条件更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0 或者 1-0说明更新前parent子树⼀边高⼀边低新增的结点插⼊在低的那边插入后parent所在子树高度不变不会影响parent的父亲结点的平衡因子更新结束。更新后parent的平衡因子等于1 或 -1更新前更新中parent的平衡因子变化为0-1 或者 0--1说明更新前parent子树两边⼀样高新增的插入结点后parent所在的子树⼀边高⼀边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲结点的平衡因子所以要继续向上更新。更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1--2说明更新前parent子树⼀边高⼀边低新增的插入结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把parent子树旋转平衡。2、降低parent子树的高度恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新插入结束。不断更新更新到根根的平衡因子是1或-1也停止了。插入代码实现boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_left;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_right;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;while(parent){if(curparent-_left)parent-_bf--;elseparent-_bf;if(parent-_bf0){break;}elseif(parent-_bf-1||parent-_bf1){curparent;parentcur-_parent;}elseif(parent-_bf2||parent-_bf-2){//旋转}else{assert(false);}}}3.AVL树的旋转旋转的原则保持搜索树的规则让旋转的树从不满足变平衡其次降低旋转树的高度旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。1.右单旋当左子树纯粹地比右边高时且高度差为2时就要开始右单旋右单旋有一个好记的规则就是将旋转点的左子树的右子树放到右子树的左子树可以参考下面的例子。而且有时候要旋转两次一次时不够的图三就是旋转了2次。代码实现voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-_leftsubLR;if(subLR){subLR-_parentparent;}Node*Pparentparent-_parent;parent-_parentsubL;subL-_rightparent;if(Pparentnullptr){_rootsubL;_root-_parentnullptr;}else{if(Pparent-_leftparent){Pparent-_leftsubL;}else{Pparent-_rightsubL;}subL-_parentPparent;}parent-_bf0;subL-_bf0;}2.左单旋左单旋和右单旋同理都是规则是一样的唯一不同的就是左单旋是将根的右子树的左子树放到根的左子树的右子树代码实现voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL){subRL-_parentparent;}parent-_parentsubR;subR-_leftparent;Node*Pparentparent-_parent;if(Pparentnullptr){_rootsubR;_root-_parentnullptr;}else{if(parentPparent-_left){Pparent-_leftsubR;}else{Pparent-_rightsubR;}subR-_parentPparent;}parent-_bf0;subR-_bf0;}3.右左双旋产生双旋的条件是比较好辩别的就是当一棵树不是纯粹的一边高时就会发生双旋比如图一根的右子树比左子树高本来理应左旋但是左子树的右子树比左子树矮左旋的代价是把旋上去的那个节点的左子树放到原本的根的右子树上这样就会陷入循环导致问题无法解决所以我们要把右子树变成纯粹的一边高情景有以下几种代码演示voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(subR);RotateL(parent);if(bf0){parent-_bf0;subR-_bf0;subRL-_bf0;}elseif(bf-1){parent-_bf0;subR-_bf1;subRL-_bf0;}elseif(bf1){parent-_bf-1;subR-_bf0;subRL-_bf0;}else{assert(false);}}4.左右双旋原理和右左双旋一样代码演示voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(subR);RotateL(parent);if(bf0){parent-_bf0;subR-_bf0;subRL-_bf0;}elseif(bf-1){parent-_bf0;subR-_bf1;subRL-_bf0;}elseif(bf1){parent-_bf-1;subR-_bf0;subRL-_bf0;}else{assert(false);}}4.AVL树的平衡检测AVL树的平衡检测需要检查检查平衡因子是否正确这时候我们需要一个参照物就要借助树的高度来检查平衡因子是否没有出错。而树的高度我们需要用到递归的方式来得到代码演示intHeight(Node*root){if(rootnullptr){return0;}intHeightLeftHeight(root-_left);intHeightRightHeight(root-_right);returnHeightLeftHeightRight?HeightLeft1:HeightRight1;}boolIsBalanceTree(Node*root){if(rootnullptr){returntrue;}intHeightleftHeight(root-_left);intHeightrightHeight(root-_right);intbfHeightleft-Heightright;if(bf-2||bf2){returnfalse;}if(bf!root-_bf){returnfalse;}returnIsBalanceTree(root-_left)IsBalanceTree(root-_right);}
AVL树（C++详解版）
1. AVL的概念AVL是一颗空树或者具备下列性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树通过控制高度差去控制平衡。AVL树实现这里我们引入一个平衡因子的概念每个结点都有⼀个平衡因子任何结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0/1/-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进性观察和控制树是否平衡。AVL树整体结点数量和分布和完全二叉树类似高度可以控制在logn\log nlogn那么增删查改的效率也可以控制在Olog(n)\log (n)log(n)相比与二叉搜索树有了本质的提升。2.AVL的实现2.1 AVL树的结构templateclassK,classVstructAVLNode{pairK,V_kv;AVLNodeK,V*_parent;AVLNodeK,V*_left;AVLNodeK,V*_right;int_bf;AVLNode(constpairK,Vkv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_bf(0){}};templateclassK,classVclassAVLTree{usingNodeAVLNodeK,V;public:private:Node*_rootnullptr;};2.2 AVL树的插入插⼊⼀个值按⼆叉搜索树规则进行。新增结点以后只会影响祖先结点的高度也就是可能会影响部分祖先结点的平衡因子所以更新从新增结点-根结点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了具体情况我们下面再详细分析。更新平衡因子过程中没有出现问题则插入结束更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后本质调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。平衡因子更新更新原则平衡因子 右子树高度-左子树高度只有子树高度变化才会影响当前结点平衡因子。插入结点会增加高度所以新增结点在parent的右子树parent的平衡因子新增结点在parent的左子树parent平衡因子–parent所在⼦树的⾼度是否变化决定了是否会继续往上更新更新停止条件更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0 或者 1-0说明更新前parent子树⼀边高⼀边低新增的结点插⼊在低的那边插入后parent所在子树高度不变不会影响parent的父亲结点的平衡因子更新结束。更新后parent的平衡因子等于1 或 -1更新前更新中parent的平衡因子变化为0-1 或者 0--1说明更新前parent子树两边⼀样高新增的插入结点后parent所在的子树⼀边高⼀边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲结点的平衡因子所以要继续向上更新。更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1--2说明更新前parent子树⼀边高⼀边低新增的插入结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把parent子树旋转平衡。2、降低parent子树的高度恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新插入结束。不断更新更新到根根的平衡因子是1或-1也停止了。插入代码实现boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_left;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_right;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;while(parent){if(curparent-_left)parent-_bf--;elseparent-_bf;if(parent-_bf0){break;}elseif(parent-_bf-1||parent-_bf1){curparent;parentcur-_parent;}elseif(parent-_bf2||parent-_bf-2){//旋转}else{assert(false);}}}3.AVL树的旋转旋转的原则保持搜索树的规则让旋转的树从不满足变平衡其次降低旋转树的高度旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。1.右单旋当左子树纯粹地比右边高时且高度差为2时就要开始右单旋右单旋有一个好记的规则就是将旋转点的左子树的右子树放到右子树的左子树可以参考下面的例子。而且有时候要旋转两次一次时不够的图三就是旋转了2次。代码实现voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-_leftsubLR;if(subLR){subLR-_parentparent;}Node*Pparentparent-_parent;parent-_parentsubL;subL-_rightparent;if(Pparentnullptr){_rootsubL;_root-_parentnullptr;}else{if(Pparent-_leftparent){Pparent-_leftsubL;}else{Pparent-_rightsubL;}subL-_parentPparent;}parent-_bf0;subL-_bf0;}2.左单旋左单旋和右单旋同理都是规则是一样的唯一不同的就是左单旋是将根的右子树的左子树放到根的左子树的右子树代码实现voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL){subRL-_parentparent;}parent-_parentsubR;subR-_leftparent;Node*Pparentparent-_parent;if(Pparentnullptr){_rootsubR;_root-_parentnullptr;}else{if(parentPparent-_left){Pparent-_leftsubR;}else{Pparent-_rightsubR;}subR-_parentPparent;}parent-_bf0;subR-_bf0;}3.右左双旋产生双旋的条件是比较好辩别的就是当一棵树不是纯粹的一边高时就会发生双旋比如图一根的右子树比左子树高本来理应左旋但是左子树的右子树比左子树矮左旋的代价是把旋上去的那个节点的左子树放到原本的根的右子树上这样就会陷入循环导致问题无法解决所以我们要把右子树变成纯粹的一边高情景有以下几种代码演示voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(subR);RotateL(parent);if(bf0){parent-_bf0;subR-_bf0;subRL-_bf0;}elseif(bf-1){parent-_bf0;subR-_bf1;subRL-_bf0;}elseif(bf1){parent-_bf-1;subR-_bf0;subRL-_bf0;}else{assert(false);}}4.左右双旋原理和右左双旋一样代码演示voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(subR);RotateL(parent);if(bf0){parent-_bf0;subR-_bf0;subRL-_bf0;}elseif(bf-1){parent-_bf0;subR-_bf1;subRL-_bf0;}elseif(bf1){parent-_bf-1;subR-_bf0;subRL-_bf0;}else{assert(false);}}4.AVL树的平衡检测AVL树的平衡检测需要检查检查平衡因子是否正确这时候我们需要一个参照物就要借助树的高度来检查平衡因子是否没有出错。而树的高度我们需要用到递归的方式来得到代码演示intHeight(Node*root){if(rootnullptr){return0;}intHeightLeftHeight(root-_left);intHeightRightHeight(root-_right);returnHeightLeftHeightRight?HeightLeft1:HeightRight1;}boolIsBalanceTree(Node*root){if(rootnullptr){returntrue;}intHeightleftHeight(root-_left);intHeightrightHeight(root-_right);intbfHeightleft-Heightright;if(bf-2||bf2){returnfalse;}if(bf!root-_bf){returnfalse;}returnIsBalanceTree(root-_left)IsBalanceTree(root-_right);}
