C++学到现在，最常挂在嘴边的数据结构除了链表、栈、队列，估计就要轮到二叉树了。而二叉搜索树一旦遇到有序插入，直接退化成一个长链表，查找性能从 O(logN) 掉到 O(N)，让人血压上去。AVL 树就是为解决这个尴尬产生的——它在每次插入或删除后，都通过最多几次旋转，让整棵树保持高度平衡。我最近用 C++ 完整实现了一遍 AVL 树的插入、删除、旋转和自测，踩了不少坑。很多坑藏得很深，但一旦理解了旋转的对称性，代码实际上可以短得让人惊讶。这篇文章适合那些已经会写普通二叉搜索树，想进一步搞懂自平衡机制的 C++ 学习者。如果你还没写过二叉树，建议先去复习一下前驱、后继、递归遍历，AVL 树只是在这个基础上多加了一步平衡修复。
正文里每一段代码我都跑过，旋转、删除、验证函数都能直接复制下来用。你会看到对平衡因子的掌握比背八股有用得多，也会明白为什么某一次删除需要一路旋转到根，而插入只需要一次局部处理。文章不会只贴代码，还会把每一步的“为什么”讲清楚。尤其是删除那一块，是网上教程最容易含糊的地方，我会把我自己 debug 的完整链路写出来。
1. 为什么AVL树不是“平衡二叉树”那么简单？
1.1 从二叉搜索树的退化说起
先想一个问题：普通二叉搜索树什么时候最难受？插入顺序是1, 2, 3, 4, 5, 6, 7的时候。每次新节点都挂在右孩子上，树变成一条右斜链，查找数字7需要走 7 层。数据规模一上来，这个代价肉眼可见地失控。
二叉搜索树的平均复杂度 O(logN) 默认建立在“随机插入”这个前提上。只要插入序列有规律，比如几乎有序，树就会偏向一边，复杂度退化成 O(N)。AVL 树的核心方案是给每个节点加一个约束：任意节点的左子树和右子树高度差绝对值不超过 1。满足这个条件的二叉搜索树就叫 AVL 树。
这里容易产生一个误解：有人把 AVL 树当成“完全二叉树”或者“完美平衡”，要求每个节点的左右子树节点数一样。这个要求太苛刻，也没必要。AVL 树关心的只是“高度差”，不是“节点数差”。高度差不超过 1，就能保证整棵树的高度接近 log 级别，查找性能稳定。
1.2 平衡因子与最小不平衡子树
实现 AVL 树之前，必须先明确两个概念。
第一个是平衡因子（Balance Factor）。它表示某个节点的左子树高度减去右子树高度。我用的是：
int balanceFactor = getHeight(root->left) - getHeight(root->right);你也可以用右减左，但整棵树必须保持一致。我习惯左减右，因为直觉上偏左就是正数，偏右就是负数。
第二个是最小不平衡子树。插入或删除一个节点后，理论上从叶子到根这条路径上所有祖先的高度都可能变化，但真正可能失衡的是离叶子最近的那个祖先？不，是路径上第一个出现 |平衡因子| > 1 的节点。把以它为根的子树调整平衡之后，这棵子树的高度会恢复成和插入/删除之前一样，所以它上面的所有节点都不再受影响。这一棵需要调整的子树，就是最小不平衡子树。
我之前一直没想明白：为什么插入只需要调整一次，而删除可能要调整多次？原因就在这里。插入新节点后，某个子树高度从 h 变成 h+1，旋转后该子树高度变回 h，上层不再失衡。删除节点后，子树高度从 h 变成 h-1，旋转后子树高度虽然变回 h，但这是在原高度 h 的基础上减了个 1？不对，旋转后子树高度只能恢复到删除之前的高度 h，但是删除导致整体少了一层，上层节点感受到的高度变化还是存在，所以失衡可能继续向上传播。
这个区别非常重要。等后面写删除逻辑的时候，你会看到我为什么在每一层递归返回处都调用rebalance，而不是只在某一次旋转之后结束。
2. 旋转操作的底层逻辑：四种旋转的推导与记忆方法
2.1 左旋与右旋的代码原型
AVL 树的所有操作归根结底是两种基础旋转：左旋、右旋。其余只是这两者的组合。
右旋的场景：某个节点的左孩子偏高，需要把这个左孩子提上来当新根，原节点变成新根的右孩子。看代码最直观：
AVLNode* rotateRight(AVLNode* node) { AVLNode* leftChild = node->left; node->left = leftChild->right; // 把左孩子的右子树挂到原节点的左子树 leftChild->right = node; // 原节点降级为左孩子的右子树 updateHeight(node); updateHeight(leftChild); return leftChild; }左旋完全对称：
AVLNode* rotateLeft(AVLNode* node) { AVLNode* rightChild = node->right; node->right = rightChild->left; rightChild->left = node; updateHeight(node); updateHeight(rightChild); return rightChild; }注意这两段代码有一个关键细节：先更新原节点的高度，再更新新根的高度。因为新根的高度依赖于原节点的高度，顺序反了，树的高度数据就会错乱。我最初写漏了这一步，导致平衡因子算出来全是乱码，花了半天才定位到。
2.2 LL、RR、LR、RL四种情况的判定与旋转组合
avl树的四种失衡形态，名字都对应“偏高的方向”：
- LL：节点的左孩子偏高，且左孩子的左子树偏高。处理：对节点做一次右旋。
- RR：节点的右孩子偏高，且右孩子的右子树偏高。处理：对节点做一次左旋。
- LR：节点的左孩子偏高，但左孩子的右子树偏高。处理：先对左孩子做一次左旋，再对节点做一次右旋。
- RL：节点的右孩子偏高，但右孩子的左子树偏高。处理：先对右孩子做一次右旋，再对节点做一次左旋。
代码里怎么判断是哪一种？靠平衡因子的符号。
假设balance(root) = getHeight(root->left) - getHeight(root->right)：
- 如果
balance(root) > 1，说明 root 的左子树偏高。此时看balance(root->left)：>= 0：LL，直接右旋。< 0：LR，先左旋root->left，再右旋root。
- 如果
balance(root) < -1，说明 root 的右子树偏高。此时看balance(root->right)：<= 0：RR，直接左旋。> 0：RL，先右旋root->right，再左旋root。
为什么用>= 0而不是> 0判断 LL？因为当左孩子平衡因子恰好为 0 时，虽然左右子树一样高，但结合父节点的失衡，旋转后依然能恢复平衡。写成>= 0更稳妥，能覆盖所有情况。
我把这个逻辑封装成一个统一函数，后面插入删除都调它：
AVLNode* rebalance(AVLNode* root) { if (!root) return nullptr; updateHeight(root); int balance = balanceFactor(root); if (balance > 1) { // 左偏高 if (balanceFactor(root->left) >= 0) { return rotateRight(root); } else { root->left = rotateLeft(root->left); return rotateRight(root); } } if (balance < -1) { // 右偏高 if (balanceFactor(root->right) <= 0) { return rotateLeft(root); } else { root->right = rotateRight(root->right); return rotateLeft(root); } } return root; }2.3 旋转后高度为什么不会错
再看一次旋转代码里那两行updateHeight。
右旋rotateRight(node)中，node的左右子树在旋转后都变了：它的左子树变成了原来leftChild的右子树，它的右子树保持不变。leftChild变成新根，leftChild的右子树变成了node，左子树保持不变。此时只有node和leftChild的高度可能变化，其他节点高度都没动。
高度更新顺序必须是：先更新下层（原节点），再更新上层（新根）。因为leftChild的右子树是node，node的高度本身就是计算leftChild高度的输入。不过你如果写成先更新leftChild再更新node，后者的高度会用到更新过但还不应该包含本轮旋转结果的leftChild？实际上先更新 node 不会有任何问题。养成这个习惯后，双旋转时也要注意：先旋转左/右孩子，再旋转当前节点，每次旋转内部都保持正确顺序。
3. 手写AVL树插入：从找位置到修复平衡
3.1 节点结构设计与高度存储
我的节点结构很简单，没有 parent 指针。为什么不用 parent？因为递归版本里，每一层递归通过返回值把新的子树根传回去，父节点自然能接住，省掉了维护 parent 的烦恼。代码读起来也更清爽。
struct AVLNode { int key; AVLNode* left; AVLNode* right; int height; explicit AVLNode(int k = 0) : key(k), left(nullptr), right(nullptr), height(1) {} };高度存储用height，叶子节点高度为 1，空节点高度为 0。这样父节点的高度就是max(左子树高度, 右子树高度) + 1。为什么叶子高度不是 0？因为叶子节点的左空和右空高度都是 0，它的高度应当是max(0,0)+1=1。否则高度和平衡因子的计算会全乱。我见过不少教程用 0 作为叶子高度，然后 getHeight 返回root ? root->height : 0，问题不大，但你要自己保证所有公式的一致性。我选择最经典的约定：叶子为 1。
3.2 插入后的回溯路径与失衡检查
插入采用递归，每次递归返回时调用rebalance。代码非常短：
AVLNode* insertNode(AVLNode* root, int key) { if (!root) return new AVLNode(key); if (key < root->key) { root->left = insertNode(root->left, key); } else if (key > root->key) { root->right = insertNode(root->right, key); } else { return root; // 已经存在，不处理重复值 } return rebalance(root); }这个递归的神奇之处在于：你不需要显式找“从哪个祖先开始修复”。因为递归调用的路径就是插入路径，每一层返回时都调用rebalance，它会检查当前节点是否失衡。路径上所有需要旋转的节点都会被处理。底层完成旋转后，上层节点的高度可能因此还原，所以上层计算出来的平衡因子也自动正确。
为什么插入时最多只需要一次旋转？因为插入让子树高度最多 +1，旋转能让子树高度恢复原值。恢复后，上层不可能再失衡。这一点和删除形成对比。
3.3 插入完整测试代码
我把辅助函数都补上，组成一个可直接运行的版本：
#include <iostream> #include <algorithm> struct AVLNode { int key; AVLNode* left; AVLNode* right; int height; explicit AVLNode(int k = 0) : key(k), left(nullptr), right(nullptr), height(1) {} }; int getHeight(AVLNode* root) { return root ? root->height : 0; } void updateHeight(AVLNode* root) { if (root) { root->height = std::max(getHeight(root->left), getHeight(root->right)) + 1; } } int balanceFactor(AVLNode* root) { return root ? (getHeight(root->left) - getHeight(root->right)) : 0; } AVLNode* rotateRight(AVLNode* node) { AVLNode* leftChild = node->left; node->left = leftChild->right; leftChild->right = node; updateHeight(node); updateHeight(leftChild); return leftChild; } AVLNode* rotateLeft(AVLNode* node) { AVLNode* rightChild = node->right; node->right = rightChild->left; rightChild->left = node; updateHeight(node); updateHeight(rightChild); return rightChild; } AVLNode* rebalance(AVLNode* root) { if (!root) return nullptr; updateHeight(root); int bf = balanceFactor(root); if (bf > 1) { if (balanceFactor(root->left) >= 0) { return rotateRight(root); } else { root->left = rotateLeft(root->left); return rotateRight(root); } } if (bf < -1) { if (balanceFactor(root->right) <= 0) { return rotateLeft(root); } else { root->right = rotateRight(root->right); return rotateLeft(root); } } return root; } AVLNode* insertNode(AVLNode* root, int key) { if (!root) return new AVLNode(key); if (key < root->key) { root->left = insertNode(root->left, key); } else if (key > root->key) { root->right = insertNode(root->right, key); } else { return root; } return rebalance(root); } void inorder(AVLNode* root) { if (!root) return; inorder(root->left); std::cout << root->key << " "; inorder(root->right); } int main() { AVLNode* root = nullptr; for (int i = 1; i <= 7; ++i) { root = insertNode(root, i); } inorder(root); std::cout << "\nHeight: " << root->height << "\n"; return 0; }跑一下，中序遍历输出1 2 3 4 5 6 7，说明二叉搜索树性质没破坏。打根的高度，实测是 3。因为 7 个节点的 AVL 树高度是 3，比普通二叉树的有序插入高度 7 少了一半还多。
这个例子也回答了“接近有序的数据会不会让 AVL 退化”的疑问：不会退化成链表，但会触发旋转，插入 2、3、4 时都会有不同的旋转发生。
4. AVL树的删除：真正的重灾区
4.1 删除节点后的失衡传播
删除的难点不在“删”本身，而在于删除之后平衡的连锁反应。前面说过，删除一个节点后，树高整体可能减少 1，这意味着所有祖先节点的平衡因子都可能变化，而且旋转修复后，上层可能依然失衡。
举个例子，一棵树右子树偏高，你从右子树里删了几个点，右子树变矮了，反而可能导致某个祖先左偏高。这时虽然你刚刚对某个局部做了右旋，但上层节点的平衡因子依然可能是 -2 或者 +2，需要继续处理。所以删除的正确实现是：每一层递归返回时都调用rebalance，让修复一直传播到根。
4.2 删除逻辑里的四个易错点
我在写删除时踩过四个坑，逐一说明。
第一个坑：删除有两个孩子的节点时，不能只是用后继节点替换掉 key，然后把后继删了就完事。你需要递归地调用deleteNode(root->right, successorKey)，这样才能让被删除的后继所在路径上的节点完成平衡更新。如果你在原树里手动切断后继节点与父节点的连接，很容易漏掉高度更新。
第二个坑：只有一个孩子或没有孩子的节点，直接返回另一个孩子。但如果返回的是非空孩子，这个孩子的高度可能没更新。别担心，因为父节点递归返回后会调用rebalance，它会重新计算高度。不过你必须在deleteNode的典型实现里小心：删除一个叶子节点后，rebalance(root)会处理断裂后的高度。如果直接把非空子树返回给上一层，上层 rebalance 也能处理。
第三个坑：找后继用的是右子树的最小节点。最小节点一定没有左孩子，所以删除它时会走入“只有一个孩子或没有孩子”的分支，整个过程很干净。相反，用前驱（左子树最大节点）也是对称的，但前驱可能没有右孩子，同样可行。我习惯用右子树最小。
第四个坑：删除全部节点后根变成 nullptr。任何对空节点的getHeight和balanceFactor都要返回 0，否则越界崩溃。
4.3 删除完整实现源码
以下删除函数可以直接和插入部分拼在一起：
AVLNode* findMin(AVLNode* root) { while (root && root->left) root = root->left; return root; } AVLNode* deleteNode(AVLNode* root, int key) { if (!root) return nullptr; if (key < root->key) { root->left = deleteNode(root->left, key); } else if (key > root->key) { root->right = deleteNode(root->right, key); } else { // 找到了要删除的节点 if (!root->left) { AVLNode* temp = root->right; delete root; return temp; } else if (!root->right) { AVLNode* temp = root->left; delete root; return temp; } else { // 有两个孩子：找右子树最小值 AVLNode* successor = findMin(root->right); root->key = successor->key; root->right = deleteNode(root->right, successor->key); } } return rebalance(root); }这里我特别说明一下：为什么deleteNode的递归调用返回后不需要手动判断是否需要继续旋转？因为rebalance内部已经做了所有事情。它先updateHeight，再检查平衡因子，然后根据情况旋转。如果旋转后树的高度发生了变化，上层递归返回时又会调用rebalance，如此一层层向上修正。所以这个递归结构天然就能处理“删除需要多次旋转”的场景。
为了验证删除后修复的正确性，我做了一个测试：依次插入 1 到 50，然后从 1 到 25 顺序删除。输出中序遍历和根的高度。实测中序遍历始终有序，树高始终在合理范围。我没有在代码里额外打印每一次的高度，但每一步都用下面第 5 小节的自检函数验证过。
5. 查找、遍历与正确性验证：让代码“自证”平衡
5.1 查找与中序遍历
删除和插入都搞定后，查找反而最简单。递归或者循环都行：
bool search(AVLNode* root, int key) { if (!root) return false; if (key == root->key) return true; return key < root->key ? search(root->left, key) : search(root->right, key); }中序遍历上面写过了，顺序输出就是从小到大，可以快速核对搜索树性质是否被破坏。
5.2 自检函数：isAVLTree
写 AVL 树最容易出现的问题是：某个旋转写错，但自己看不出来。所以我强烈建议写一个自动校验函数，递归检查两个条件：
- 是否满足二叉搜索树性质：左子树所有 key 小于当前 key，右子树所有 key 大于当前 key。
- 是否满足 AVL 平衡条件：每个节点的平衡因子绝对值不超过 1。
判断 BST 时，不能只比较当前节点和左右孩子的大小，因为可能出现跨层的不符合。稳妥做法是传上下界：
bool isBST(AVLNode* root, long long minKey, long long maxKey) { if (!root) return true; if (root->key <= minKey || root->key >= maxKey) return false; return isBST(root->left, minKey, root->key) && isBST(root->right, root->key, maxKey); }这里直接用long long，初始上下界传LLONG_MIN和LLONG_MAX，避免 key 等于极端整型时的边界问题。
平衡检查：
bool isBalanced(AVLNode* root) { if (!root) return true; int bf = balanceFactor(root); if (bf > 1 || bf < -1) return false; return isBalanced(root->left) && isBalanced(root->right); }这两个函数组合起来，就是isAVLTree：
bool isAVLTree(AVLNode* root) { return isBST(root, LLONG_MIN, LLONG_MAX) && isBalanced(root); }我每次插入或删除后都调用它。一旦返回 false，就说明某层出现了错误，配合断点可以快速定位。我的实际经验是：绝大部分错误发生在双旋转时 left/right 指针接错，或者旋转后高度没有及时更新。由于自检盯着平衡因子，这类错误基本上一跑就现形。
5.3 随机数据压测与测试结果
手写测试用例永远不可能覆盖所有情况，我建议做随机测试。下面的代码生成随机序列，插一组、删一组，每次操作后检查isAVLTree：
#include <random> #include <vector> #include <climits> #include <unordered_set> int main() { AVLNode* root = nullptr; std::mt19937 rng(2025); std::uniform_int_distribution<int> dist(0, 100000); std::unordered_set<int> nums; while (nums.size() < 10000) { nums.insert(dist(rng)); } std::vector<int> insertData(nums.begin(), nums.end()); std::vector<int> deleteData(insertData.begin(), insertData.begin() + 5000); for (int x : insertData) { root = insertNode(root, x); if (!isAVLTree(root)) { std::cerr << "Insert failed at " << x << "\n"; return 1; } } std::cout << "After insert: height=" << getHeight(root) << "\n"; for (int x : deleteData) { root = deleteNode(root, x); if (!isAVLTree(root)) { std::cerr << "Delete failed at " << x << "\n"; return 1; } } std::cout << "After delete: remaining=" << (int)(nums.size() - deleteData.size()) << " height=" << getHeight(root) << "\n"; return 0; }我在本地跑过 1 万次插入、5 千次删除，每一步自检都通过。1 万节点的 AVL 树，高度实测是 14 左右，和理论值ceil(log2(N+1))非常接近。对比普通二叉搜索树，如果按随机顺序插入，高度大约在 24 上下；如果按有序序列插入，普通搜索树高度会直接变成 10000。AVL 的高度稳定优势在这里体现得清清楚楚。
6. 工程实践中的几个细节与常见坑
6.1 递归带来的栈深度，其实不是大问题
有人担心递归插入删除会爆栈。AVL 树保证高度 O(logN)，以 10 亿节点的树来说，高度也不到 30，递归调用深度也就 30 层左右。正常情况下完全不用担心。普通二叉搜索树才需要担心递归深度的问——如果数据有序插入，深度可能等于节点数，几万次递归就可能把栈压爆。
如果你想写一个不依赖递归的 AVL 树，就得维护 parent 指针，或者在迭代过程中用栈记录路径。工程上如果真的需要极致性能，通常会考虑更复杂的自平衡结构。但学习阶段我认为递归是理解 AVL 树最好的方式，它让每个节点都只关心自己这一层的平衡修复。
6.2 指针引用与父节点维护
网上有些版本的 AVL 树会用AVLNode*& root或者双重指针传入根节点。这样做可以避免返回值，但会让插入和删除代码更难读。我坚持用返回值更新父节点的指针，原因很简单：每个节点在递归返回后，能明确拿到以自己为根的子树的新根，然后挂在父节点对应位置，逻辑无歧义。
如果你非要在写完递归版本之后，改成循环版本，有一个很现实的坑：rotateLeft和rotateRight返回新子树根后，父节点必须立刻接住这个返回值，否则新根就会丢失。递归版本天然接住了，迭代版本里要手动操作，很容易漏。我曾经在实现红黑树的时候漏过一次，整个树直接乱掉，从此更坚定地用递归来接。
6.3 删除后根为空、释放与复用
删除所有节点后，deleteNode返回nullptr，如果你的调用端没有把根变量置空，后续再insertNode(root, key)时会直接把节点挂到已经悬空的指针上？不会，因为你的root变量在调用端仍然是旧指针，但旧节点已经被delete，这是典型的悬垂指针。正确的调用方式是：
root = deleteNode(root, key);用root接收返回值，而不是只调不接收。这一点很多人知道，但真正写的时候容易因为deleteNode的参数和返回值同名而迷惑。我在设计函数时，内部用root作为递归参数，外部同样用root接收新根，因为二者是不同作用域，C++ 允许，但新手看起来容易跟丢。你要么换名，要么注释清楚。我测试随机删除时，中途遇到过一次Access Violation，就是因为删掉最后一个节点后，没有把root更新为nullptr，后续又取了一次root->height。
6.4 平衡因子方向造成的旋转陷阱
如果你的balanceFactor用的是“右子树高度减左子树高度”，那么所有判断符号都得反过来。很多人写的时候只改了一个地方，结果出现“有时候旋转正确，有时候不对”的诡异 bug。我的建议是：把平衡因子函数定义写在固定位置，所有 rebalance 判断都从它出发。如果你以后想改成右减左，全局搜索替换，别手改单点。
另一个细节是rebalance里对balanceFactor(root->left)的判断，一定要在调用旋转前重新计算，不能复用外部已经算过的bf，因为先旋转左孩子后，root->left已经变了。我在 2.2 的代码里就是这么写的：先root->left = rotateLeft(root->left)，接着立刻return rotateRight(root)，这个调用链顺理成章。
6.5 什么时候该用AVL，什么时候该用红黑树
聊到这里，顺口提一句工程选型。AVL 树查找时最坏比较次数就是树高，比红黑树略小，因为它对平衡的要求更高。但每次插入删除，AVL 树可能要旋转多次，红黑树最多旋转三次且对高度限制较松。如果你的场景是读多写少、需要频繁查询，AVL 树在理论上更优。如果插入删除非常频繁，红黑树更合适。C++ 标准库里的std::map和std::set一般用红黑树实现，但这不是说 AVL 树没有价值——它结构直观，自平衡原理清晰，是理解更复杂平衡树的最佳跳板。
实现 AVL 树的过程中，我最深的体会是：写代码前先把四种旋转画清楚，比对着代码硬背有用得多。旋转的本质是“保序地换根”，左孩子升上来，原根往右挪，中间的子树交接给原根。你只要记住这一点，LL、RR、LR、RL 都可以现场推导出来。画完图再写旋转函数，错误率会低非常多。插入和删除的核心都是递归回溯，每一层rebalance都在做同一件事。你的代码只需要保证三件事：高度准确、平衡因子可靠、旋转方向正确。这三件事都验证好，一棵 AVL 树就立起来了。最后再说一个小技巧：写完后先跑有序插入，再跑随机插入，再跑随机删除。有序插入能检验旋转对连续数据的反应，随机测试能覆盖边界条件。如果这两种测试都能连续通过 10000 次操作不出错，这棵树基本就可以放心用了。
