Lecture 26：树形查找

树形查找把“有序”组织成层次结构：二叉排序树用大小关系决定向左还是向右；AVL 树用严格高度平衡避免退化；红黑树用较宽松的颜色约束换取更低的动态维护成本。核心判断是：BST 保证查找方向，AVL 与红黑树保证高度量级。

26.1 二叉排序树

26.1.1 定义与中序性质

定义：#二叉排序树 #BST

描述：二叉排序树（Binary Search Tree，BST）是一棵空树，或满足以下性质的二叉树：任一结点的左子树关键字均小于该结点关键字，右子树关键字均大于该结点关键字，左右子树也分别是 BST。

$$ \text{key}(\text{左子树})<\text{key}(\text{根})<\text{key}(\text{右子树}) $$

• 本笔记按“关键字互异”的 408 常规处理。若允许重复关键字，必须额外规定相等键放在哪侧或在结点中计数，不能沿用上式后再随意插入。
• 对 BST 做中序遍历会得到严格递增序列；这是判断一棵树是否满足 BST 关键字次序的直接方法。
• BST 的形状由插入顺序决定。同一批关键字可构成不同形状的 BST，不同插入序列也可能得到同一棵树。

对任一结点，左子树所有关键字都小于它，右子树所有关键字都大于它；该条件必须对子树中的全部结点成立，而不只是比较直接孩子。

26.1.2 查找与插入

查找过程：

typedef struct BSTNode {
    KeyType key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

BSTNode *BST_Search(BSTree T, KeyType key) {
    while (T != NULL && T->key != key) {
        if (key < T->key)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;  // NULL 表示查找失败
}

• 每一层只需一次关键字比较，并根据大小关系排除另一棵子树。
• 非递归查找的额外空间为 $O(1)$；递归写法的调用栈深度为树高 $h$，空间为 $O(h)$。
• 查找失败落到空指针时结束，不能在空指针上继续取 key。

插入过程：

1. 按普通 BST 查找规则向下走，直到遇到空指针。
2. 将新结点作为该空指针位置的叶结点。
3. 若遇到相等关键字，则按本讲约定插入失败。

• 新结点一定插在叶子位置，故不会破坏原有祖先与子树的大小关系。
• 将序列逐个执行插入即可构造 BST；不要把“按数组下标建完全二叉树”的规则套到 BST 上。

bool BST_Insert(BSTree *T, KeyType key) {
    if (*T == NULL) {
        *T = malloc(sizeof(BSTNode));
        if (*T == NULL) return false;
        (*T)->key = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return true;
    }
    if (key == (*T)->key) return false;
    if (key < (*T)->key) return BST_Insert(&(*T)->lchild, key);
    return BST_Insert(&(*T)->rchild, key);
}

void Create_BST(BSTree *T, KeyType keys[], int n) {
    *T = NULL;
    for (int i = 0; i < n; ++i)
        BST_Insert(T, keys[i]);
}

例如依次插入 $50,66,60,26,21,30,70,68$，每个新键都从根开始比较并落到唯一的空指针位置；交换插入次序可能改变树形和 ASL。

26.1.3 删除

定义：#BST删除

描述：删除结点后既要保持连通结构，也要保持左小右大的 BST 性质。按被删结点的孩子数分为三类。

直接前驱与直接后继：

• 直接前驱：被删结点左子树中最右下的结点，即左子树最大关键字。
• 直接后继：被删结点右子树中最左下的结点，即右子树最小关键字。
• 只替换关键字再删除前驱/后继结点，或直接调整指针均可；答题时需交代清楚采取的方式。
• 不能随便选左子树或右子树中的一个结点替代根。只有前驱/后继才能保证替换后两边仍满足大小关系。

删除图中的 $z=50$ 时，可取其右子树最小结点 $p=60$ 作为直接后继：先用 $60$ 替换 $50$，再在原位置删除 $60$。后一步至多属于“叶结点”或“只有一个孩子”的简单情况。

26.1.4 查找效率与 ASL

• 含 $n$ 个结点的 BST，按一次三路关键字比较（小于、等于、大于）计，某次成功查找的比较次数等于目标结点所在层数，最坏为树高 $h$。
• 最理想时树接近完全二叉树：

$$ h_{\min}=\lfloor\log_2n\rfloor+1 $$

此时查找的量级为 $O(\log n)$。

• 最坏时每个结点只有一个孩子，BST 退化为链表，$h=n$，查找、插入和删除都为 $O(n)$。
• 没有给出树形或插入序列的概率模型时，不能笼统断言普通 BST 的“平均复杂度必为 $O(\log n)$”；随机插入等常见模型下才有期望 $O(\log n)$。

成功与失败 ASL：

• 成功查找按内部结点层数统计。图示 8 个关键字的层数分布为 $1,2,4,1$，故：

$$ \begin{aligned} ASL_{\text{成功}} &=\frac{1\times1+2\times2+3\times4+4\times1}{8}\ &=\frac{21}{8}=2.625 \end{aligned} $$

• 含 $n$ 个内部结点的二叉树有 $n+1$ 个空指针位置，每个位置对应一个失败区间。
• 失败结果画成外部结点时，真正发生的关键字比较停在其父结点，所以失败查找长度等于父结点层数；若把根深度记为 $0$，则等于外部结点深度。

图中 9 个失败区间里，7 个需比较 $3$ 次，2 个需比较 $4$ 次。若各失败区间等概率被查找，则：

$$ \begin{aligned} ASL_{\text{失败}} &=\frac{3\times7+4\times2}{9}\ &=\frac{29}{9}\approx3.22 \end{aligned} $$

---

26.2 平衡二叉树（AVL）

26.2.1 定义与高度

定义：#平衡二叉树 #AVL树

描述：AVL 树是一棵 BST，且任一结点左右子树高度之差的绝对值不超过 $1$。

定义结点的平衡因子：

$$ BF= h_{\text{左}}-h_{\text{右}} $$

AVL 树中任一结点都有：

$$ BF\in{-1,0,1} $$

• 它首先是 BST，因此仍保留中序有序和按大小分支的查找性质。
• 它又限制高度差，避免连续插入有序关键字时退化成链表。
• 若规定空树高度为 $0$、单结点树高度为 $1$，高度为 $h$ 的 AVL 树最少结点数满足：

$$ N_0=0,\quad N_1=1,\quad N_h=N_{h-1}+N_{h-2}+1\ (h\ge2) $$

因此 $N_h=F_{h+2}-1$，AVL 树高度为 $O(\log n)$，查找、插入、删除的时间复杂度均为 $O(\log n)$。

图中采用 $BF=h_{\text{左}}-h_{\text{右}}$：左高为正、右高为负。若题目采用相反定义，只是符号相反，树是否平衡与旋转方向不变。

26.2.2 插入后的调整原则

1. 先按 BST 规则插入新结点。
2. 从新结点沿祖先链向上更新平衡因子。
3. 找到第一个满足 $\lvert BF\rvert>1$ 的祖先，称为最小不平衡子树的根。
4. 根据插入路径确定 LL、RR、LR、RL 四种类型并旋转。
5. 旋转后既要恢复平衡，又必须保持 BST 的中序次序不变。

• 对 AVL 插入，调整最小不平衡子树后，该子树高度恢复到插入前，祖先不会再因本次插入失衡，因此一次局部调整即可结束。
• 旋转不是把两个结点机械交换，而是要保留中间子树。例如右旋时，原左孩子的右子树必须接到原根的左侧。

26.2.3 四种旋转

上排是 LL、RR 单旋，下排是 LR、RL 双旋。判断类型只看从最小不平衡根 $A$ 到插入点的前两步方向；旋转后 $A,B,C$ 的中序次序必须保持不变。

LL 右旋的结构：

设 $B$ 为 $A$ 的左孩子，$T_2$ 为 $B$ 的右子树。右旋后 $B$ 成为该子树的新根，$A$ 成为 $B$ 的右孩子，$T_2$ 成为 $A$ 的左子树：

        A                 B
       / \               / \
      B   T4    ->      T1  A
     / \                   / \
    T1 T2                 T2 T4

由于 $T_2$ 的全部关键字大于 $B$ 且小于 $A$，它移动后仍符合 BST 次序。

插入 67 的例子：

新结点 $67$ 插到 $68$ 的左侧后，沿祖先向上第一个失衡结点是 $70$，路径为“左-左”，属于 LL 型；对 $70$ 右单旋后，以 $68$ 为该局部子树的新根，$67<68<70$ 的中序次序不变。

题型：#AVL插入与旋转

第一部分：解题方法

1. 按 BST 比较规则把新关键字插入，不要先凭肉眼猜旋转。
2. 从插入点向上找第一个失衡结点 $A$。
3. 记录从 $A$ 到新结点的前两步方向：左左为 LL，右右为 RR，左右为 LR，右左为 RL。
4. 完成对应旋转后，检查中序遍历仍递增，并检查各结点 $BF\in{-1,0,1}$。

第二部分：易错点

• 失衡类型取决于插入路径，不是单看新结点与根的大小。
• LR、RL 必须双旋；把它们当作单旋会破坏高度平衡或 BST 次序。
• 平衡因子定义为“左高减右高”时，左重为正、右重为负；若题目采用相反定义，符号会反过来，但旋转类型不变。

第三部分：原资料中的 2021 年插入题

原树以 $20$ 为根，左孩子为 $16$；右孩子 $30$ 的左右孩子分别为 $25$、$40$。插入 $23$ 后，它成为 $25$ 的左孩子：

插入前                插入后                右旋 30、左旋 20 后
20                    20                    25
├─L: 16               ├─L: 16               ├─L: 20
└─R: 30               └─R: 30               │   ├─L: 16
    ├─L: 25               ├─L: 25           │   └─R: 23
    └─R: 40               │   └─L: 23       └─R: 30
                          └─R: 40               └─R: 40

沿插入路径向上，第一个失衡结点是 $20$，路径为“右、左”，属于 RL 型。先对 $30$ 右旋，再对 $20$ 左旋；最终根关键字为 $25$（D）。旋转前后的中序序列都为 $16,20,23,25,30,40$。

26.3 AVL 树的删除

26.3.1 删除与回溯调整

AVL 删除先完成普通 BST 删除，再恢复高度平衡：

1. 按 BST 规则找到目标；双孩子结点先用直接前驱或直接后继替换，把问题转化成删除至多有一个孩子的结点。
2. 从实际被删位置向根回溯，更新沿途高度和平衡因子。
3. 若结点 $A$ 出现 $\lvert BF(A)\rvert=2$，选择较高孩子 $B$；再根据 $B$ 的平衡因子决定单旋或双旋。
4. 旋转可能使调整后的子树高度继续减小，因此还要向上检查祖先，直至根或高度不再变化。

采用 $BF=h_{\text{左}}-h_{\text{右}}$ 时：

删除时会出现 $BF(B)=0$，所以判定条件必须包含等号；只背插入路径的“儿子-孙子”口令容易漏掉这个边界。

• 当 $BF(A)=+2, BF(B)=0$ 时仍对 $A$ 右单旋；当 $BF(A)=-2, BF(B)=0$ 时仍对 $A$ 左单旋。
• 这个边界下，旋转后的局部子树高度与删除前相同，故更高祖先不再因本次删除继续失衡，可以停止向上传播；若 $BF(B)\ne0$，旋转后局部高度可能继续降低，仍须检查祖先。

删除使结点 $75$ 左侧高度下降后，$75$ 右重；其较高孩子为 $80$，较高方向继续在右侧，属于 RR 型。

对 $75$ 左单旋后，$80$ 成为局部根，$75$ 与 $90$ 分居左右；随后仍需继续检查更高祖先是否失衡。

26.3.2 插入与删除的关键差别

两种操作的查找、回溯和旋转总时间都是 $O(\log n)$；单次旋转是 $O(1)$，但删除可能执行多次局部旋转。

---

26.4 红黑树基础

26.4.1 为什么还需要红黑树

红黑树（Red-Black Tree）仍是 BST，但它不要求每个结点左右子树高度差不超过 $1$，而是用颜色与黑高约束保证最长路径不会失控。

WARNING · “调整是常数时间”要分清对象 一次旋转或染色是 $O(1)$；红黑树插入最多旋转 $2$ 次，删除修复在常见实现中最多旋转 $3$ 次，但颜色修复可能沿祖先链上传，因此整个插入、删除仍按 $O(\log n)$ 计，不能把完整调整过程写成无条件 $O(1)$。

26.4.2 五条定义性质

本节仍按关键字互异处理；若实现允许重复键，必须固定相等键策略。红黑树满足：

1. 每个内部结点非红即黑。
2. 根结点为黑色。
3. 所有外部空叶结点 NIL 为黑色；NIL 是概念上的哨兵叶，不是普通关键字结点。
4. 红结点的父结点和两个孩子都为黑色，即不存在相邻的两个红色内部结点。
5. 从任一结点 $x$ 到其任一后代 NIL 叶的简单路径，所含黑结点数相同。

口诀可记为：左根右、根叶黑、不红红、黑路同。

IMPORTANT · “黑路同”的方向 比较的是同一结点到各后代 NIL 叶的路径，不是“任意结点到根”的路径，也不是“到任意普通结点”的路径。

一种常见结点定义为：

typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    KeyType key;
    Color color;
    struct RBNode *parent, *left, *right;
} RBNode;

实际实现常让所有空孩子共同指向一个黑色 NIL 哨兵，以统一边界处理。

26.4.3 黑高与高度上界

约定结点 $x$ 的黑高 $bh(x)$ 是从不含 $x$ 开始，到任一后代 NIL 叶的路径上黑结点数量，包含终点 NIL。性质 5 保证它与所选路径无关。

• 黑高为 $b$ 的子树至少含 $2^b-1$ 个内部结点。
• 由于红结点不能相邻，根到叶的任一路径上红结点数不超过黑结点数，因此最长内部路径至多约为最短路径的 $2$ 倍。
• 若有 $n$ 个内部结点，则红黑树高度满足：

$$ h\le2\log_2(n+1) $$

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

---

26.5 红黑树的插入与删除

26.5.1 插入修复

先按 BST 规则把新结点插到 NIL 位置：

• 若新结点成为根，直接染黑。
• 否则先染红。插入红结点不会改变任何路径的黑高；只有父结点也为红色时才违反“不红红”。
• 父结点为黑色时，直接结束。

若父结点为红色，则祖父结点必为黑色。令新结点为 $x$、父为 $p$、祖父为 $g$、叔叔为 $u$：

情况一：红叔叔 - 染色并上移

1. 将 $p,u$ 染黑。
2. 将 $g$ 染红。
3. 令 $x=g$，继续向上检查。
4. 最后强制根结点为黑色。

这一步不旋转，但可能沿祖先链重复，因此不能把完整过程当作 $O(1)$。

情况二：黑叔叔或 NIL - 旋转并染色

外侧型一次旋转，内侧型两次旋转；修复后该局部根为黑色、原祖父为红色，既消除红红冲突，也保持各路径黑高不变。

26.5.2 插入序列例题

依次插入 $17,18,23,34,27,15$：

最终中序序列为 $15,17,18,23,27,34$；所有红结点的孩子均黑，从根到各 NIL 的黑结点数相同。

EXAMPLE · 原稿长序列练习中的重复键边界 原稿另给序列 $20,10,5,30,40,57,3,2,4,35,25,18,22,23,24,19,18$。按本笔记“关键字互异”的约定，最后一个 $18$ 与树中已有 $18$ 重复，必须判定插入失败，不能再把它挂到任一侧。按上述标准插入修复完成前 16 个互异关键字后，可得到下面这棵合法红黑树（B 为黑、R 为红）；中序遍历仍严格递增，任一路径黑高相同。

10B
├─L: 3B
│   ├─L: 2B
│   └─R: 5B
│       └─L: 4R
└─R: 23B
    ├─L: 20R
    │   ├─L: 18B
    │   │   └─R: 19R
    │   └─R: 22B
    └─R: 30R
        ├─L: 25B
        │   └─L: 24R
        └─R: 40B
            ├─L: 35R
            └─R: 57R

26.5.3 删除与“双黑”思路

红黑树先按 BST 删除规则定位并替换关键字，再根据实际从树中移除结点的原颜色决定是否修复：

1. 实际删去红结点：黑高不变，直接结束。
2. 实际删去黑结点且其唯一非 NIL 孩子为红：用孩子顶替并染黑，结束。
3. 实际删去黑结点，顶替位置也是黑色或 NIL：该路径少一个黑结点，可把顶替结点暂看成“额外带一层黑”，即双黑，随后围绕兄弟结点修复。

设双黑结点为 $x$，兄弟为 $s$；“近侄子”靠近 $x$，“远侄子”远离 $x$。以下以 $x$ 是左孩子为例，右孩子情形镜像处理：

此时近侄子是 $s$ 的左孩子，远侄子是 $s$ 的右孩子。若 $x$ 是右孩子，不能照抄上表的旋转方向，而要完整镜像：

循环结束后还要把当前 $x$ 染黑，并再次保证根为黑色。特别地，在“黑兄弟、双黑侄子”情况下，若父原为红色，双黑上移到父后会由最终染黑直接吸收，不再继续上传。

删除修复必须同时维护 BST 次序、根黑、不红红和黑路同；仅完成普通 BST 的指针删除并不代表红黑树删除结束。整个删除仍为 $O(\log n)$。

---

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：顺序查找和折半查找 · 下一篇：B 树
• 关联专题：查找代码

26.6 本节复盘

• BST 的核心是不等式和中序有序；普通 BST 的最坏性能由树高决定，可退化到 $O(n)$。
• 删除双孩子 BST 结点时，用直接前驱或直接后继把问题转化为至多一个孩子的删除。
• AVL 是 BST，且每个结点 $BF\in{-1,0,1}$；插入通常一次局部调整结束，删除可能继续向上调整。
• AVL 的 LL、RR 用单旋，LR、RL 用双旋；旋转后一定要复核中序次序和高度。
• 红黑树的四句核心是“根叶黑、不红红、黑路同”，高度满足 $h\le2\log_2(n+1)$。
• 红黑树插入先染红：红叔染色上移，黑叔按 LL/RR/LR/RL 旋转染色；删除黑结点时要处理黑高亏欠。
• AVL 平衡更严格，红黑树更新通常更省调整；二者查找、插入、删除的最坏时间均为 $O(\log n)$。