企业官网建设流程全解析

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 树就是理解这套逻辑最好的起点。