【C++ AVL树】平衡因子、四种旋转与插入维护

C AVL树平衡因子、四种旋转与插入维护大家好上一篇我们实现了二叉搜索树但它有个硬伤按顺序插数据会退化成一根单支链查找从 O(logN) 掉到 O(N)。AVL 树就是在二叉搜索树上加一层自平衡——每次插入后顺手把歪掉的子树转回来保证任意节点左右两边差不多高增删查都稳定在 O(logN)。先约定两个大白话说法后面全程用高度就是从某个节点往下走到最深的叶子一共要经过几层**平衡因子bf**就是右边高度 − 左边高度所以它等于1 说明右边偏重、等于 -1 说明左边偏重、等于 0 说明两边一样平。这篇把节点结构、平衡因子更新和四种旋转的代码完整搬出来并重点讲清楚每种旋转到底在什么时机用、转完 bf 各是多少。目录一、AVL 树与平衡因子二、节点结构三、插入后怎么更新平衡因子四、什么时候用哪种旋转重点五、右单旋六、左单旋七、左右双旋与三种情况八、右左双旋与三种情况九、插入与平衡校验代码十、总结一、AVL 树与平衡因子AVL 树是最先发明的自平衡二叉搜索树。它要么是空树要么满足左右子树都是 AVL 树且左右子树高度差的绝对值不超过 1。它名字来自两位前苏联学者 Adelson-Velsky 和 Landis 1962 年的论文。为了观察和控制平衡每个节点带一个平衡因子bf。本文和代码统一采用bf 右子树高度 − 左子树高度所以任意节点的 bf 只能是 0、1、-1。注意这个口径和有些教材左减右相反代码全程一致不要记混。为什么允许高度差为 1而不是必须为 0不是不想设计成完全等高而是像 2 个节点、4 个节点这种结构天然做不到两边完全等高最优也只能差 1。取不超过 1是做得到的最严格平衡。整体节点分布和完全二叉树接近高度控制在 logN增删查也就是 O(logN)相比二叉搜索树有了本质提升。补充一句AVL 并不是非带平衡因子不可——也有不带 bf 的写法靠临时遍历左右子树取高度差来判断。但每次现算代价高所以实际实现都在节点里存一个 bf像风向标一样直接告诉我们这棵子树偏左还是偏右。本文统一讲带_bf的版本。二、节点结构相比二叉搜索树AVL 节点多了_bf和_parent_parent用来沿父链向上更新平衡因子。下面是完整节点结构和工程代码一致。templateclassK,classVstructAVLTreeNode{pairK,V_kv;AVLTreeNodeK,V*_left;AVLTreeNodeK,V*_right;AVLTreeNodeK,V*_parent;int_bf;// balance factorAVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;public:// 旋转... 这里没写成员函数在下面private:Node*_rootnullptr;};三、插入后怎么更新平衡因子插入规则和二叉搜索树一样按 key 大小走到空位挂新节点。维护的核心就是从新节点出发沿_parent往上更新 bf。更新原则新节点挂在 parent 的右边parent 的_bf挂在左边_bf--。只有子树高度真的变了parent 的 bf 才会跟着变而 parent 这棵子树的高度变没变又决定了要不要继续往它父亲那里传。往上更新时只会出现下面三种情况括号里是笔记里的典型变化过程bf 变成 0比如从 -1 变 0或从 1 变 0说明更新前 parent 本来就一边高一边矮新节点恰好插在了矮的那一边把矮的补齐了。结果这棵子树的总高度没变父亲的 bf 不受影响更新到此为止bf 变成 1 或 -1比如从 0 变 1或从 0 变 -1说明更新前 parent 左右一样平新节点插下去后一边高了。虽然子树仍然满足平衡要求但它的高度比之前多了 1这个变化会传递给它的父亲所以要继续往上走bf 变成 2 或 -2比如从 1 变 2或从 -1 变 -2说明更新前 parent 本来就一边高一边矮新节点又偏偏插在高的那一边让高的更高、彻底失衡。这时不能再往上更新了必须旋转。旋转有两个目标① 把这棵子树重新转平衡② 把它的高度降回插入新节点之前的高度。正因为高度被压回去了旋转完也就不用再往上更新整支插入结束。最后还有一种自然停止一路更新到了根节点根的父亲是空循环自然结束——哪怕根的 bf 最后是 1 或 -1也没有上层需要它影响了。四、什么时候用哪种旋转重点先记住旋转的两条原则所有旋转都不违背不能破坏搜索树规则——转完任意节点仍然满足左 它 右只是上下左右的挂法变了把歪掉的子树重新转平衡并且顺便把它的高度压回插入前。只要高度压回去了上层就不用再管。拿到第一个失衡节点parentbf 刚变成 ±2 的那个先看它的 bf 是正还是负再看高的那一侧孩子的 bf就能确定用哪种旋转parent 的 bf高的一侧高侧孩子的 bf形状用哪种旋转-2左边高左孩子 subL-1左子树的左边高LL右单旋 RotateR-2左边高左孩子 subL1左子树的右边高LR左右双旋 RotateLR2右边高右孩子 subR1右子树的右边高RR左单旋 RotateL2右边高右孩子 subR-1右子树的左边高RL右左双旋 RotateRL一句话记外侧高LL/RR单旋一次内侧高LR/RL单旋转不动先把内侧折成外侧再单旋。五、右单旋什么时候触发parent10的 bf 从 -1 变成 -2说明左边太高了。看上图以 10 为根它的左孩子是 55 的左边挂 a 子树、右边挂 b 子树10 的右边挂 c 子树a/b/c 是三棵抽象出来的、高度都为 h 的 AVL 子树h≥0代表所有右单旋的通用形态。10 可能是整棵树的根也可能只是上层某个节点的子树根。插入后发生了什么新节点插在 a 子树里a 的高度从 h 变成 h1。从新节点开始沿父链往上更新先更新 5再更新 10——5 的 bf 从 0 变成 -110 的 bf 从 -1 变成 -2。此时以 10 为根的这棵子树左右高度差是 2左边太重必须往右边压一下。旋转具体怎么动对照中间图到右图因为大小关系是5 b 子树所有值 10b 子树既不能留在 5 下面、也不能留在 10 的右边正确位置是 10 的左边——所以先把 b 从 5 的右孩子摘下来挂成 10 的左孩子把 10 降下来挂成 5 的右孩子5 升上去成为这棵子树新的根。这样转完大小关系完全没乱a5b10c 依然成立左右高度差也回到了 1 以内更关键的是这棵子树插入后高度一度涨到 h3右旋后又降回 h2和插入前完全一样。子树高度一旦回到插入前就不会再影响上层所以旋转完不必继续往上更新这一支的插入到此结束。如果 10 原本只是上层的子树根5 还要接回它爷爷原来接 10 的那个位置原来 10 是爷爷的左孩子5 就接左边是右孩子就接右边。旋转部分之上还有没有节点没旋转之前parent还有父亲节点的时候即parent不是根节点的时候我们把parent的父节点记为parentParent。旋转之后要更新parentParent的孩子指向。parentParent的左子树可能旋转部分右子树也可能是都要考虑参考如下图无论是右单旋、左单旋还是左右双旋、右左双旋都是要这么考虑我只示意这一次下面不画了右单旋的完整实现如下//右单旋的实现voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-_leftsubLR;//这个时候要考虑subLR是不是空节点//按照逻辑来说subLR的父节点要更新成parent。但是subLR如果是空节点就没这一说if(subLR)subLR-_parentparent;//考虑parent还有父亲Node*parentParentparent-_parent;subL-_rightparent;parent-_parentsubL;if(parentParentnullptr){_rootsubL;subL-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubL;}else{parentParent-_rightsubL;}subL-_parentparentParent;}parent-_bfsubL-_bf0;}六、左单旋左单旋和右单旋是镜像对称只是把左右反过来。什么时候触发parent10的 bf 从 1 变成 2右边太重。以 10 为根右孩子是 1515 的左边挂 b 子树、右边挂 a 子树10 的左边挂 c 子树a/b/c 同样是高度为 h 的抽象子树。插入后发生了什么新节点插在 a 子树15 的右边里a 从 h 变 h1沿父链更新 15 和 10 的 bf——15 从 0 变 110 从 1 变 2。旋转具体怎么动大小关系是10 b 子树所有值 15b 子树应挂到 10 的右边——先把 b 从 15 的左孩子摘下挂成 10 的右孩子把 10 降下来挂成 15 的左孩子15 升上去成为新根。转完同样恢复搜索树大小关系、把子树高度降回插入前上层不再受影响。右单旋是左边太高向右压左单旋就是右边太高向左压三步一一对应。//左旋voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}parent-_bfsubR-_bf0;}七、左右双旋与三种情况什么时候用parent bf-2但高在左孩子的右边——也就是 subL5的右孩子 subLR8那一侧高。这时直接右单旋压不住得先对 5 左旋、再对 10 右旋中间节点 8 成为新根。为什么单旋转不动右单旋解决的是左孩子的左边高a 侧高。现在高的却是左孩子的右边8 这一侧。如果硬对 10 右旋把 5 提上去8 那一坨还是悬在 5 右边、10 左边高度差没真正降下来。所以思路是分两步先在 5 这棵子树内部对 5 来一次左单旋把 8 从 5 的右边翻到 5 上面来做完这步高就从5 的右边变成了5 的左边形状退化成右单旋能处理的 LL再对 10 右单旋一次8 就稳稳落到新根位置。失衡结构对照上图10 是 parent左孩子 5 是 subL5 的右孩子 8 是 subLR。平衡时 10 的 bf-1、5 的 bf05 左边挂 a高 h8 下面分 e、f 两棵高度 h-1 的子树10 右边挂 c高 h。新节点插在 5 的右子树 b 里也就是 8 这一侧b 从 h-1 长高到 h沿 8→5→10 更新5 的 bf 从 0 变成1右边高了10 的 bf 从 -1 变成-2正式失衡。旋转后到底是哪种 bf取决于新节点插在 8 的左边e还是右边f或者 h0 时 8 自己就是新节点。别死记结论两步旋转做完后 8 成为新根、左边挂 5、右边挂 10只要把每棵子树高度代进去bf 自己就出来了。场景 1h≥1新节点插在 ee 从 h-1 升到 h此时 8 的 bf-1它左边高。先以 5 为旋转点做一次左单旋把 8 从 5 的右边翻上来再以 10 为旋转点做一次右单旋8 落到新根。转完 5 下面是 a高 h和 e高 h左右一样高所以5 的 bf010 下面是 f高 h-1和 c高 h右边比左边高 1所以10 的 bf18 左右两棵子树等高8 的 bf0。情景一视图中我将先左单旋再右单旋的过程画出来了。再其余场景和右左双旋的场景中依次为参考我就都不画了只画这一次。场景 2h≥1新节点插在 ff 从 h-1 升到 h此时 8 的 bf1它右边高。两步旋转后5 下面是 a高 h和 e高 h-1左边比右边高 1所以5 的 bf-110 下面是 f高 h和 c高 h左右一样高所以10 的 bf08 左右等高8 的 bf0。场景 3h0插入前 a/b/c 都是空树8也就是 b自己就是那个新节点旋转前 8 没有左右孩子、bf0。两步旋转后 5 和 10 下面都挂不出非空子树三个节点 bf 全为 0。可以看到双旋不是把 bf 一刀切全置 0而是要按旋转前 8 的 bf 分三种情况分别修正——这正是 RotateLR 里那个if (bf 0) / else if (bf -1) / else if (bf 1)在做的事。voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);RotateR(parent);if(bf0){subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1){subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1){subL-_bf-1;subLR-_bf0;parent-_bf0;}//防御性编程else{assert(false);}}八、右左双旋与三种情况什么时候用parent bf2但高在右孩子的左边——subR15的左孩子 subRL12那一侧高。这是左右双旋的镜像先对 15 右旋、再对 10 左旋中间节点 12 成为新根。为什么单旋转不动左单旋解决的是右孩子的右边高a 侧高现在高的却是右孩子的左边12 这一侧。硬对 10 左旋12 那一坨还是悬在 15 左边、10 右边高度差没降下来。所以分两步先对 15 右单旋把 12 从 15 的左边翻到 15 上面做完高就从15 的左边变成15 的右边形状退化成左单旋能处理的 RR再对 10 左单旋12 落到新根。失衡结构对照上图10 是 parent右孩子 15 是 subR15 的左孩子 12 是 subRL。平衡时 10 的 bf1、15 的 bf010 左边挂 c高 h12 下面分 e、f 两棵高度 h-1 的子树15 右边挂 a高 h。新节点插在 15 的左子树 b 里也就是 12 这一侧b 从 h-1 长高到 h沿 12→15→10 更新15 的 bf 从 0 变成-1左边高了10 的 bf 从 1 变成2正式失衡。旋转后 12 成为新根、左边挂 10、右边挂 15。同样把各子树高度代进去场景 1h≥1插在 ee 从 h-1 升到 h此时 12 的 bf-1它左边高。先以 15 为旋转点做一次右单旋再以 10 为旋转点做一次左单旋。转完 10 下面是 c高 h和 e高 h左右等高10 的 bf015 下面是 f高 h-1和 a高 h右边比左边高 115 的 bf112 左右等高12 的 bf0。场景 2h≥1插在 ff 从 h-1 升到 h此时 12 的 bf1它右边高。两步旋转后10 下面是 c高 h和 e高 h-1左边比右边高 110 的 bf-115 下面是 f高 h和 a高 h左右等高15 的 bf012 左右仍然等高12 的 bf0。场景 3h012 自己就是新节点旋转前 bf0两步旋转后10、12、15 三个节点 bf 全为 0。这三个分支对应 RotateRL 里bf 0 / 1 / -1的三种修正和左右双旋完全镜像。voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(parent-_right);RotateL(parent);if(bf0){subR-_bf0;subRL-_bf0;parent-_bf0;}elseif(bf1){subR-_bf0;subRL-_bf0;parent-_bf-1;}elseif(bf-1){subR-_bf1;subRL-_bf0;parent-_bf0;}//防御性编程else{assert(false);}}九、插入与平衡校验代码下面是插入骨架和平衡校验的完整实现。插入里检测到 bf±2 时留下了旋转的位置把第四节的判断接进来即可。boolinsert(){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;// 更新平衡因子while(parent)//最坏的情况是更新到根根的父亲是空所以以此为判断条件{if(parent-leftcur){parent-_bf--;}else{parent-_bf;}if(parent-_bf0){break;}elseif(parent-_bf1||parent-_bf-1){parentparent-_parent;curparent;}elseif(parent-_bf-2||parent-_bf2){//旋转//这里我太累了实在不想写了旋转相关接口都已经实现//大家根据情况来分类施行不同旋转策略//.......break;}}returntrue;}int_Height(Node*root){if(rootnullptr)return0;intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);returnleftHeightrightHeight?leftHeight1:rightHeight1;}bool_IsBalanceTree(Node*root){// 空树也是AVL树if(nullptrroot)returntrue;// 计算pRoot结点的平衡因子即pRoot左右子树的高度差intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);intdiffrightHeight-leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者// pRoot平衡因子的绝对值超过1则一定不是AVL树if(abs(diff)2){coutroot-_kv.first高度差异常endl;returnfalse;}if(root-_bf!diff){coutroot-_kv.first平衡因子异常endl;returnfalse;}// pRoot的左和右如果都是AVL树则该树一定是AVLreturn_IsBalanceTree(root-_left)_IsBalanceTree(root-_right);}十AVL 高度平衡的二叉搜索树bf 右高 − 左高取值只能是 0/±1插入后沿父链更新 bf变 0 停、变 ±1 继续上、变 ±2 旋转旋转时机parent bf-2 看左孩子-1 右单旋、1 左右双旋bf2 看右孩子1 左单旋、-1 右左双旋外侧高单旋、内侧高双旋双旋后 bf 分三种按新节点落在 subLR/subRL 的左、右还是 h0分别修正三个节点的 bf不能一刀切全置 0写完用_IsBalanceTree递归校验每个节点 bf 与真实高度差是否一致是最稳的自测方式。本文只讲了插入场景删除操作同样会引发 bf 变化和旋转方向相反、更复杂篇幅较长我不太想讲了以后有时间出吧无限期延长讲删除的计划。