5.1 二叉搜索树与平衡

普通二叉树没有规定关键字应放在哪里，查找一个值往往要遍历整棵树。二叉搜索树把“比较结果”变成方向：小值向左，大值向右；AVL 树再通过旋转控制高度，让这种方向选择始终有效。

学习目标

准确陈述二叉搜索树的不变量，并完成查找、插入、删除；
区分前驱、后继与父子关系，解释删除双孩子节点的替换策略；
用树高 $h$ 推导 BST 操作复杂度，并构造退化反例；
理解旋转只改变局部形态、不改变中序次序；
识别 AVL 的 LL、RR、LR、RL 四类失衡，完成插入和删除后的再平衡；
阅读并解释一份维护高度与所有权的 C++ AVL 核心实现。

5.1.1 二叉搜索树：定义、有序性质、查找、插入、删除（含前驱/后继）

定义与有序不变量

定义 · 二叉搜索树

一棵二叉搜索树（Binary Search Tree，BST）或者为空，或者对每个节点 x 都满足：

x 左子树中的每个关键字都小于 x.key；
x 右子树中的每个关键字都大于 x.key；
左右子树本身也都是二叉搜索树。

本页采用“关键字互异”的接口约定。若业务允许重复键，必须额外规定重复值统一放一侧，或在节点中维护计数；不能让不同操作各用一套规则。

性质 · 中序序列有序

对关键字互异的 BST 做中序遍历，得到严格递增序列。反过来，若一次结构修改破坏了中序递增性，它就不再是合法 BST。

例如，把 8, 3, 10, 1, 6, 14, 4, 7, 13 依次插入空树：

中序遍历为 1, 3, 4, 6, 7, 8, 10, 13, 14。

查找与插入

查找从根开始：目标小于当前关键字就进入左子树，大于就进入右子树，相等则成功。插入执行同样的比较，直到遇到空链接，再把新节点接到那里。沿途不需要访问另一侧子树。

cpp

struct Node {
    int key;
    Node* left{};
    Node* right{};
};

// 查找：沿 BST 比较规则向下走，找到返回节点指针，找不到返回 nullptr
Node* search(Node* root, int key) {
    while (root != nullptr && root->key != key) {
        // 当前节点不是目标，根据大小关系选择左/右子树继续
        root = key < root->key ? root->left : root->right;
    }
    return root;  // 命中返回该节点，走到空链接则查找失败
}

// 插入：先走查找路径，在第一个空链接处创建新节点
// 使用 Node** 统一处理"接在根上还是接在孩子上"
bool insert(Node*& root, int key) {
    Node** link = &root;           // link 始终指向"下一个该被填充的指针槽位"
    while (*link != nullptr) {
        if (key == (*link)->key) {
            return false;          // 本实现拒绝重复键
        }
        // 决定往左子树还是右子树走，link 更新为对应指针的地址
        link = key < (*link)->key ? &(*link)->left : &(*link)->right;
    }
    *link = new Node{key};         // 在空链接处接入新节点
    return true;
}

bst-search-insert.cpp

Node** link 指向“将被更新的指针槽位”，因此插入根节点和插入普通孩子可以使用同一段逻辑。真实工程还需要用 RAII 管理内存；这里先突出查找路径。

前驱与后继

对某个已存在节点 x：

前驱是严格小于 x.key 的最大关键字；
后继是严格大于 x.key 的最小关键字。

若 x 有左子树，前驱就是左子树中最靠右的节点；若有右子树，后继就是右子树中最靠左的节点。没有相应子树时，需要沿父链接向上，找到第一次从右孩子方向（求前驱）或左孩子方向（求后继）进入的祖先。若节点不保存父指针，也可以从根重新搜索并沿途记录候选者。

在上图中，8 的前驱是 7，后继是 10；10 没有左子树，它的前驱是向上找到的祖先 8。

删除的三种结构情况

删除必须同时满足两个目标：目标关键字消失，剩余节点的中序次序不变。

叶节点：直接断开。
只有一个孩子：用唯一孩子顶替目标节点的位置。
有两个孩子：用中序后继（右子树最小值）或前驱（左子树最大值）替换目标关键字，再删除那个至多只有一个孩子的替身节点。

示例 · 删除双孩子节点 3

上图中 3 的后继是 4。先把节点 3 的关键字改为 4，再删除原来位于 6 左侧的节点 4。替换前后的中序序列只少了 3，其他相对顺序不变。

易错点 · 复制关键字不等于复制整棵子树

删除双孩子节点时只把前驱或后继的“记录内容”移到目标位置，再在原位置删除替身。直接把替身节点指针覆盖到目标位置，若没有同时重接原左右子树，很容易丢失节点、制造重复所有权或破坏链接。

C++：用唯一所有权实现删除

下面的删除函数使用 std::unique_ptr 表达“父节点独占孩子”的所有权。返回值始终是删除后子树的新根，因此叶删除、单孩子顶替和根节点变化都能统一处理。

cpp

#include <memory>

struct BstNode {
    explicit BstNode(int value) : key(value) {}
    int key;
    std::unique_ptr<BstNode> left;
    std::unique_ptr<BstNode> right;
};

// 找到以 root 为根的子树中的最小关键字节点（最左节点）
const BstNode& minimum(const BstNode& root) {
    const BstNode* current = &root;
    while (current->left) {
        current = current->left.get();  // 一路向左，直到没有左孩子
    }
    return *current;
}

// 删除：返回删除后子树的新根，用 unique_ptr 自动管理内存
std::unique_ptr<BstNode> erase(std::unique_ptr<BstNode> root, int key) {
    if (!root) {
        return nullptr;  // 走到空链接，目标不存在
    }
    if (key < root->key) {
        // 目标在左子树，递归删除后更新左链接
        root->left = erase(std::move(root->left), key);
    } else if (key > root->key) {
        // 目标在右子树，递归删除后更新右链接
        root->right = erase(std::move(root->right), key);
    } else {
        // 找到目标节点，分三种结构情况处理
        if (!root->left) {
            // 情况 1/2：没有左孩子，用右孩子顶替（右孩子可为空）
            return std::move(root->right);
        }
        if (!root->right) {
            // 情况 2：没有右孩子，用左孩子顶替
            return std::move(root->left);
        }
        // 情况 3：有两个孩子，用右子树最小值（后继）替换当前关键字
        root->key = minimum(*root->right).key;
        // 再递归删除右子树中那个已经被"复制"上来的后继节点
        root->right = erase(std::move(root->right), root->key);
    }
    return root;
}

bst-erase.cpp

5.1.2 二叉搜索树的复杂度与退化【C/C++】

所有核心操作都受树高控制

设树高按边数记为 $h$ 。查找、插入和删除只沿一条根到节点的路径移动，删除双孩子节点时再沿一条子树边界寻找前驱或后继，因此：

复杂度 · 普通 BST

操作	时间	额外空间
查找、插入、删除	$O (h)$	迭代为 $O (1)$ ；递归为 $O (h)$
找最小/最大、前驱/后继	$O (h)$	同上
完整中序遍历	$Θ (n)$	递归栈 $O (h)$

若树形接近平衡， $h = Θ (\log n)$ ；若退化成链， $h = n - 1$ ，单次操作变为 $Θ (n)$ 。因此“BST 查找是 $O (\log n)$ ”只有在树高受控或随机形态假设成立时才准确。

退化怎样发生

把 1, 2, 3, 4, 5 按递增顺序插入空 BST：

这棵树的结构与单链表相同。查找 5 要比较 5 次；若继续插入递增数据，第 $n$ 次插入也要走过接近 $n$ 个节点。

反例 · 有序不等于高效

上面的退化树仍完全满足 BST 有序性质，中序序列也正确。问题不是“树错了”，而是有序不变量没有对高度作任何保证。仅检查中序递增，无法证明性能达标。

交互式演示 · BST 操作

下面的演示可以亲手体验 BST 的插入、查找与删除。尝试依次插入 1, 2, 3, 4, 5 观察退化链，再换一组平衡序列如 8, 3, 10, 1, 6, 14 对比树高；也可以选中节点后点击删除，观察三种结构情况的处理。

观察重点

用递增序列插入，看树如何退化成链；
用同一组关键字的不同插入顺序，对比树高与查找路径长度；
选中节点删除，观察叶节点、单孩子、双孩子三种情况的处理逻辑。

递归深度仍为 $O (h)$ 。若普通 BST 可能接收恶意有序输入，退化深度还会带来调用栈风险；这正是平衡树要解决的问题。

5.1.3 对于旋转和非旋转的讨论

笔者认为，常见平衡树分别通过旋转和非旋转两种方式去实现平衡。大学数据结构相关教材中只提及了几类旋转平衡树，故笔者在此处想拓展一些非旋转平衡树，以起到抛砖引玉之效。

旋转——用局部旋转修复失衡。 AVL、Splay、Treap 以及红黑树都属于这一类平衡树（AVL和红黑树多见于各种大学教材）。它们的共同点是通过某种约定判断某个子树"歪了"的时候，就通过左旋或右旋把重心拉回来。旋转的优势在于只改常数条链接， $O (1)$ 就能完成一次结构调整。OI-Wiki 上有对旋转的经典总结是："旋转操作是多数平衡树能够维持平衡的关键，它能在不改变一棵合法 BST 中序遍历结果的情况下改变局部节点的深度。" [^oiwiki-rotate]

（旋转平衡树如果不够熟悉，写的时候可能会有绕晕的风险。

非旋——绕开旋转，用别的方式保持平衡。 这一类平衡树在算法竞赛中反而更受欢迎，原因很简单：好写、好调、不容易写挂。

FHQ Treap（非旋 Treap）：完全取消旋转，只用**分裂（Split）和合并（Merge）**两个操作。按关键字把树劈成两半，递归处理完再粘回去。FHQ Treap 在 OI 中普及的一个很重要原因是它天然支持区间操作，这是旋转很难优雅做到的。
替罪羊树（Scapegoat Tree）：很暴力，不过实际上很优雅，采用暴力重建的方法来代替旋转。一旦某个子树的节点数超过整棵树的 $α$ 倍（通常取 0.7 或 0.8），就拍扁重建——把子树里的所有节点拿出来排好序，重新建一棵完全平衡的 BST。替罪羊树的均摊复杂度仍是 $O (\log n)$ ，单次重建最坏 $O (n)$ ，但触发频率被控制得很低，实际运行起来相当快。

此处笔者只是从算法竞赛角度略作拓展，大学课程中还是以 AVL 和红黑树为重。

5.1.4 平衡的思想与旋转操作

平衡不是让两边节点数完全相等

平衡策略的目标是控制树高，使根到任意叶的路径不会过长。不同平衡树使用不同约束：AVL 限制每个节点的左右子树高度差，红黑树限制颜色路径，B 树限制每个节点的关键字数量。这里先看 AVL 的局部修复工具——旋转。

定义 · 旋转

旋转是在保持 BST 中序次序不变的前提下，重新连接一个节点、它的孩子和中间子树的局部操作。一次旋转只改常数个链接，时间为 $Θ (1)$ 。

右旋前后：

旋转前后的中序序列都是 A, x, B, y, C。左旋是完全对称的操作：当 y 的右孩子 x 上升时，x 的左子树成为 y 的右子树。

性质 · 为什么旋转保持有序

旋转前有 A < x < B < y < C。旋转只重新分配 x、y 与中间子树 B 的父子关系，没有改变这五个区间的相对顺序，因此中序序列不变。

每次旋转后必须自底向上更新受影响节点的高度。右旋时先更新下降的 y，再更新上升的 x；顺序反过来会读取旧高度。

5.1.5 AVL 树：平衡因子、四种失衡与单/双旋转、插入、删除【进阶】

平衡因子与 AVL 不变量

定义 · AVL 树

AVL 树是满足 BST 有序性质，并且每个节点 v 都满足

BF (v) = height (v . l e f t) - height (v . r i g h t) \in {- 1, 0, 1}

的二叉搜索树。本页约定空树高度为 $- 1$ ，叶节点高度为 $0$ 。

插入或删除只会改变搜索路径上节点的高度。回溯时找到 |BF| > 1 的节点，再根据“重的一侧内部又偏向哪边”选择旋转。

四种失衡

失衡类型	最低新节点/重路径	局部特征	修复
LL	左孩子的左侧	`BF(root)=2` 且 `BF(left)>=0`	对根右旋
RR	右孩子的右侧	`BF(root)=-2` 且 `BF(right)<=0`	对根左旋
LR	左孩子的右侧	`BF(root)=2` 且 `BF(left)<0`	先左旋左孩子，再右旋根
RL	右孩子的左侧	`BF(root)=-2` 且 `BF(right)>0`	先右旋右孩子，再左旋根

四种失衡的重路径形态如下。把从失衡根出发的两段方向连起来读，就是类型名称：

示例 · LR 双旋

依次插入 30, 10, 20：30 左侧过高，但新节点 20 位于左孩子 10 的右侧，属于 LR 型。单次右旋无法修复——20 会从 10 的右侧原样搬到 30 的左侧，重路径依然是折线。正确做法是先把折线“掰直”，再整体旋转：

第 ② 步之后重路径变成 30 → 20 → 10 的连续向左，正是 LL 型，因此第 ③ 步用一次右旋即可收尾。最终根为 20，左右孩子分别是 10 和 30，三个节点的 BF 全为 0。

插入后的再平衡

AVL 插入先按 BST 规则把新节点接到叶位置，再沿递归返回路径更新高度与再平衡。对一次插入，从最低失衡点完成恰当旋转后，该局部子树高度恢复到插入前水平；继续向上仍要更新高度，但不会再产生新的插入失衡。

删除后的再平衡

AVL 删除先执行 BST 删除。与插入不同，删除可能让子树高度减少；一次旋转后，修复后的子树高度还可能继续下降，因此必须一路检查到根，不能修复第一个失衡点就停止。

删除判断还要允许重孩子的平衡因子为 0。例如根左侧过高且左孩子 BF=0 时，仍使用 LL 型右旋；若机械套用“新节点插入方向”，会漏掉删除特有情形。

易错点 · 类型名称描述路径，不描述旋转方向

LL 失衡使用一次右旋，RR 失衡使用一次左旋。名称表示重路径从失衡根出发走向哪两个方向，不是要执行的旋转方向。

5.1.6 AVL 树的实现与复杂度【C/C++】

下面的 C++ 核心实现把高度维护、单旋和双旋统一放在 rebalance 中。insert 与 erase 只负责 BST 语义，返回前都经过同一再平衡出口。

cpp

#include <algorithm>
#include <memory>

// AVL 节点：比普通 BST 多一个 height 字段，用于判断失衡
struct AvlNode {
    explicit AvlNode(int value) : key(value) {}
    int key;
    int height{0};                       // 叶节点高度为 0
    std::unique_ptr<AvlNode> left;
    std::unique_ptr<AvlNode> right;
};

// 辅助函数：空树高度为 -1，否则取节点记录的高度
int height(const std::unique_ptr<AvlNode>& node) {
    return node ? node->height : -1;
}

// 根据左右孩子高度重新计算当前节点高度
void update(AvlNode& node) {
    node.height = 1 + std::max(height(node.left), height(node.right));
}

// 平衡因子 = 左子树高度 - 右子树高度
// AVL 要求平衡因子在 {-1, 0, 1} 范围内
int balanceFactor(const AvlNode& node) {
    return height(node.left) - height(node.right);
}

// 右旋：pivot 是当前根的左孩子，右旋后 pivot 上升为新根
// 中间子树 B 从 pivot 的右侧改挂到原根的左侧
std::unique_ptr<AvlNode> rotateRight(std::unique_ptr<AvlNode> root) {
    auto pivot = std::move(root->left);     // ① 保存左孩子 pivot
    root->left = std::move(pivot->right);   // ② pivot 的右子树变成 root 的左子树
    update(*root);                          // ③ 先更新下降节点 root 的高度
    pivot->right = std::move(root);         // ④ root 成为 pivot 的右孩子
    update(*pivot);                         // ⑤ 再更新上升节点 pivot 的高度
    return pivot;                           // ⑥ 返回新根
}

// 左旋：与右旋完全对称
std::unique_ptr<AvlNode> rotateLeft(std::unique_ptr<AvlNode> root) {
    auto pivot = std::move(root->right);
    root->right = std::move(pivot->left);
    update(*root);
    pivot->left = std::move(root);
    update(*pivot);
    return pivot;
}

// 再平衡：根据平衡因子判断失衡类型，选择单旋或双旋
std::unique_ptr<AvlNode> rebalance(std::unique_ptr<AvlNode> root) {
    update(*root);                          // 先更新当前节点高度
    if (balanceFactor(*root) > 1) {         // 左子树过高
        if (balanceFactor(*root->left) < 0) {           // 左孩子右偏 → LR
            root->left = rotateLeft(std::move(root->left)); // 先左旋左孩子
        }
        return rotateRight(std::move(root));             // LL（或 LR 调整后）右旋
    }
    if (balanceFactor(*root) < -1) {        // 右子树过高
        if (balanceFactor(*root->right) > 0) {           // 右孩子左偏 → RL
            root->right = rotateRight(std::move(root->right)); // 先右旋右孩子
        }
        return rotateLeft(std::move(root));              // RR（或 RL 调整后）左旋
    }
    return root;                            // 平衡，无需旋转
}

// AVL 插入：先按 BST 规则插入，返回时沿途再平衡
std::unique_ptr<AvlNode> insert(std::unique_ptr<AvlNode> root, int key) {
    if (!root) {
        return std::make_unique<AvlNode>(key);  // 空位置，创建新节点
    }
    if (key < root->key) {
        root->left = insert(std::move(root->left), key);   // 递归插入左子树
    } else if (key > root->key) {
        root->right = insert(std::move(root->right), key); // 递归插入右子树
    } else {
        return root;                                    // 拒绝重复键
    }
    return rebalance(std::move(root));                  // 回溯时再平衡
}

// 找子树最小值（最左节点）
const AvlNode& minimum(const AvlNode& root) {
    const AvlNode* current = &root;
    while (current->left) current = current->left.get();
    return *current;
}

// AVL 删除：先按 BST 规则删除，返回时沿途再平衡
std::unique_ptr<AvlNode> erase(std::unique_ptr<AvlNode> root, int key) {
    if (!root) return nullptr;              // 空树，目标不存在
    if (key < root->key) {
        root->left = erase(std::move(root->left), key);    // 递归删除左子树
    } else if (key > root->key) {
        root->right = erase(std::move(root->right), key);  // 递归删除右子树
    } else {
        // 找到目标，分三种结构情况
        if (!root->left) return std::move(root->right);    // 用右孩子顶替
        if (!root->right) return std::move(root->left);    // 用左孩子顶替
        // 双孩子：用后继替换关键字，再递归删除后继
        root->key = minimum(*root->right).key;
        root->right = erase(std::move(root->right), root->key);
    }
    return rebalance(std::move(root));      // 回溯时再平衡（删除可能一路传到根）
}

avl-tree.cpp

交互式演示 · AVL 树平衡过程

下面的演示可以观察 AVL 树的插入与再平衡过程。依次插入 30, 10, 20 体验 LR 双旋，或插入递增序列观察旋转如何阻止退化。

观察重点

依次插入 30, 10, 20，观察 LR 双旋的完整过程；
插入递增序列，观察 AVL 如何通过单旋阻止退化成链；
注意每次插入后节点高度的更新和平衡因子的变化。

复杂度 · AVL 操作

AVL 树的最少节点数满足类似斐波那契的递推，因此高度为 $O (\log n)$ 。查找、插入、删除都只访问一条根到叶路径：

查找： $O (\log n)$ ；
插入： $O (\log n)$ ，旋转次数为常数级；
删除： $O (\log n)$ ，可能在多个祖先处旋转；
单次旋转： $Θ (1)$ ；
递归辅助空间： $O (\log n)$ ；节点与高度字段总空间为 $O (n)$ 。

实现自检不变量

每次公开操作后至少验证：

中序序列严格递增；
每个节点保存的高度等于 1 + max(left, right)；
每个节点 abs(balanceFactor) <= 1；
节点数与成功插入、删除记录一致；
空树、单节点、根删除、连续递增插入和交替插删均不泄漏或重复拥有节点。

5.1.7 红黑树

AVL 严格限制左右高度差。红黑树使用较宽松的颜色规则限制最长路径，使更新时通常需要更少旋转。

把所有空孩子视为黑色 NIL 叶结点。一棵红黑树满足：

每个结点非红即黑；
根结点是黑色；
所有 NIL 叶结点是黑色；
红结点的两个孩子都是黑色，不能出现连续红结点；
从任一结点到其所有后代 NIL 叶结点的路径，都包含相同数量的黑结点。

从某结点到后代 NIL 路径上的黑结点数称为黑高。性质 4 保证最长路径至多在每两个黑结点之间插入一个红结点，因此最长路径不会超过最短路径的两倍。

定义 · 黑高与红黑树

一个结点的黑高是从该结点到其所有后代 NIL 叶的路径上经过的黑结点数（不含该结点本身）。红黑树通过"所有路径黑高相同"（性质 5）限制树高，又通过"无连续红结点"（性质 4）限制最长与最短路径之比。

含 $n$ 个内部结点的红黑树高度满足：

h \leq 2 \log_{2} (n + 1) .

所以查找、插入、删除的最坏时间都是 $O (\log n)$ 。

定理 · 红黑树高度上界

性质 4 使最长路径上最多每两个黑结点夹一个红结点，故最长路径 ≤ $2 \times$ 最短路径。又由性质 5 所有路径黑高相同为 $b h$ ，最短路径至少 $b h$ 个黑结点。一棵黑高为 $b h$ 的红黑树至少含 $2^{b h} - 1$ 个内部结点，从而 $b h \leq \log_{2} (n + 1)$ ，所以 $h \leq 2 b h \leq 2 \log_{2} (n + 1)$ 。

红黑树插入的修复思路

新结点按 BST 规则插入并染红。染红不会改变任一路径的黑高；唯一可能破坏的是"红结点不能有红孩子"。若父结点也是红色，观察叔叔结点：

叔叔为红色：把父和叔染黑、祖父染红，再从祖父继续向上检查；
叔叔为黑色，路径成折线：先旋转父结点，把折线变成直线；
叔叔为黑色，路径成直线：旋转祖父，并交换父与祖父的颜色。

最后把根染黑。修复可能多次变色，但插入最多做常数次结构旋转。

直觉 · 为什么新结点染红

插入新结点若染黑，会让经过它那条路径的黑高比别的路径多 1，立刻破坏性质 5，而且这个破坏很难局部修复。染红则只可能破坏性质 4（父也是红），而"连续红"是可以通过变色和旋转在局部消除的。因此染红把问题变成一个更可控的局部约束。

红黑树删除的修复思路

删除红结点不会改变黑高；删除有红孩子的黑结点时，可让红孩子顶替并染黑。困难发生在删除黑色叶位置：某些路径会少一个黑结点，可把这个缺额理解为"额外一重黑色"。

修复时根据兄弟颜色、兄弟孩子颜色决定变色和旋转，把黑色缺额向上移动或在局部消除。完整代码分支较多，但每一步都服务于两件事：恢复相同黑高，避免连续红结点。

不要用 AVL 的高度差判断红黑树

红黑树不要求任意结点左右子树高度差不超过 1。它只通过颜色和黑高限制整体最长路径，因此可能比同关键字集合的 AVL 更高。

完整实现：红黑树（C++）

下面给出一份维护颜色、带哨兵 NIL 的红黑树核心实现。插入和删除的修复逻辑严格按照前文所述的变色与旋转策略实现。

cpp

#include <memory>

enum class Color { RED, BLACK };

struct RbNode {
    int key;
    Color color{Color::RED};            // 新节点默认染红
    std::shared_ptr<RbNode> left;
    std::shared_ptr<RbNode> right;
    std::weak_ptr<RbNode> parent;       // 需要父指针做向上修复
};

using NodePtr = std::shared_ptr<RbNode>;

// ---------- 辅助旋转 ----------
void leftRotate(NodePtr& root, NodePtr x) {
    NodePtr y = x->right;               // y 是 x 的右孩子
    x->right = y->left;                 // y 的左子树变成 x 的右子树
    if (y->left) {
        y->left->parent = x;
    }
    y->parent = x->parent;              // y 接替 x 的位置
    if (!x->parent.lock()) {
        root = y;                       // x 原来是根
    } else if (x == x->parent.lock()->left) {
        x->parent.lock()->left = y;
    } else {
        x->parent.lock()->right = y;
    }
    y->left = x;
    x->parent = y;
}

void rightRotate(NodePtr& root, NodePtr x) {
    NodePtr y = x->left;
    x->left = y->right;
    if (y->right) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (!x->parent.lock()) {
        root = y;
    } else if (x == x->parent.lock()->right) {
        x->parent.lock()->right = y;
    } else {
        x->parent.lock()->left = y;
    }
    y->right = x;
    x->parent = y;
}

// ---------- 插入修复 ----------
void insertFixup(NodePtr& root, NodePtr z) {
    // 只要父节点是红色，就违反了"无连续红节点"的性质
    while (z->parent.lock() && z->parent.lock()->color == Color::RED) {
        NodePtr p = z->parent.lock();
        NodePtr g = p->parent.lock();   // 祖父节点
        if (p == g->left) {             // 父节点是左孩子
            NodePtr u = g->right;       // 叔叔节点
            if (u && u->color == Color::RED) {
                // 情况 1：叔叔为红，变色后向上继续检查
                p->color = Color::BLACK;
                u->color = Color::BLACK;
                g->color = Color::RED;
                z = g;
            } else {
                // 叔叔为黑
                if (z == p->right) {
                    // 情况 2：折线，先左旋父节点拉成直线
                    z = p;
                    leftRotate(root, z);
                    p = z->parent.lock();
                    g = p->parent.lock();
                }
                // 情况 3：直线，右旋祖父并变色
                p->color = Color::BLACK;
                g->color = Color::RED;
                rightRotate(root, g);
            }
        } else {
            // 对称情况：父节点是右孩子
            NodePtr u = g->left;
            if (u && u->color == Color::RED) {
                p->color = Color::BLACK;
                u->color = Color::BLACK;
                g->color = Color::RED;
                z = g;
            } else {
                if (z == p->left) {
                    z = p;
                    rightRotate(root, z);
                    p = z->parent.lock();
                    g = p->parent.lock();
                }
                p->color = Color::BLACK;
                g->color = Color::RED;
                leftRotate(root, g);
            }
        }
    }
    root->color = Color::BLACK;         // 根始终为黑
}

// ---------- 公开插入接口 ----------
NodePtr rbInsert(NodePtr root, int key) {
    NodePtr z = std::make_shared<RbNode>();
    z->key = key;

    NodePtr y;                          // 追踪父节点位置
    NodePtr x = root;
    while (x) {
        y = x;
        if (key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (!y) {
        root = z;                       // 空树，z 成为根
    } else if (key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }

    insertFixup(root, z);
    return root;
}

red-black-tree.cpp

红黑树实现要点

新节点默认染红，这样只可能破坏"无连续红节点"的性质，而不会破坏所有路径黑高相同的性质；
修复时始终关注叔叔节点的颜色：叔叔为红则变色上移，叔叔为黑则通过旋转+变色在局部解决；
左旋和右旋的实现与 AVL 基本相同，只是额外维护了 parent 指针；
删除修复比插入更复杂，核心思想是把"黑节点 deficit"（双重黑）向上传递或在局部消除。

配套 Lab

实验	练习内容
BST 插入与查找	沿比较方向下降，在空链接处接入新节点
BST 删除	三种结构情况，尤其是双孩子节点的替身选择
验证 BST 先序序列	用区间约束判断序列能否还原为合法 BST
BST 第 k 小元素	利用中序有序性，避免全量排序
AVL 插入与平衡	四类失衡的识别与单/双旋转实现
将二叉搜索树变平衡	中序遍历还原有序序列，再二分建树使高度最小
祭坛三元组	有序序列上枚举 + 二分查找统计方案数

小结与自测

BST 用全序关系缩小查找范围，但性能仍由树高决定；AVL 在每次更新后用局部旋转恢复高度约束。旋转之所以安全，是因为它保持中序次序；旋转之所以高效，是因为只修改常数个链接。

在示例 BST 中分别求 6 的前驱和后继；若删除 6，可选哪个节点替换？
为什么递增插入得到的树仍是合法 BST，却不能保证 $O (\log n)$ 查找？
依次插入 50, 30, 40 会产生哪类 AVL 失衡？画出两次旋转。
为什么 AVL 删除可能一路向根继续旋转，而插入通常只需修复最低失衡点？
若把高度约定改为“空树 0、叶节点 1”，哪些代码和公式要改，哪些判断不变？

查看自测答案

示例 BST 的中序序列是 1, 3, 4, 6, 7, 8, 10, 13, 14。6 的前驱是左子树中的最大值 4，后继是右子树中的最小值 7。删除 6 时它有两个孩子，用前驱 4 或后继 7 顶替都可以：这两个值恰好是中序序列中 6 的紧邻元素，用它们替换不会破坏中序递增性。
递增插入时每个新键都大于已有全部键，因而一路走右链接，最终形成只有右孩子的链。它仍满足“左子树 < 根 < 右子树”（左子树全为空，条件平凡成立），中序序列也正确，所以是合法 BST。但 BST 的有序不变量只约束顺序，对高度不作任何保证；此时树高为 $n - 1$ ，查找退化为 $O (n)$ 。这正是需要额外平衡约束的原因。
依次插入后，50 为根、30 为其左孩子、40 为 30 的右孩子。节点 50 的 $B F = h (左) - h (右) = 1 - (- 1) = 2$ ，失衡且“左子树重、左子树内部右偏”，属于 LR 型，需要两次旋转：
- 第 ① 步，对左孩子 30 左旋，得到 50 → 40 → 30 的连续向左路径，问题转化为 LL 型；
- 第 ② 步，对失衡点 50 右旋，40 上升为根，30 与 50 成为它的左右孩子。最终形态为根 40、左 30、右 50，高度从 2 降为 1。
关键差别在于修复后子树的高度是否回到原状。插入时，从最低失衡点完成恰当旋转后，该局部子树的高度恢复到插入前的水平，因此所有祖先的平衡因子都不再改变，一次旋转即可收工。删除则可能让子树高度减少 1，旋转修复后高度仍可能比原来低，于是父节点的平衡因子随之变化并可能产生新的失衡，必须一路检查到根。
需要改的是基准值，不需要改的是相对关系：
- 要改：空链接的哨兵返回值由 $- 1$ 改为 $0$ （height() 中的 : -1）；新节点的初值 height{0} 改为 1；所有把高度数值与节点数直接挂钩的公式整体平移 1。
- 不变：update() 中的 1 + max(left, right) 递推形式；balanceFactor() 及其 |BF| > 1 的判定——因为平衡因子是两个高度的差，两者同时加 1 后差值不变；四种失衡类型的判别与旋转代码； $O (\log n)$ 的渐近结论。

下一节进入5.2 堆与优先队列：它不维护完整排序，而是用更弱的局部偏序换取高效的最高优先级访问。

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

学习目标 ​

5.1.1 二叉搜索树：定义、有序性质、查找、插入、删除（含前驱/后继） ​

定义与有序不变量 ​

查找与插入 ​

前驱与后继 ​

删除的三种结构情况 ​

C++：用唯一所有权实现删除 ​

5.1.2 二叉搜索树的复杂度与退化【C/C++】 ​

所有核心操作都受树高控制 ​

退化怎样发生 ​

交互式演示 · BST 操作 ​

5.1.3 对于旋转和非旋转的讨论 ​

5.1.4 平衡的思想与旋转操作 ​

平衡不是让两边节点数完全相等 ​

5.1.5 AVL 树：平衡因子、四种失衡与单/双旋转、插入、删除【进阶】 ​

平衡因子与 AVL 不变量 ​

四种失衡 ​

插入后的再平衡 ​

删除后的再平衡 ​

5.1.6 AVL 树的实现与复杂度【C/C++】 ​

交互式演示 · AVL 树平衡过程 ​

实现自检不变量 ​

5.1.7 红黑树 ​

红黑树插入的修复思路 ​

红黑树删除的修复思路 ​

完整实现：红黑树（C++） ​

配套 Lab ​

小结与自测 ​

学习目标

5.1.1 二叉搜索树：定义、有序性质、查找、插入、删除（含前驱/后继）

定义与有序不变量

查找与插入

前驱与后继

删除的三种结构情况

C++：用唯一所有权实现删除

5.1.2 二叉搜索树的复杂度与退化【C/C++】

所有核心操作都受树高控制

退化怎样发生

交互式演示 · BST 操作

5.1.3 对于旋转和非旋转的讨论

5.1.4 平衡的思想与旋转操作

平衡不是让两边节点数完全相等

5.1.5 AVL 树：平衡因子、四种失衡与单/双旋转、插入、删除【进阶】

平衡因子与 AVL 不变量

四种失衡

插入后的再平衡

删除后的再平衡

5.1.6 AVL 树的实现与复杂度【C/C++】

交互式演示 · AVL 树平衡过程

实现自检不变量

5.1.7 红黑树

红黑树插入的修复思路

红黑树删除的修复思路

完整实现：红黑树（C++）

配套 Lab

小结与自测