企业官网建设流程全解析

学平衡二叉树的时候，有句话我印象很深：普通二叉搜索树（BST）的查询性能，完全取决于输入数据给你面子还是不给面子。数据有序进入，树就直接歪成链表，查询从 O(log n) 变成 O(n)，你在面试里讲“BST 平均 log n”的时候，面试官下一个问题基本就是“那最坏情况呢”。为了把最坏情况摁住，AVL 树和红黑树这两棵平衡树出现了。这篇文章是我从概念到模拟实现完整走了一遍之后整理的笔记，重点放在旋转、插入修复、删除修复这些最容易卡壳的环节，最后会附上我自己实测的数据对比和一堆踩坑记录，适合正在复习数据结构、准备手撕平衡树的人直接参考。

很多人学这两棵树的时候，习惯直接背旋转代码，背完就忘，忘了再背，原因就是没搞明白它们到底在解决什么。先把这个底层问题说透，后面的代码就顺理成章了。

1. 为什么要把 BST 武装成平衡树

1.1 BST 退化：一场有序插入引发的灾难

二叉搜索树的查找过程本质上是二分查找的树形展开：每走一步，你都能丢掉一侧子树，把搜索范围砍半。这个“砍半”的美好假设，建立在树高是 O(log n) 的基础上。可一旦树失去平衡，比如按 1、2、3、4……的顺序插入，每个新节点都只会挂到右孩子上，树的形状变成一条单链，查找最后一个元素你要走满整棵树。

用数据感受一下。插入 10 万个顺序递增的 key，普通 BST 的高度就是 10 万，AVL 树高度大约 17，红黑树高度大约 34。查找一个最深的节点，前者要做 10 万次比较，后者只需要几十次。几十次和十万次的差距，在数据库索引、缓存淘汰、路由表这类高频查询场景里就是天壤之别。

所以平衡树做的事情说起来非常简单：在插入、删除之后，通过局部的结构调整，把树的高度重新压到对数级别。关键就在于“局部调整”怎么做，以及调整的成本如何控制。

1.2 AVL 树：用高度差把树形“锁”住

AVL 树是 1962 年由 Adelson-Velsky 和 Landis 提出的，它立了一条非常朴素的规矩：任意节点的左子树和右子树高度差不超过 1。这个高度差就是平衡因子（Balance Factor），一般定义为左高减右高。只要某次插入或删除让某个节点的高度差变成 2 或者 -2，马上触发旋转。

AVL 的“严格”意味着它的树高非常接近 theoretical 最优。n 个节点的 AVL 树，高度严格小于 1.44 * log2(n + 2)，而且这个界限在数据量特别大的时候更贴近 log2(n) 本身。代价就是你为了维持这种严格平衡，插入时平均需要旋转更多次，删除时可能一路调整到根节点。

我把 AVL 的调平衡理解成“强迫症患者整理书架”：每一本书放进去之后，都要检查周围书架高度差有没有超过一层，超过就立刻把局部书架重新盘一遍。

1.3 红黑树：用颜色换更低的调整成本

红黑树是 1972 年由 Rudolf Bayer 提出的，它放弃了对单节点高度差的强制约束，改用颜色规则来保证“最长路径不超过最短路径的两倍”。这五条规则你应该早就背得滚瓜烂熟：

1. 每个节点非红即黑
2. 根节点是黑色
3. 叶子节点（NIL）是黑色
4. 红色节点的两个子节点必须是黑色（不能出现连续红节点）
5. 从任一节点到其每个叶子节点的所有路径，包含相同数量的黑色节点

第 5 条规则是红黑树的灵魂。它保证了“黑高”一致，再加上第 4 条限制连续红节点，理论上最长路径就是“黑 + 红 + 黑 + 红……”交替，最多是纯黑路径的两倍。这个“不超过两倍”虽然不如 AVL 的“高度差不超过 1”精确，但已经足够把树高限制在 O(log n)，换来的是更少的旋转。

AVL 追求绝对均衡，红黑树追求“尚算均衡”。所以红黑树在插入、删除频繁的场景下整体成本更低，STL 的 map、set，Linux 内核的调度器、虚拟内存管理，用的都是红黑树。

2. AVL 树模拟实现：旋转是最值得写十遍的代码

2.1 节点设计和高度维护

AVL 节点的数据结构比普通 BST 多一个height字段。不需要像红黑树那样存父指针，因为插入修复时我们用递归自底向上回退，父节点天然就在递归栈里。

#include <algorithm> using namespace std; struct AVLNode { int key; int height; AVLNode* left; AVLNode* right; AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {} }; int getHeight(AVLNode* node) { return node ? node->height : 0; } int getBalance(AVLNode* node) { return node ? getHeight(node->left) - getHeight(node->right) : 0; } void updateHeight(AVLNode* node) { node->height = max(getHeight(node->left), getHeight(node->right)) + 1; }

这里有个新手最容易犯的错：getHeight(nullptr)返回 0 才能让高度计算正确，千万不能因为偷懒在空指针判断里返回 -1，那会导致父节点高度全部算错。叶子节点高度为 1 而不是 0，这是我习惯的约定，你把nullptr高度当 0、空叶子当 0、单节点高当 1，这套保持全局一致就没有问题。

2.2 四种失衡与旋转选择

AVL 插入之后只需要处理四种失衡情况。如果用 LL、LR、RL、RR 来命名，记忆方式非常简单：LL 和 RR 是单旋，LR 和 RL 是双旋。LL 就是“左边太重，往右掰”，RR 就是“右边太重，往左掰”。LR 是“左孩子的右子树过长”，必须先左旋左孩子变成 LL，再右旋根节点；RL 同理。

AVLNode* rotateRight(AVLNode* y) { AVLNode* x = y->left; AVLNode* T2 = x->right; x->right = y; y->left = T2; updateHeight(y); updateHeight(x); return x; } AVLNode* rotateLeft(AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; y->left = x; x->right = T2; updateHeight(x); updateHeight(y); return y; }

为什么双旋不能直接用两次单旋代替？可以，双旋本来就是两次单旋的复合。关键在于顺序和轴的选取。LR 的情况如果直接对根节点右旋，你会把“左孩子的右子树”提上来，但那个子树依然偏在右边，问题没有解决。必须先让左孩子左旋，把 LL 形态构造出来，再对整体右旋。这个“先处理孩子，再处理自己”的思路，在红黑树里还会出现一次。

判断用哪种旋转，我用 balance 因子加插入位置来区分：

2.3 插入过程的完整代码

AVL 插入的递归写法和普通 BST 几乎一样，只是每次递归返回后要重新计算高度并检查平衡因子。插入的 key 和当前节点相等时，我直接返回不处理，这对应集合语义；如果要做映射表，就在相等分支里覆盖 value。

AVLNode* insertAVL(AVLNode* node, int key, int& rotateCount) { if (!node) return new AVLNode(key); if (key < node->key) node->left = insertAVL(node->left, key, rotateCount); else if (key > node->key) node->right = insertAVL(node->right, key, rotateCount); else return node; updateHeight(node); int balance = getBalance(node); // LL if (balance > 1 && key < node->left->key) { rotateCount++; return rotateRight(node); } // RR if (balance < -1 && key > node->right->key) { rotateCount++; return rotateLeft(node); } // LR if (balance > 1 && key > node->left->key) { node->left = rotateLeft(node->left); rotateCount++; return rotateRight(node); } // RL if (balance < -1 && key < node->right->key) { node->right = rotateRight(node->right); rotateCount++; return rotateLeft(node); } return node; }

写这段代码的时候有个隐藏的细节：判断 LL 时用的是key < node->left->key，而不是盲目比较balance > 1就右旋。因为 balance > 1 只能说明左子树比右子树高，但具体是左孩子的哪一侧变高，要靠 key 的数值去判断。如果插入的是重复 key，函数在前面就直接 return 了，不会走到这里。把 key 判断换成“比较两个子树高度”也能判断，但用 key 更直观，而且不需要额外查询。

LR 分支里那句node->left = rotateLeft(node->left)很容易被漏写。漏掉之后直接把根右旋，旋转后的树依然是失衡的，树高并没有真正恢复。我自己第一次手撕 AVL 就犯过这个错，表现出来就是插入了固定数据之后，验证函数检查平衡因子没过。

3. 红黑树模拟实现：插入修复的三种情形

3.1 红黑规则与节点默认颜色

红黑树的节点结构比 AVL 多一个 parent 指针和颜色标记。有人问 non-recursive 实现是不是必须存 parent，我的回答是：如果只做插入，递归加引用也能绕过去；但删除修复的循环逻辑里有大量“找叔父、找祖父、找兄弟”的操作，没有 parent 指针写起来的复杂度会指数级上升。STL 的实现也是带 parent 的。

enum Color { RED, BLACK }; struct RBNode { int key; Color color; RBNode* left; RBNode* right; RBNode* parent; RBNode(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };

新插入的节点为什么默认红色？想一下规则 5：如果插入黑色节点，从祖父到叶子的某一条路径就会多一个黑色节点，后面对黑高的破坏需要大范围调整。红色节点则不同，它唯一可能违反的是规则 4（连续红节点），而连续红节点只会影响局部路径，修复范围小得多。所以“先默认红，再向上修复”是成本最低的策略。

3.2 三种修复情形的判别与处理

插入修复的逻辑可以收敛成一张很清晰的决策表。假设插入的节点是 z，它的父节点是红色（如果是黑色就直接结束了），看叔叔节点 y 的颜色：

情况一：叔叔是红色

把父节点和叔叔都变黑，祖父变红，然后 z 上移到祖父继续循环。这是一种“扩散式”修复，红黑颜色向上浮，把冲突从局部推向更高层。纯变色完成后子树的黑高不变，所以不需要旋转。

情况二：叔叔是黑色，且 z 是内侧节点

也就是 z 是父节点的右孩子，而父节点是祖父的左孩子（或者镜像）。先用父节点做一次旋转，让内侧变外侧，此时树形从 LR/RL 变成 LL/RR，但颜色冲突还在，走到情况三。

情况三：叔叔是黑色，且 z 是外侧节点

父节点变黑，祖父变红，然后对祖父旋转。旋转完成后，原来的父节点代替祖父成为子树根，整棵子树的黑高和旋转前保持一致，而且不会再出现连续红节点。

下面是一个可以直接跑通的插入修复代码，我把左、右两侧分开写成两个函数，避免在一大段 if-else 里迷路：

void rotateLeft(RBNode*& root, RBNode* x) { RBNode* y = x->right; x->right = y->left; if (y->left) y->left->parent = x; y->parent = x->parent; if (!x->parent) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; } void rotateRight(RBNode*& root, RBNode* x) { RBNode* y = x->left; x->left = y->right; if (y->right) y->right->parent = x; y->parent = x->parent; if (!x->parent) root = y; else if (x == x->parent->right) x->parent->right = y; else x->parent->left = y; y->right = x; x->parent = y; } void fixupInsert(RBNode*& root, RBNode* z) { while (z->parent && z->parent->color == RED) { RBNode* grand = z->parent->parent; if (z->parent == grand->left) { RBNode* uncle = grand->right; if (uncle && uncle->color == RED) { z->parent->color = BLACK; uncle->color = BLACK; grand->color = RED; z = grand; } else { if (z == z->parent->right) { z = z->parent; rotateLeft(root, z); } z->parent->color = BLACK; grand->color = RED; rotateRight(root, grand); } } else { RBNode* uncle = grand->left; if (uncle && uncle->color == RED) { z->parent->color = BLACK; uncle->color = BLACK; grand->color = RED; z = grand; } else { if (z == z->parent->left) { z = z->parent; rotateRight(root, z); } z->parent->color = BLACK; grand->color = RED; rotateLeft(root, grand); } } } root->color = BLACK; }

这里最容易被忽略的一点是while循环的进入条件。第一次循环判断的是“父节点是不是红色”，如果父节点是黑色就可以退出了；如果父节点为空，说明 z 已经升到根，循环退出后强制把根染黑。很多实现会额外在uncle判断里先判空，实际上空叔叔等价于黑色叔叔，直接走 else 分支即可，不需要单独处理。

旋转的时候还有个小坑：rotateLeft/rotateRight里必须同步更新 parent 指针。有些人只改了 left、right 没改 parent，结果修复循环里走两步就拿到了 nullptr，程序直接崩溃。

3.3 删除修复的“双黑”难题

删除比插入难，这是红黑树的共识。插入修复只需要处理“父红子红”的冲突，删除修复要解决的问题是“某个路径少了一个黑色节点”，也就是黑高失衡。为了解决这个问题，我们把这个缺失黑节点的路径标记成“双黑”（double black），修复的目标就是消除双黑。

删除分两步：先用 BST 的方式找到替代节点（右子树最小或左子树最大），把目标节点值拷过来，然后物理删除替代节点。如果被删除的节点是红色，没有任何问题直接结束；如果被删除的节点是黑色，它的位置就变成了双黑节点，需要把它的兄弟节点分情况讨论：

1. 兄弟是红色：父节点变红，兄弟变黑，然后旋转父节点，转换之后问题变成兄弟是黑色的情形。

2. 兄弟是黑色，兄弟的两个孩子都是黑色：兄弟变红，双黑节点向上移动到父节点。如果父节点是红色，父节点变黑就结束；如果父节点是黑色，父节点继续作为双黑节点递归处理。

3. 兄弟是黑色，兄弟的左孩子是红色，右孩子是黑色：对兄弟做右旋，把红色孩子翻到外侧，转换成情况 4。

4. 兄弟是黑色，兄弟的右孩子是红色（外侧红）：父节点的颜色平移给兄弟，父节点变黑，兄弟的右孩子变黑，旋转父节点，双黑消除。

这四种情况是等镜像的两侧各一套。写删除修复的时候，我强烈建议先把对称的两半各自用一个函数封装，比如fixupDeleteLeft和fixupDeleteRight，否则很容易在镜像转换的时候把 left/right 写反。我在第一次写删除修复时就是因为左右镜像没对应上，测了一晚上全是断言失败，最后把两半拆开才找到问题。

物理删除节点时还有一个边界条件：如果要删的节点是根节点，直接置空返回；如果只有一个孩子，直接用孩子顶上来并保持颜色；如果两个孩子的替代节点是叶子或只有一个右孩子，需要先把替代节点从树上摘下来。

4. 实测对比：高度、旋转次数与场景选择

4.1 实测高度、旋转次数与调用成本

学习平衡树不能只看理论。我写了一段压测程序，分别对普通 BST、AVL 树、红黑树插入十万个随机整数，统计三者的高度和旋转次数，结果如下：

随机数据下 AVL 和红黑树的表现差距不大，红黑树更高是因为它的平衡条件更宽松。有序数据下普通 BST 直接退化，AVL 和红黑树依然稳定。旋转次数上，插入阶段 AVL 与红黑树实际差距并不明显，真正的差距会在删除操作上进一步拉开，红黑树删除修复的触发频率比 AVL 低不少。

这就是为什么 STL map、set 选红黑树而不选 AVL：map 是高频读写的容器，删除操作频繁，红黑树的整体调整成本更低。而像数据库的只读索引、比赛评测中大量查询的场景，AVL 的严格平衡更能压榨出性能。

4.2 AVL 与红黑树的选择建议

选型从来不是“谁更高级”的问题，而是“你的场景里什么操作最频繁”的问题。我做了一个表格，方便直接对照：

实际工程里，红黑树因为删除操作的“3 次旋转定胜负”特性，很容易实现可预测的延迟；AVL 的删除则可能一直旋转到根，最坏情况下旋转次数是 O(log n)。如果你做的是硬实时系统，红黑树的删出成本更容易被保证。

但也不要盲目迷信红黑树。纯粹的“读多写少”场景，AVL 的查询路径更短，加上缓存友好的节点布局，实测查询能比红黑树快 10% 到 20%。很多内存数据库的跳表与 AVL 并存，也是因为读请求占比太高时，AVL 更划算。

4.3 用断言验证树的性质

模拟实现写完，最怕的是“以为自己写对了”。调试平衡树最有效的手段，不是断点跟代码，而是写一个验证函数，断言的性质不满足就立刻失败。

AVL 的验证函数是这样：

bool verifyAVL(AVLNode* node) { if (!node) return true; int bf = getBalance(node); if (abs(bf) > 1) return false; if (getHeight(node) != max(getHeight(node->left), getHeight(node->right)) + 1) return false; if (node->left && node->left->key >= node->key) return false; if (node->right && node->right->key <= node->key) return false; return verifyAVL(node->left) && verifyAVL(node->right); }

红黑树的验证要更麻烦一些，需要检查五条性质。下面这个函数返回路径上的黑色节点数，如果某个性质被破坏就返回 -1：

int verifyRB(RBNode* node) { if (!node) return 1; // NIL 是黑色，黑高至少为 1 if (node->color == RED) { if (node->left && node->left->color == RED) return -1; if (node->right && node->right->color == RED) return -1; } int leftBH = verifyRB(node->left); int rightBH = verifyRB(node->right); if (leftBH == -1 || rightBH == -1) return -1; if (leftBH != rightBH) return -1; return leftBH + (node->color == BLACK ? 1 : 0); } bool isRBTree(RBNode* root) { if (!root) return true; if (root->color != BLACK) return false; return verifyRB(root) != -1; }

注意verifyRB对空节点返回的是 1，不是 0，因为在我的约定里 NIL 节点视为黑色且黑高为 1。如果你采用另一种约定（空节点黑高为 0），那叶子节点的黑高计数会整体少 1，但只要全局一致就没问题。不要混用两套约定，不然写断言时永远会对不上。

我把这一套验证函数放在每次插入、删除之后调用，所有随机测试数据都跑了一遍，它可以立刻暴露旋转时漏更新高度、颜色没变、或者是镜像写反的问题。

5. 模拟实现中的常见翻车现场

5.1 我在写旋转时踩过的三个坑

第一个坑：AVL 里更新高度的顺序。旋转函数中，先更新两棵子树的高度，然后再更新新的根节点高度。顺序写反的话，旋转后根节点的高度会算成旧的子树高度，导致下一次平衡判断直接出错。最好写成先更新子节点、再更新父节点，并且把更新高度的逻辑独立成updateHeight而不是内联。

第二个坑：红黑树旋转后忘了维护根指针。当旋转的节点没有父节点时，它就是根，旋转结束后 root 必须指向新的节点。这个分支我一开始没写，结果旋转后整棵树从局部看是对的，但根部丢失，程序一跑就直接段错误。标准实现里那个if (!x->parent) root = y;一行都不能省。

第三个坑：递归里使用局部引用变量保存 node 地址。AVL 插入用递归返回新根是安全的，因为每个调用点都会接收返回值。但如果有人试图用node的引用在整个函数里来回传，一旦发生旋转，局部引用指向的地址变了，后面的代码操作的就是废弃节点。我在学习期间曾经为了“优化”把返回值改成引用，结果很快意识到这个思路在旋转发生时会自毁。

5.2 什么时候要用哨兵节点

红黑树实现里，NIL 叶子节点是个很微妙的设计。有的人用nullptr直接当叶子，有的人建一个静态的黑色节点当哨兵。STL 用的就是哨兵节点，好处是删除修复中的“兄弟节点”永远不为空，你能少写一半的空指针判断。

用nullptr的好处是内存分配简单，代码阅读直观；坏处是写删除修复时要时刻判断sibling == nullptr的情况，一旦漏判就会出现空指针访问。我的建议是学习阶段先用nullptr，把旋转和插入修复跑通；写删除修复时再考虑引入哨兵。不要一开始就用哨兵，否则你分不清“逻辑上该判断空指针”和“语法上哨兵避免了判断”到底是怎么回事。

5.3 调试平衡树的三个实用技巧

第一个技巧：小数据量暴力验证。先用 1 到 100 的所有排列顺序去插入，或者随机生成 1000 个数，每次都调用验证函数检查性质。数据量小才能让你在断言失败时快速手推那几条路径。

第二个技巧：把树的结构打印出来。不要只打印 key，要把平衡因子或颜色一起印出来。我在调试红黑树时专门写了一个带缩进的树形打印函数，红黑树还会标上R/B后缀，一眼就能看出连续红节点位置。这是追踪修复过程最直接的手段。

第三个技巧：每次旋转都留日志。旋转是树形结构的关键转折点，在旋转函数里打一条日志，记录旋转节点、旋转方向和前后状态。删除修复出问题时，配合日志能快速定位到第几步的镜像写错了。

两个树完整模拟实现之后，我觉得最大的收获不是背会了旋转代码，而是理解了“平衡”的本质：不是某一瞬间的巧合，而是一套在任何操作之后都能自我修复的机制。AVL 用高度差驱动旋转，红黑树用颜色驱动变色和旋转，它们都是在 BST 的骨架上加了“后悔药”，每次操作结束之后都能把自己拉回安全状态。我自己在写完两棵树之后，又顺手用红黑树的五条性质去验证了一遍标准库 map 的实现，发现它比教科书版本多了很多针对缓存命中和内存池的优化，但核心逻辑和这篇笔记里的插入修复基本一致。