引言为什么需要 AVL 树在数据结构的世界里二叉搜索树Binary Search Tree, BST无疑是最优雅的设计之一。它利用左小右大的规则让查找、插入、删除的平均时间复杂度都降到 O(log N)。听起来很美好——直到你真正用它处理一组有序数据。设想我们按 1, 2, 3, 4, 5 的顺序依次插入一棵二叉搜索树你会发现树并没有像预期那样铺开而是笔直地向一侧生长退化成了一条单支链本质上和链表没有任何区别。此时查找 5 需要比较 5 次时间复杂度从 O(log N) 恶化为*O(N)*。树越高性能越差——二叉搜索树的优势荡然无存。问题的根源在于BST 只约束了节点的相对顺序却对树的形状放任不管。同样的 N 个数据可以长成一棵矮胖的平衡树也可以长成一棵瘦高的单链而它们的查找效率天差地别。于是一个自然的想法诞生了——能不能在插入的过程中自动维持树的平衡这正是 AVL 树要解决的问题。它由苏联数学家 Adelson-Velsky 和 Landis 于 1962 年提出是历史上第一种自平衡二叉搜索树AVL 正是两位发明者姓氏的缩写。AVL 树在 BST 的基础上增加了一条硬性约束任意节点的左右子树高度差平衡因子的绝对值不超过 1。一旦插入或删除破坏了这条规则AVL 树就会通过旋转操作把树重新扶正。这一约束保证了树的高度始终维持在 O(log N) 量级从而让查找、插入、删除稳定地保持在 O(log N)不会因为数据顺序而退化。听起来只是加了一条约束但要真正实现它却需要处理不少细节如何高效地检测失衡旋转有哪几种情况双旋之后平衡因子又该如何修正本文将带你从零手写一棵完整的 AVL 树。我们采用三叉链每个节点额外保存_parent指针 平衡因子_bf的实现方案逐步剖析插入、旋转与平衡因子更新的全过程并用测试用例验证它的正确性。读完之后你将不仅理解 AVL 树的原理更能写出经得起随机数据考验的完整代码。二、节点设计为什么用三叉链在动手实现之前先想清楚节点该长什么样这直接决定了后续插入和旋转代码的复杂度。本文的节点结构定义如下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){}};相比普通二叉搜索树的节点这里多了两样东西一个指向父节点的_parent指针以及一个整型的平衡因子_bf。它们也正是 AVL 树实现的核心。2.1_bf平衡因子用一个整数表示高度差平衡因子记录的是一个节点右子树高度减去左子树高度的差值即_bf H(右) − H(左)。还是用树来看最直观逐个节点算一遍叶子节点 2、6、12左右子树都是空高度都为 0所以_bf 0 − 0 0节点 4左子树以 2 为根高度为 1右子树以 6 为根高度为 1_bf 1 − 1 0节点 10左子树为空高度 0右子树以 12 为根高度为 1_bf 1 − 0 1节点 8左右子树高度都是 2_bf 2 − 2 0。这是一棵平衡的树所有节点的_bf都落在 {-1, 0, 1} 之内。再看一棵失衡的节点 4左子树高度 2右子树高度 1_bf 1 − 2 -1节点 8左子树高度 3右子树高度 1_bf 1 − 3 **-2**.当某个节点的_bf超出[-1, 1]的范围就说明以它为根的子树已经不平衡了。于是_bf的取值可以总结为_bf的值含义0左右子树等高1右子树比左子树高一层-1左子树比右子树高一层±2失衡需要旋转修复这样一来平衡因子就成了失衡的报警器每次插入后我们只需检查从新节点到根这条路径上的_bf就能第一时间发现并处理问题——这正是下一节插入流程的核心思路。至于为什么选右减左而不是左减右其实只是一个人为约定只要全篇统一、旋转时对应记清楚即可。本文严格采用右子树高度 − 左子树高度。2.2_parent父指针为回溯和挂接服务这是整份实现中最关键的一个抉择。为什么非要多存一个父指针原因有两个。其一插入后需要自下而上回溯更新平衡因子。新节点插入后只会影响从它到根节点这条路径上所有祖先的子树高度进而影响它们的平衡因子。所以更新工作必须从新节点出发一层层向上走while(parent){if(parent-_leftnode)parent-_bf--;// 插在左边左高bf 减 1elseparent-_bf;// 插在右边右高bf 加 1if(parent-_bf0){break;// 高度不变无需继续向上}elseif(parent-_bf1||parent-_bf-1){nodeparent;// 高度增加继续向上更新parentparent-_parent;// ← 靠 _parent 指针爬到祖父}else// parent-_bf 2 || parent-_bf -2失衡{// ... 根据失衡类型旋转 ...break;}}注意循环里那句node parent; parent parent-_parent;——正是靠_parent指针我们才能不借助任何额外的栈或递归直接爬到祖父节点继续更新。其二旋转后需要把新的子树根重新挂接到祖父节点。以右旋 RotateR 为例旋转会把 subL 提上来成为这棵子树的新根此时必须修正它和原祖父节点的关系Node*Pparentparent-_parent;// ... 旋转调整 left/right/parent ...else{subL-_parentPparent;if(Pparent-_leftparent)Pparent-_leftsubL;elseif(Pparent-_rightparent)Pparent-_rightsubL;}如果没有_parent我们就无法在旋转后快速找到 parent 的父节点也就无法完成这次换根挂接。三、插入流程插入是 AVL 树最核心、也最容易写错的部分。它比普通 BST 的插入只多了一件事——维护平衡。整体思路可以概括为三步① 按二叉搜索树规则插入新节点 → ② 从新节点向上回溯更新平衡因子 → ③ 一旦发现失衡就旋转修复。这三步在代码里对应 Insert 函数的两个阶段先是迭代找位置并挂接然后是那个 while (parent) 回溯循环。下面逐步拆解。3.1 步骤一空树直接建根如果当前是一棵空树新节点就是根直接建好返回if(_rootnullptr){Node*nodenewNode(kv);_rootnode;}此时不需要更新任何平衡因子——单个节点的_bf天然为 0。3.2 步骤二非空则按 key 迭代找插入位置非空时从根出发利用 BST 左小右大的性质一路向下同时用 parent 记录走过的最后一个节点未来的父节点Node*cur_root;Node*parent_root;Node*nodenewNode(kv);while(cur){if(kv.firstcur-_kv.first){parentcur;curcur-_left;}elseif(kv.firstcur-_kv.first){parentcur;curcur-_right;}else{returnfalse;// key 已存在去重}}这里有个值得注意的去重语义当kv.first既不小于也不大于cur-_kv.first说明key已存在AVL 树不允许重复键直接返回 false。所以 Insert 的返回值不仅表示成功与否还隐含了是否为新插入的信息。3.3 步骤三挂接新节点并设置_parent循环结束后 cur 为空parent 恰好是待插入位置的父节点。根据 key 的大小把新节点挂到 parent 的左边或右边别忘了补上_parent指针if(kv.firstparent-_kv.first){parent-_leftnode;node-_parentparent;}else{parent-_rightnode;node-_parentparent;}到这里新节点已经作为叶子加入了树但平衡因子还没动。注意源码里的注释为什么不能在这里直接改parent-_bf因为我们还不知道这次插入会让parent 的哪一侧变高、需要往哪个方向传播——这些信息只有在回溯时逐层判断才清楚。所以_bf的更新放到下一阶段统一处理。3.4 步骤四向上回溯更新平衡因子这是全章的重中之重。新节点插入后只会影响从它到根这条路径上祖先们的子树高度。我们从 parent 出发一层层向上走。每一层先根据新节点落在哪一侧更新_bfwhile(parent){if(parent-_leftnode)parent-_bf--;// 插在左子树 → 左变高 → bf 减 1elseparent-_bf;// 插在右子树 → 右变高 → bf 加 1// ... 见下文三种情况}关于方向的记忆口诀因为_bf 右高 − 左高新节点插在左边使左子树变高_bf就减 1插在右边则加 1。更新完当前节点后根据新的_bf值只有三种可能情况一_bf 0—— 高度不变停止if(parent-_bf0){break;}_bf从 ±1 变成了 0意味着插入把原本较低的一侧补齐了整棵子树的高度没有增加。既然高度没变就不会再影响更上层的祖先回溯可以立即停止。情况二_bf ±1—— 高度增加继续向上elseif(parent-_bf1||parent-_bf-1){nodeparent;parentparent-_parent;}_bf从 0 变成了 ±1说明原本等高现在某一侧高了一层整棵子树的高度增加了 1。这会让父节点也面临某一侧变高的问题所以必须继续向上传播node parent;当前节点上移一层后它成为了祖父节点的孩子下一轮判断parent-_left node时要用它来比较方向所以必须同步上移否则方向判断就会出错。parent parent-_parent;借助_parent指针爬到祖父节点。这一步正体现了第二节里三叉链设计的价值——不用递归、不用额外栈靠父指针就能完成回溯。情况三_bf ±2—— 失衡旋转后停止elseif(parent-_bf2||parent-_bf-2){// 根据失衡类型选择旋转 ...break;}_bf从 ±1 变到 ±2说明插入使某一侧高出了两层以 parent 为根的子树已经失衡。此时必须旋转把树扶正。旋转之后这棵子树的高度会回到插入前的水平不会再向上影响祖先所以旋转完直接 break 即可。至于具体该做哪种旋转左旋、右旋还是双旋取决于 parent 和它的孩子各自的_bf组合我们留到第四章详细展开。这里先记住失衡必然发生在最先出现_bf ±2的那个节点上且只需要修它一次。3.5 平衡因子传播示意图用流程图概括这段回溯四、四种旋转当回溯过程中某个节点的_bf变成 ±2就说明它失衡了必须通过旋转来降高度、恢复平衡。到底是哪一种旋转取决于 parent 和它的孩子各自的_bf组合。一共四种情况按英文助记就是LL、RR、LR、RL。失衡类型触发条件旋转方式LLparent-_bf -2 node-_bf -1RotateR右旋RRparent-_bf 2 node-_bf 1RotateL左旋LRparent-_bf -2 node-_bf 1先RotateL(subL)再RotateR(parent)RLparent-_bf 2 node-_bf -1先RotateR(subR)再RotateL(parent)助记字母表示从 parent 到新节点的路径方向。LL 指新节点插在左子树的左子树里往同一侧连续偏两次LR 则是先左后右的拐折。4.1 RotateRLL 型右旋触发条件parent-_bf -2 node-_bf -1。即 parent 左高而它的左孩子也左高插入发生在左子树的左边。设subL parent-_leftsubLR subL-_rightparent-_right c三步调整对应源码 RotateR第一步调整子树指针。 把 subLR 过继给 parent 当左孩子parent 挂到 subL 右边parent-_leftsubLR;subL-_rightparent;第二步调整父指针。 先记住祖父 Pparent旋转前就得存好Node*Pparentparent-_parent;parent-_parentsubL;if(subLR)subLR-_parentparent;// subLR 可能为空判断后再改第三步把新子树根挂回祖父。if(Pparentnullptr){_rootsubL;// parent 原本是根 → subL 成为新根subL-_parentnullptr;}else{subL-_parentPparent;if(Pparent-_leftparent)Pparent-_leftsubL;elseif(Pparent-_rightparent)Pparent-_rightsubL;elseassert(false);}最后修正平衡因子两者都归零subL-_bf0;parent-_bf0;两个边界细节最容易出错subLR 可能为空。当 subL 没有右孩子时旋转后parent-_left就是空指针此时不需要也不能设置subLR-_parent指向 parent。parent 可能本来就是根。此时没有祖父节点必须更新_root并把subL-_parent置空否则根就被孤立了。4.2 RotateLRR 型左旋触发条件parent-_bf 2 node-_bf 1。与右旋完全镜像。设subR parent-_rightsubRL subR-_leftparent-_rightsubRL;subR-_leftparent;Node*Pparentparent-_parent;if(subRL)subRL-_parentparent;parent-_parentsubR;// ... 与右旋对称的挂接逻辑 ...parent-_bf0;subR-_bf0;镜像之后subRL 为空和 parent 是根这两个边界同样要处理逻辑与右旋一一对应。4.3 RotateLRLR 型左右双旋触发条件parent-_bf -2 node-_bf 1。parent 左高但它的左孩子 subL 却右高——这棵子树是拐着的。为什么单旋解决不了如果对 parent 直接右旋subL 被提上来但它那个较高的右子树 subLR 会被过继给 parent 当左孩子结果 parent 的左边仍然挂着一棵高子树_bf依旧失衡。单旋只能处理一直朝同一侧偏的情况遇到这种先左后右的拐折必须先把它掰直。双旋先左旋 subL再右旋 parentNode*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;// 关键提前保存RotateL(subL);// ① 先对 subL 左旋把拐折掰成 LLRotateR(parent);// ② 再对 parent 右旋RotateL(subL) 后subLR 被顶上 subL 的位置整棵树就变成了标准的 LL再做一次 RotateR(parent) 即可关键点为什么必须先保存subLR-_bf因为 RotateL 和 RotateR 内部都会重写沿途节点的_bf设成 0。等两次旋转做完subLR-_bf早被改掉了所以必须在旋转之前用一个临时变量 bf 记下它原来的值。那这个 bf 有什么用它指示了新节点当初插在 subLR 的哪一侧从而决定旋转后三个节点的最终平衡因子。分三种情况if(bf0)// 新节点就是 subLR 本身{subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1)// 新节点在 subLR 左边b 更高{subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1)// 新节点在 subLR 右边c 更高{subL-_bf-1;subLR-_bf0;parent-_bf0;}else{assert(false);}可以用高度验证一下其中一例bf -1新节点落入 b旋转后 subL 的左右孩子 a、b 同高故subL-_bf 0而 parent 的右孩子 d 比左孩子 c 高一层故parent-_bf 1。与代码完全吻合。4.4 RotateRLRL 型右左双旋触发条件parent-_bf 2 node-_bf -1是 LR 的镜像。新节点插在 parent 右孩子的左子树里。Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;// 同样要提前保存RotateR(subR);// ① 先对 subR 右旋RotateL(parent);// ② 再对 parent 左旋旋转后结构平衡因子按 bf 分三种情况与 LR 镜像if(bf0){parent-_bf0;subR-_bf0;subRL-_bf0;}elseif(bf-1){subR-_bf1;parent-_bf0;subRL-_bf0;}elseif(bf1){subRL-_bf0;subR-_bf0;parent-_bf-1;}结语本文所有代码均来自一份可编译运行的完整工程包含 AVL.h树实现与 AVL.cpp测试用例覆盖了固定序列测试与 10000 个随机数据的压力测试仓库地址AVLTree如果这篇文章帮你理清了 AVL 树的插入与旋转欢迎点个赞或留言交流。若有疏漏之处也欢迎指正。