AVL树这个东西只要搞过一段时间的二叉搜索树基本都会碰到。它本质上就是一棵“严格要求自己”的自平衡二叉搜索树靠平衡因子把左右子树的高度差锁在可接受范围内从而让查找、插入、删除的时间稳定在 O(logn) 级别。标题叫“AVL树的实现和部分注意点”看起来是个老生常谈的话题但真正动手写一遍就会发现插入要不要旋转、删除后哪里需要重新平衡、高度什么时候更新、空指针怎么处理到处都能踩出坑来。这篇文章不用教科书口吻讲定义我会从工程实现的角度把 AVL 树的完整思路、代码、测试方法以及文档里很少写清楚的注意点拆开讲。适合刚学完二叉搜索树、准备手写自平衡树的读者也适合那些树写完了但说不清为什么这么旋的人。看一遍然后照着写一遍基本就不会再怕这种数据结构。1. 项目概述与需求拆解1.1 为什么需要 AVL 树二叉搜索树的平均复杂度很漂亮查找、插入、删除在随机数据下都能做到 O(logn)。但“平均”这两个字才是重点。如果数据按顺序插入比如 1、2、3、4、5 这样一直追加普通二叉搜索树会变成一条链。此时的查找其实就是在遍历链表性能直接掉到 O(n)。有些场景下数据按时间戳顺序生成或者来自某种近似有序的流这种退化一点也不罕见。AVL 树解决的就是这个问题。它给每个节点增加了一个约束左右子树的高度差不能超过 1。这个约束看起来不起眼但数学推导可以证明含有 n 个节点的 AVL 树高度始终接近 log2n 的常数倍。也就是说即使面对最坏的数据序列树的高度也只有几十层所有操作自然稳在 O(logn)。所以在需要长时间频繁插入删除、又要求查询稳定的场景比如内存索引、字典结构、缓存淘汰机制AVL 树虽然实现成本比普通 BST 高但它换来的是不会让人半夜被线上问题叫起来的确定性。这也是为什么它常被当成数据结构课程必须手写一遍的东西。1.2 AVL 树的硬约束平衡因子和高度定义AVL 树的“平衡”不是玄学而是靠一个明确的数值来判定平衡因子。平衡因子一般定义为左子树高度减右子树高度。只要这个值的绝对值不超过 1就认为节点平衡超过 1就要做旋转修复。这里有个最容易被忽略的问题就是空节点高度怎么定义。我用的是最容易统一的一套做法空节点高度为 0叶子节点高度为 1。这样某个节点的高度就可以写成height(node) 1 max(height(node-left), height(node-right))而平衡因子balance(node) height(node-left) - height(node-right)如果 height 的基准定义不一致后面旋转判断和高度更新很容易出现莫名其妙的偏差而且这种偏差不会立刻崩溃只会让树在某些数据组合下偶尔乱掉非常难查。还有一点需要提前明确平衡因子不一定要单独存一个字段它可以随时由左右子树的高度算出来。真正要存的是 height 这个值因为它的计算代价取决于子树高度如果不存每次判断平衡都要递归扫一遍子树操作复杂度会退化。用 int 字段存高度是最常见的方案。1.3 实现选型递归、返回新根、存高度而不是实时算AVL 树按递归实现会清爽很多。递归的关键在于每次对子树进行操作后都可能改变这棵子树的根节点。比如右旋之后原来的父节点变成了新根的右孩子新根成了一个不同的节点。所以递归函数不能只修改传入节点而要返回新的根节点让上一层把返回值接回去。这个设计直接决定了很多代码的 shape。比如插入函数在递归返回时要做三件事更新当前节点高度、检查当前节点平衡因子、决定是否需要旋转。而旋转函数也返回新根于是上层只需要写root-left rotateLeft(root-left);外层调用最终会拿到一棵新的局部子树根节点整个召回链一层层重新构造出平衡的树。选择递归还带来一个重要好处删除节点时的回溯过程天然就是自底向上的。删除造成的失衡可能出现在多个祖先节点递归返回时每一层都有机会检查并修复这比自己在迭代里维护父路径要省心太多。代价是递归调用栈的深度但这恰好因为 AVL 树高度是对数级别所以完全不用担心栈溢出这种问题。2. 旋转机制四种失衡的标准处理2.1 高度更新在旋转里的先后顺序旋转是 AVL 树的灵魂。但真正写旋转代码时最容易出问题的不是旋转指针本身而是旋转后节点高度的更新顺序。以右旋为例旋转前有两个关键节点原来的根节点 y 和它的左孩子 x旋转后 x 成为新根y 成为 x 的右孩子而 x 原来的右子树会被挪到 y 的左子树。旋转后哪些节点的高度变了y 的高度依赖它新的左右孩子必须最先更新。更新完 y 后x 的高度依赖它的右孩子也就是 y所以 x 再更新。顺序一旦颠倒x 算高度时用的还是旧的 y 高度结果就差了一层虽然不至于立即使树崩溃但会埋下很隐蔽的失衡种子。左旋是同样的道理先更新原根节点再更新新的根节点。这个细节我会在后面的代码和实验里反复强调因为它属于那种“书上没写但写代码必踩”的点。2.2 单旋场景LL 与 RR先实现两个最核心的单旋。右旋处理的是 LL 型失衡当前节点的平衡因子大于 1并且左子树的平衡因子大于等于 0说明失衡集中在左侧的左侧。Node* rotateRight(Node* y) { Node* x y-left; Node* T2 x-right; x-right y; y-left T2; updateHeight(y); updateHeight(x); return x; }左旋对称处理 RR 型失衡Node* rotateLeft(Node* x) { Node* y x-right; Node* T2 y-left; y-left x; x-right T2; updateHeight(x); updateHeight(y); return y; }这两个函数都不需要判断当前节点是否为空因为只有非空且有孩子时才可能被调用。调用它们的判断逻辑在统一的 rebalance 函数里做。我见过有人把单旋写成原地修改不改返回值结果外层链条断裂。要记住指针操作后原变量并不会自动变成新根所以旋转函数必须返回新根调用处也必须把返回结果接回到父节点的 left 或 right 字段或者赋值给最外层的 root。2.3 双旋场景LR 与 RL双旋的处理对象是失衡方向不在同一侧的情况。比如当前节点平衡因子大于 1但左孩子反而是右重这就是 LR 型。这时候直接对当前节点做右旋是不行的因为左孩子的右子树太深旋完当前节点仍然不平衡。正确思路是先把左孩子做一次左旋让子问题变成 LL 型再对当前节点做一次右旋。代码里只需要组合两个单旋顺序不能弄反if (balance 1 balanceFactor(node-left) 0) { node-left rotateLeft(node-left); return rotateRight(node); }RL 型是对称的if (balance -1 balanceFactor(node-right) 0) { node-right rotateRight(node-right); return rotateLeft(node); }这里有个很重要的细节第一次旋转完成后必须把返回值赋给 node-left 或 node-right再接第二次旋转。很多初学者忘记这个赋值第一次旋转的结果丢了后面转的是旧指针树结构直接错乱。我把判断和旋转统一放到 rebalance 函数里这样插入和删除都能复用。rebalance 的职责只有三个更新当前节点高度计算平衡因子按四种型式旋转并返回新根。3. 插入与删除完整实现和关键分支3.1 插入的递归模板插入操作分两步先按二叉搜索树的规则把新节点放进去然后沿递归路径向上回溯修复。每一步都调用 rebalance这样即使底层插入导致多个祖先失衡也能在回溯时逐一修好。Node* insert(Node* node, int key) { if (node nullptr) { return new Node(key); } if (key node-key) { node-left insert(node-left, key); } else if (key node-key) { node-right insert(node-right, key); } else { return node; // 重复 key直接放弃 } return rebalance(node); }rebalance 的实现可以写成这样Node* rebalance(Node* node) { if (node nullptr) { return nullptr; } updateHeight(node); int balance balanceFactor(node); // LL if (balance 1 balanceFactor(node-left) 0) { return rotateRight(node); } // LR if (balance 1 balanceFactor(node-left) 0) { node-left rotateLeft(node-left); return rotateRight(node); } // RR if (balance -1 balanceFactor(node-right) 0) { return rotateLeft(node); } // RL if (balance -1 balanceFactor(node-right) 0) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }插入这段代码基本就是 AVL 树的模板细节不多。唯一要注意的是重复 key 的处理我选择直接返回 original 节点不更新高度也不旋转。如果业务要求允许重复键就要在节点里增加一个 count 字段或者规定重复键插到右子树并单独处理不能一句 return node 带过。3.2 删除的完整流程删除比插入复杂一截因为删除一个节点可能会让某个子树高度减 1这个高度变化会向上传播可能在好几个祖先节点上都破坏平衡。先写标准 BST 删除逻辑。删除有三种情况节点没有孩子直接删掉返回空节点只有一个孩子用孩子顶替它节点有两个孩子用右子树的最小节点或者左子树的最大节点替代当前节点。我用的是右子树最小节点因为找起来逻辑清晰。Node* findMin(Node* node) { while (node-left ! nullptr) { node node-left; } return node; } Node* remove(Node* node, int key) { if (node nullptr) { return nullptr; } if (key node-key) { node-left remove(node-left, key); } else if (key node-key) { node-right remove(node-right, key); } else { if (node-left nullptr || node-right nullptr) { Node* temp (node-left ! nullptr) ? node-left : node-right; delete node; return temp; } else { Node* successor findMin(node-right); node-key successor-key; node-right remove(node-right, successor-key); } } if (node nullptr) { return nullptr; } return rebalance(node); }这里的关键分支在于有两个孩子的情况先用后继节点的 key 覆盖当前节点然后去右子树里删除那个后继节点。这样做的意义是避免复杂的指针交换只改 key再递归处理后继的物理删除。还有一种常见做法是找左子树最大节点用在 key 分布偏左或删除频繁的场景可以减少右子树的高度波动。原理上两者都可以只要保持一致性不要一会儿用前驱一会儿用后继。3.3 删除后的“多处失衡”怎么处理插入一个节点最多只会让路径上的一个祖父节点失衡修复一次就能完成。删除不一样子树高度减 1 后所有祖先都可能轮流失衡有些节点修完更高层的节点可能又变得不平衡。递归实现天然覆盖了这一点。remove 函数在每个递归返回处都调用 rebalance最底下一层先恢复带着新的高度继续往上走上一层再判断。所以代码里那个if (node nullptr) return nullptr的判断不可省略因为删除单个孩子节点时remove 直接返回了孩子的引用而这个孩子可能为空如果不判空就直接 rebalance 会空指针崩溃。很多人以为删除只要在最后一个节点做一次旋转这是错的。我在实际测试中见过删除一次后整棵树依然平衡、但某棵子树高度少了一层的情况没过几次插入问题才在另一个节点上爆出来。所以最稳妥的做法就是每层都走 rebalance不要试图去判断“这里该不该旋”。4. 边界、测试与排查经验4.1 最容易被细节坑到的几个点AVL 树代码不长但坑都在细节。我总结几个最容易出问题的地方。第一空节点高度必须统一。我全程用空节点高度 0叶子高度 1但任何时候都不能在某些函数里写死成if (n nullptr) return -1而另一些函数又写成return 0。这种不一致会让平衡因子偶尔算错而且错误结果是可复现但不易察觉的。第二旋转后的高度更新顺序写反。右旋必须先更新原根 y再更新新根 x左旋必须先更新原根 x再更新新根 y。顺序错了不会立刻报错需要多组随机数据才能暴露特别坑。第三双旋时第一次旋转结果没有接回。比如写了rotateLeft(node-left)却不赋值第一次旋转的新根丢掉了后续所有链表指针都会乱。这类 bug 通常一测试就会崩溃反而是最好发现的。第四删除后直接对空节点调用 rebalance。在递归删除单个孩子节点的分支里要特别注意返回值可能为空。规范做法是每个递归返回处先判空再接 rebalance。第五平衡因子的符号方向不统一。有人写左减右有人写右减左本身没有对错但必须确保判断条件跟着改。最怕代码里前半个函数用左减右后半个函数又按右减左来判断树的平衡会彻底错乱。第六递归调用后忘记把返回值接回。插入删除递归后node-left insert(node-left, key)这种赋值链路不能省否则子树的新根会断掉而这种断链不一定立刻让程序崩有时候只是查询结果悄悄不对。4.2 如何验证一棵 AVL 树没有写错手写 AVL 树之后最需要的就是验证方法。只跑一次插入再打印中序遍历根本发现不了旋转问题。我一般会做三件事。第一验证二叉搜索树性质。中序遍历结果必须是严格递增序列这个可以用一个递归函数检查所有节点的 key 都在合理区间内。bool isValidBST(Node* node, long long minKey, long long maxKey) { if (node nullptr) { return true; } if (node-key minKey || node-key maxKey) { return false; } return isValidBST(node-left, minKey, node-key) isValidBST(node-right, node-key, maxKey); }第二验证平衡性和高度正确性。可以写一个递归函数返回子树高度的同时检查每个节点的平衡因子绝对值是否小于等于 1。int checkBalanceAndHeight(Node* node) { if (node nullptr) { return 0; } int leftHeight checkBalanceAndHeight(node-left); int rightHeight checkBalanceAndHeight(node-right); if (abs(leftHeight - rightHeight) 1) { printf(balance error at key %d\n, node-key); exit(1); } int correctHeight 1 max(leftHeight, rightHeight); if (node-height ! correctHeight) { printf(height error at key %d\n, node-key); exit(1); } return correctHeight; }第三做随机化压力测试。随机插入 10 万个数字再随机删除一部分每操作几千次之后就执行一次中序遍历和平衡检查。这种测试能覆盖大量旋转组合比人肉构造用例有效得多。如果随机测过三轮还稳定这棵树的正确性基本就稳了。4.3 实际操作中的几条心得我在调试过程中最有用的习惯是先把 rebalance 单独抽出来然后每个旋转函数都单独测试。具体做法是用手绘小树模拟比如构造一棵三个节点的 LL 型失衡手动调用 rotateRight再打印中序遍历结果。旋转不改 BST 性质中序应该始终递增但树结构会变。只有每个旋转都正确了rebalance 才有意义。打印树结构也很有用。我会写一个缩进打印函数每层右子树向左缩进或者用先序遍历配合换行把节点 key 和 height 同时打印出来。人眼盯着树结构看往往能一眼看出旋转哪一步出现了高度更新错误。还有一个经验就是用 long long 作为 key 的边界测试或者用链式递增数据测试退化场景。插入 1 到 1000 的有序数据如果 AVL 实现正确树的高度应该一直保持在十几层如果某天发现树高接近 1000说明某个分支的旋转判断写错了。5. 实现完之后的一点长期建议5.1 把 rebalance 抽出来不止为了少写代码刚开始写 AVL 树时插入里放一套旋转判断删除里再抄一套代码长了很容易两边改着改着不一致。后来我把 rebalance 抽成公共函数插入和删除都只负责维护 BST 关系和返回新根平衡逻辑只写一遍出问题也好定位。这个习惯后来用到红黑树验证、跳表维护甚至一些自定义索引结构时都很有用核心思路是一样的把“结构调整”和“业务逻辑”分离开。rebalance 函数本身的判断顺序也有讲究。先更新高度再计算平衡因子最后分四支旋转。这个顺序不要轻易改。某些优化写法会把高度更新揉进旋转里但如果 rebalance 里不再更新逻辑会分散增加排查成本。AVL 树本身是个教学级的数据结构代码可读性比微优化重要得多。5.2 我后来在实际项目中怎么看 AVL 树AVL 树频繁旋转的缺点常被拿出来和红黑树比特别是写入密集型场景红黑树因为旋转更少实际跑起来可能更占优。但 AVL 树结构更简单平衡判定非常显式在一棵节点数量不大、读多写少的索引结构里它反而是最容易维护、最不容易写错的选择。我个人的建议是先认真手写一遍 AVL 树把插入、删除、四种旋转、高度更新和验证脚本都跑通。这个过程会比看一百遍教程都值。写完之后再去看红黑树或 B 树你会发现自己开始能用“高度”“旋转”“回溯”这些词去理解更复杂的数据结构了。很多数据结构的本质其实都是在平衡和性能之间做取舍AVL 树就是理解这套逻辑最好的起点。