7.3.2 平衡二叉树
## 7.3.2 平衡二叉树 ### 1. 平衡二叉树的定义 为了避免树的高度增长过快而导致二叉排序树性能下降，在插入和删除结点时，需保证任意结点的左右子树高度差的绝对值不超过1。满足这一条件的二叉树称为平衡二叉树（Balanced Binary Tree），也称AVL树。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树中所有结点的平衡因子只能取-1、0或1。 **考点击左** 平衡二叉树的定义（2009） 因此，平衡二叉树可形式化定义为：它或者是一棵空树，或者是具有下列性质的二叉树——其左子树和右子树均为平衡二叉树，且左右子树的高度差的绝对值不超过1。图7.9(a)是一棵平衡二叉树，图7.9(b)是一棵不平衡的二叉树。结点内的数字表示其平衡因子。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 平衡二叉树
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 不平衡的二叉树 图7.9 平衡二叉树和不平衡的二叉树 ### 2. 平衡二叉树的插入 平衡二叉树维持平衡的基本思想如下：每当插入一个结点后，沿查找路径向上检查各祖先结点是否因该操作而失去平衡。若存在失衡结点，则定位插入路径上离新结点最近、且平衡因子绝对值大于1的结点 $A$，以 $A$ 为根的子树即为最小不平衡子树。随后，在保持二叉排序树特性的前提下，通过旋转调整该子树的结构，使其重新达到平衡。 **考点击左** 平衡二叉树中插入操作的特点（2015） 每次调整的对象都是最小不平衡子树，图7.10中的虚线框内所示即为最小不平衡子树。 <!-- page: 295 --> 第7章 查找 283
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.10 最小不平衡子树示意 ## 考虑图7.1 平衡二叉树的插入及调整操作的实例（2010、2019、2021） 平衡二叉树的插入过程前半部分与普通二叉排序树相同；但在新结点插入后，若导致查找路径上的某个结点失去平衡，则需执行相应的调整。可将调整的规律归纳为下列4种情况： 1）LL平衡旋转（右单旋转）。由于在结点 $A$ 的左孩子（L）的左子树（L）上插入了新结点，$A$ 的平衡因子由1增至2，导致以 $A$ 为根的子树失去平衡，需要一次向右的旋转操作。将 $A$ 的左孩子 $B$ 向右上旋转，使其代替 $A$ 成为新的根结点；将 $A$ 向右下旋转，成为 $B$ 的右孩子；而 $B$ 的原右子树则作为 $A$ 的左子树。如图7.11所示，结点旁的数值代表结点的平衡因子，方块表示相应结点的子树，下方数值代表该子树的高度。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 插入结点前
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 插入结点导致不平衡
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) LL旋转（右单旋转） 图7.11 LL平衡旋转 2）RR平衡旋转（左单旋转）。由于在结点 $A$ 的右孩子（R）的右子树（R）上插入了新结点，$A$ 的平衡因子由-1减至-2，导致以 $A$ 为根的子树失去平衡，需要一次向左的旋转操作。将 $A$ 的右孩子 $B$ 向左上旋转，使其替代 $A$ 成为新的根结点；将 $A$ 向左下旋转，成为 $B$ 的左孩子；而 $B$ 的原左子树则作为 $A$ 的右子树，如图7.12所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 插入结点前
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 插入结点导致不平衡
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) RR旋转(左单旋转) 图7.12 RR平衡旋转 3）LR平衡旋转（先左后右双旋转）。由于在结点 $A$ 的左孩子（L）的右子树（R）上插入新结点，$A$ 的平衡因子由1增至2，导致以 $A$ 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 $A$ 的左孩子 $B$ 的右子树的根结点 $C$ 向左上旋转，使其取代 <!-- page: 296 --> 2027年数据结构考研复习指导 $B$ 的位置；然后将 $C$ 向右上旋转，使其取代 $A$ 的位置，如图 7.13 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 插入结点导致不平衡
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) LR旋转(双旋转) 图 7.13 LR 平衡旋转 4）RL 平衡旋转（先右后左双旋转）。由于在结点 $A$ 的右孩子（R）的左子树（L）上插入新结点，$A$ 的平衡因子由-1 减至-2，导致以 $A$ 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 $A$ 的右孩子 $B$ 的左子树的根结点 $C$ 向右上旋转，使其取代 $B$ 的位置；然后将 $C$ 向左上旋转，使其取代 $A$ 的位置，如图 7.14 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 插入结点前
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 插入结点导致不平衡
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) RL旋转(双旋转)
图 7.14 RL 平衡旋转
# 注意
LR 和 RL 旋转时，新结点究竟是插入 $C$ 的左子树还是右子树不影响旋转过程，而图 7.13 和图 7.14 中以插入 $C$ 的左子树为例。
## 考点击注
### 构造平衡二叉树的过程（2013）
以关键字序列 $\{15, 3, 7, 10, 9, 8\}$ 构造一棵平衡二叉树的过程为例：图 7.15(d) 插入 7 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的右子树，因此需执行 LR 旋转，先左后右双旋转，调整后的结果如图 7.15(e) 所示。图 7.15(g) 插入 9 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的左子树，需执行 LL 旋转，右单旋转，调整后的结果如图 7.15(h) 所示。图 7.15(i) 插入 8 后导致不平衡，最小不平衡子树的根为 7，插入位置为其右孩子的左子树，需执行 RL 旋转，先右后左双旋转，调整后的结果如图 7.15(j) 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 空树 (b) 插入 15 (c) 插入 3 (d) 插入 7 (e) LR旋转 (f) 插入 10 图 7.15 平衡二叉树的生成过程 <!-- page: 297 --> 第7章 查找 285
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(g)插入9
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)LL旋转
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(i)插入8
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(i)RL旋转 图 7.15 平衡二叉树的生成过程（续） ## 3. 平衡二叉树的删除 与插入操作相似，以删除结点 $w$ 为例说明平衡二叉树删除操作的步骤： 1）使用二叉排序树的方法删除结点 $w$ 。 2）若导致不平衡，则从结点 $w$ 开始向上回溯，找到第一个不平衡的结点 $z$ （最小不平衡子树的根）。设 $y$ 是 $z$ 的较高子树的根结点，$x$ 是 $y$ 的较高子树的根结点。 3）对以 $z$ 为根的子树进行平衡调整，其中 $x$ 、 $y$ 和 $z$ 的相对位置有以下四种情况： - $y$ 是 $z$ 的左孩子，$x$ 是 $y$ 的左孩子（LL，右单旋转）； - $y$ 是 $z$ 的左孩子，$x$ 是 $y$ 的右孩子（LR，先左后右双旋转）； - $y$ 是 $z$ 的右孩子，$x$ 是 $y$ 的右孩子（RR，左单旋转）； - $y$ 是 $z$ 的右孩子，$x$ 是 $y$ 的左孩子（RL，先右后左双旋转）。 这些调整方式与插入操作相同。不同之处在于：插入操作只需对以 $z$ 为根的子树进行一次平衡调整，而删除操作则可能需要多次调整。若一次调整导致子树的高度减 1，则可能还需对 $z$ 的祖先结点进行平衡调整，甚至回溯到根结点（导致整棵树的高度减 1）。 以删除图 7.16(a) 中的结点 32 为例，由于 32 是叶结点，直接删除即可。然后向上回溯，找到第一个不平衡结点 $44(z)$，$z$ 的较高子树的根为 $78(y)$，$y$ 的较高子树的根为 $50(x)$，满足 RL 情况，需执行先右后左的双旋转。调整后的结果如图 7.16(c) 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 删除 32 前 图 7.16 平衡二叉树的删除
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 右旋
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 左旋
## 4. 平衡二叉树的查找
**考虑图** 指定条件下平衡二叉树的结点数的分析（2012）
在平衡二叉树上进行查找的过程与普通二叉排序树相同，因此关键字的比较次数最多等于树的深度。设 $n_h$ 表示深度为 $h$ （根结点深度为 1）的平衡二叉树中所含的最少结点数。显然有 $n_0 = 0$ 、 $n_1 = 1$ 、 $n_2 = 2$ ，且满足 $n_h = n_{h-2} + n_{h-1} + 1$ ，如图 7.17 所示，依次推出 $n_3 = 4$ 、 $n_4 = 7$ 、 $n_5 = 12$ 、…。含
<!-- page: 298 -->
2027年数据结构考研复习指导
有 $n$ 个结点的平衡二叉树的最大深度为 $O(\log_2 n)$，因此平均查找时间复杂度为 $O(\log_2 n)$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.17 结点个数 $n$ 最少的平衡二叉树 ## 注意 该结论可用于求解给定结点数的平衡二叉树在查找时所需的最多比较次数（树的最大深度）。例如，含有12个结点的平衡二叉树中查找某个结点的最多比较次数？ 深度为 $h$ 的平衡二叉树中所含的最多结点数显然是满二叉树的情况。 ## 7.3.3 红黑树 ### 1. 红黑树的定义 为了保持AVL树的平衡性，在插入和删除操作后，会非常频繁地调整全树的整体拓扑结构，代价较大。为此，在AVL树的平衡标准基础上进一步放宽条件，引入了红黑树的结构。 一棵红黑树是满足如下红黑性质的二叉排序树： ① 每个结点或是红色，或是黑色的。 ② 根结点是黑色的。 ③ 叶结点（虚构的外部结点、NULL结点）都是黑色的。 ④ 不存在两个相邻的红结点（红结点的父结点和孩子结点均是黑色的）。 ⑤ 对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。 与折半查找树和B树类似，为了便于对红黑树的实现和理解，引入了 $n + 1$ 个外部叶结点，这些结点被视为黑色，以保证每个内部结点的左右子树均非空。图7.18所示是一棵红黑树。 从某个结点出发（不含该结点）到达一个叶结点的任意一个简单路径上的黑结点总数称为该结点的黑高（记为 bh），黑高的概念是由性质⑤确定的。根结点的黑高称为红黑树的黑高。 结论 1：从根到叶结点的最长路径不大于最短路径的 2 倍。 根据性质⑤，从根到任意一个叶结点的最短路径必然全由黑结点构成。根据性质④，当某条路径最长时，这条路径必然是由黑结点和红结点交替构成的，此时黑结点的数量固定，红结点的数量最多等于黑结点的数量。图7.18中的6-2和6-15-18-20就是这样的两条路径。 结论2：有 $n$ 个内部结点的红黑树的高度 $h \leqslant 2\log_2(n + 1)$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.18 一棵红黑树
证明：根据结论1，从根到叶结点（不含叶结点）的任意一条简单路径上都至少有一半是黑结点，因此根的黑高至少为 $h / 2$。由此得出 $n \geqslant 2^{h / 2} - 1$，从而得到结论。
由结论2也可推出，黑高为 $h$ 的红黑树的内部结点数最少是 $2^{h} - 1$，最多是 $2^{2h} - 1$。
<!-- page: 299 -->
第7章 查找
287
可见，红黑树采用“适度平衡”策略——相比AVL树的“高度平衡”（左右子树高度差 $\leqslant 1$），允许左右子树高度相差最多达2倍，显著降低了插入/删除时结构调整的频率。因此，对于动态查找表：若查找操作远多于插入/删除，采用AVL树更优（查找更快）；若插入/删除频繁，则采用红黑树更合适（调整开销小）。由于红黑树在实际应用中综合性能更优，它被广泛采用，例如C++中的map和set（Java中的TreeMap和TreeSet）均基于红黑树实现。
## 2. 红黑树的插入
红黑树的插入过程与普通二叉查找树基本类似。不同之处在于，插入新结点后可能破坏红黑性质，因此需要通过重新着色或旋转操作进行调整，以恢复红黑树的基本性质。
### 结论3：新插入的结点初始应着为红色。
假设将其染为黑色，则该结点所在路径的黑结点数将比其他路径的多1，几乎必然违反性质⑤（所有路径的黑结点数相等），且调整代价较高。而若染为红色，则所有路径的黑结点数保持不变，仅当出现父子均为红色时才违反性质④，此时，局部调整即可高效恢复平衡。
设新插入的结点为 $z$。插入与调整过程如下：
1）用二叉查找树规则插入 $z$，并将其染为红色。若 $z$ 的父结点为黑色，则红黑性质未被破坏，插入结束。
2）若 $z$ 为根结点，则将其染为黑色（满足性质②），树的黑高加1，插入结束。
3）若 $z$ 非根，且其父结点 $z.p$ 为红色，则违反性质④。由于原树合法，根据性质②和④，$z$ 的爷结点 $z.p.p$ 必然存在且为黑色。此时，需要根据叔结点 $y（z.p$ 的兄弟）的颜色分三种情形处理（此处假设 $z.p$ 是 $z.p.p$ 的左孩子，右孩子情形对称，后面会说明）。
**情形1（LR型，先左旋再右旋）：** $z$ 的叔结点 $y$ 是黑色的，且 $z$ 是其父结点的右孩子。
即 $z$ 是其爷结点的左孩子的右孩子。先对 $z.p$ 执行左旋，使 $z$ 上升取代原父位置，转化为情形2。此操作不改变任何路径的黑结点数（因 $z$ 与 $z.p$ 均为红色），故性质⑤不受影响。
**情形2（LL型，右单旋）：** $z$ 的叔结点 $y$ 是黑色的，且 $z$ 是其父结点的左孩子。
即 $z$ 是其爷结点的左孩子的左孩子。对 $z.p.p$ 执行右旋，并将原父结点染黑、原爷结点染红。此操作保持所有路径的黑结点数不变，同时消除连续红结点，恢复全部红黑性质，插入结束。
图7.19展示了情形1（LR型）和情形2（LL型）的调整过程。子树 $T_{1}$、$T_{2}$、$T_{3}$ 和 $T_{4}$ 均以黑色结点为根，且黑高相同，确保旋转前后性质⑤成立。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.19 情况1和情况2的调整方式 **对称情形**：若 $z.p$ 是 $z.p.p$ 的右孩子，则对应RL型（先右旋后左旋）和RR型（左单旋），处理方式完全对称，此处不再赘述。可见，红黑树的调整方法与AVL树有异曲同工之妙。 **情形3**：$z$ 的叔结点 $y$ 是红色的。 无论 $z$ 是左孩子还是右孩子，均无影响。将 $z.p$ 和 $y$ 染为黑色，将 $z.p.p$ 染为红色，以在局部恢复性质④（无连续红结点）和性质⑤（所有路径的黑结点数相等）。但 $z.p.p$ 变红后，可能与其 <!-- page: 300 --> 2027年数据结构考研复习指导 父结点再次形成红-红冲突。因此，将 $z p p$ 视为新的“待调整结点 $z$ ”，继续向上回溯检查。调整过程如图7.20所示。该过程可能多次重复，每次循环 $z$ 都会上移两层，直至满足以下任何一个终止条件：$z$ 成为根结点（此时染黑，结束）；进入情形1或情形2（执行旋转后结束）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.20 情况3的调整方式 补充说明：尽管新结点最初总是插入在某个叶结点位置，但在情形3的回溯过程中，指针 $z$ 可能已上移至内部结点，从而拥有子树。因此，所有调整操作都必须考虑其子树的存在。 以图7.21(a)中的红黑树为例（虚线表示插入后的状态），依次插入5、4和12的过程如图7.21所示。插入5，属于情形3，将5的父结点3与叔结点10染黑，爷结点7染红；由于7是根结点，需将其重新染黑，树的黑高加1，结束。插入4，属于情形1的对称情形（RL型），先对以5为根的子树执行右旋，转为情形2的对称情形（RR型），交换3和4的颜色，再对以4为根的子树执行左旋，结束。插入12，其父结点为黑色，无须调整，直接结束。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.21 红黑树的插入过程 ## 3. 红黑树的删除 ### 注意 本节内容难度较大，考查概率较低，读者可根据自身情况决定是否学习或学习的时机。 红黑树的插入操作可能破坏性质④（无连续红结点）。而删除操作则更易破坏性质⑤（所有路径的黑结点数相等），特别是当被删结点为黑色时，会导致经过该结点的所有路径黑高减1。 <!-- page: 301 --> 第7章 查找 289 删除过程首先执行二叉查找树的标准删除。若待删结点有两个非空子树，不能直接删除，需用其中序后继（或前驱）替代之，即右子树中的最小结点，并转为删除该后继结点。由于中序后继在其子树中是最小值，因此至多只有一个右孩子。由此，删除操作最终都可归结为以下两种情形： - 待删结点有一个孩子（左或右孩子）。 - 待删结点是终端结点（无孩子）。 1）若待删结点有一个孩子，则只有两种情况，如图7.22所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.22 只有右子树或左子树的删除情况 且仅有这两种情况存在。则子树只有一个结点，且必然是红色，否则会破坏性质⑤。 2）待删结点无孩子，且该结点是红色的，此时可直接删除，而不需要做任何调整。 3）待删结点无孩子，且该结点是黑色的，此时设待删结点为 $y$ ， $x$ 是用来替换 $y$ 的结点（注意，当 $y$ 是终端结点时，$x$ 是黑色的NULL结点）。删除 $y$ 后将导致先前包含 $y$ 的任何路径上的黑结点数量减1，因此 $y$ 的任何祖先都不再满足性质⑤，简单的修正办法就是将替换 $y$ 的结点 $x$ 视为还有额外一重黑色，定义为双黑结点。也就是说，若将任何包含结点 $x$ 的路径上的黑结点数量加1，则在此假设下，性质⑤得到满足，但破坏了性质①。于是，删除操作的任务就转化为将双黑结点恢复为普通结点。 分为以下四种情形，区别在于 $x$ 的兄弟结点 $w$ 及 $w$ 的孩子结点的颜色不同。 情形1： $x$ 的兄弟结点 $w$ 是红色的。 $w$ 必须有黑色左右孩子和父结点。交换 $w$ 和父结点 $xp$ 的颜色，然后对 $xp$ 做一次左旋，而不会破坏红黑树的任何规则。现在，$x$ 的新兄弟结点是旋转之前 $w$ 的某个孩子结点，其颜色为黑色，这样，就将情形1转换为情形2、3或4处理。调整方式如图7.23所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.23 情形1的调整方式 情形2（RR型，左单旋）： $x$ 的兄弟结点 $w$ 是黑色的，且 $w$ 的右孩子是红色的。 即这个红结点是其爷结点的右孩子的右孩子。交换 $w$ 和父结点 $xp$ 的颜色，把 $w$ 的右孩子看为黑色，并对 $x$ 的父结点 $xp$ 做一次左旋，将 $x$ 变为单重黑色，此时不再破坏红黑树的任何性质，结束。调整方式如图7.24所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.24 情形2的调整方式 <!-- page: 302 --> 2027年数据结构考研复习指导 情形3（RL型，先右旋再左旋）： $x$ 的兄弟结点 $w$ 是黑色的，$w$ 的左孩子是红色的，$w$ 的右孩子是黑色的。 即这个红结点是其爷结点的右孩子的左孩子。交换 $w$ 和其左孩子的颜色，然后对 $w$ 做一次右旋，而不破坏红黑树的任何性质。现在，$x$ 的新兄弟结点 $w$ 的右孩子是红色的，这样就将情形3转换为了情形2。调整方式如图7.25所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.25 情形3的调整方式 情形4：$x$ 的兄弟结点 $w$ 是黑色的，且 $w$ 的两个孩子结点都是黑色的。 因为 $w$ 也是黑色的，所以可从 $x$ 和 $w$ 上去掉一重黑色，使得 $x$ 只有一重黑色而 $w$ 变为红色。为了补偿从 $x$ 和 $w$ 中去掉的一重黑色，把 $x$ 的父结点 $x.p$ 额外着一层黑色，以保持局部的黑高不变。通过将 $x.p$ 作为新结点 $x$ 来循环，$x$ 上升一层。若是通过情形1进入情形4的，因为原来的 $x.p$ 是红色的，将新结点 $x$ 变为黑色，终止循环，结束。调整方式如图7.26所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.26 情形4的调整方式 若 $x$ 是父结点 $x.p$ 的右孩子，则还有四种对称的情形，处理方式类似，不再赘述。 归纳总结：在情形4中，因 $x$ 的兄弟结点 $w$ 及左右孩子都是黑色，可以从 $x$ 和 $w$ 中各提取一重黑色（以让 $x$ 变为普通黑结点），不会破坏性质④，并把调整任务向上“推”给它们的父结点 $x.p$。在情形1、2和3中，因为 $x$ 的兄弟结点 $w$ 或 $w$ 左右孩子中有红结点，所以只能在 $x.p$ 子树内用调整和重新着色的方式，且不能改变 $x$ 原根结点的颜色（否则向上可能破坏性质④）。情形1虽可能会转为情形4，但因为新 $x$ 的父结点 $x.p$ 是红色的，所以执行一次情形4就会结束。情形1、2和3在各执行常数次的颜色改变和至多3次旋转后便终止，情形4是可能重复执行的唯一情形，每执行一次指针 $x$ 上升一层，至多 $O(\log_2 n)$ 次。 以图7.27(a)所示的红黑树为例（虚线表示删除前的状态），依次删除5和15的过程如图7.27所示。删除5，用虚构的黑色NULL结点（图中为N结点）替换，视为双黑NULL结点，属于情形1，交换兄弟结点12和父结点8的颜色，对8执行左旋；转变为情形4，从双黑NULL结点和10中各提取一重黑色（提取后，双黑NULL结点变为普通NULL结点，图中省略，10变为红色），因原父结点8是红色，所以将8变为黑色，结束。删除15，属于情形3的对称情形（LR型），交换8和10的颜色，对8执行左旋；转变为情形2的对称情形（LL型），交换10和12的颜色（两者颜色一样，无变化），将10的左孩子8着为黑色，对12执行右旋，结束。 <!-- page: 303 --> 第7章 查找 291
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.27 红黑树的删除过程