【数据结构】考研408|数据结构高分堡垒：攻克红黑树五大性质与适度平衡思想

蒙奇D索隆

发布于 2025-12-19 10:26:13

830

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

导读

大家好，很高兴又和大家见面啦！！！在前面的内容中我们已经学习了两种树形查找结构：

BST：二叉排序树，其可以是一棵空树，也可以是满足以下条件的树：
- 若左子树非空，则左子树上所有节点的值均小于根节点
- 若右子树非空，则右子树上所有节点的值均大于根节点
- 其左右子树也分别是一棵二叉排序树
AVL：平衡二叉树，其是一棵能够进行自平衡旋转的 BST

为了避免 BST 的树高增长的过快而导致其查找效率降低，因此引入了能够将左右子树的高度差控制在 -1 \sim 1 之间的 AVL； AVL 通过判断树的平衡因子，以此来决定是否需要进行平衡旋转：

当平衡因子不在 -1 \sim 1 这个范围内时，则说明该树已经失衡，需要通过自平衡旋转使其恢复平衡

正因如此，当我们进行频繁的插入或删除操作时，就很容易破坏 AVL 的平衡特性，而导致其需要进行频繁的平衡旋转操作；为了优化这种情况，于是我们又再一次引入了一种新的自平衡排序树—— 红黑树。那什么是 红黑树 呢？相比于 AVL 其又有哪些优势呢？从今天的内容开始，我们将会逐步揭开 红黑树 的神秘面纱；下面就让我们一起进入今天的内容；

一、基本概念

1.1 红黑树的定义

红黑树（Red-Black Tree, RBT）是一种满足如下 红黑性质 的 BST：

每个结点或是红色，或是黑色
根结点是黑色
叶结点 （虚构的外部节点、NULL 结点）都是黑色
不存在两个相邻的 红结点 （红结点的父结点与孩子结点均为黑色）
对每个结点，从该结点出发，到任意叶结点的简单路径上，所含的黑结点的数量相同

因此我们可以将其总结为十二个字：

左根右：RBT 是一种 BST，满足左子树 \leq 根节点 \leq 右子树
根叶黑：根结点、叶结点一定是黑色
黑路同：从任一结点出发，到达任一空叶结点的路径上经过的黑结点数量都相同
不红红：任何一条查找路径上不能连续出现两个红结点

1.2 重要概念

黑高：一个结点的黑高是指从该结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数 叶结点：在 RBT 中，“叶结点”通常指“失败结点”（又名：空叶结点/NULL结点/外部结点）下面我们就来通过一棵红黑树来进一步说明这些概念：

flowchart TB
a[6<br>bh = 2]
b[2<br>bh = 1]
a--->b
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]

c[15<br>bh = 2]
a--->c

d[11<br>bh = 1]
e[18<br>bh = 1]
c--->d
c--->e

f[8<br>bh = 1]
g[14<br>bh = 1]
d--->f
f--->f1[NULL<br>bh = 0]
f--->f2[NULL<br>bh = 0]
d--->g
g--->g1[NULL<br>bh = 0]
g--->g2[NULL<br>bh = 0]

e--->e1[NULL<br>bh = 0]
h[20<br>bh = 1]
e--->h
h--->h1[NULL<br>bh = 0]
h--->h2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Black
class b1 Black
class b2 Black
class c Red
class d Black
class e Black
class f Red
class g Red
class e1 Black
class h Red
class f1 Black
class f2 Black
class g1 Black
class g2 Black
class h1 Black
class h2 Black

在上图中的这棵 RBT 中，其 根结点 与 叶结点 一定是黑色，并且这些 叶结点 一定是 NULL 结点；对于任一结点，其黑高指的是从该节点开始，到任一 叶结点 的路径上，不包含该结点的黑结点数量：

根结点 6 ，其到任一 叶结点 的路径上都会包含2个黑结点，因此其黑高为 2：
- 6 ---> 2 ---> NULL ，包含除结点 6 外的两个黑结点：2 和 NULL
- 6 ---> 15 ---> 11 ---> 8 ---> NULL ，包含除了结点 6 外的两个黑结点：11 和 NULL
结点 2 ，其到任一 叶结点 的路径上都会包含1个黑结点，因此其黑高为 1 ：
- 2 ---> NULL ，包含除结点 2 外的一个黑结点：NULL

对于结点 6 而言，其左子树之所以为黑，是因为其右子树 15 的黑高为 2 ，为了满足 黑路同 ，因此结点 2 只能为黑；若我们将 2 变为红色，则会导致从结点 6 出发，到左子树中的任一叶结点，与到右子树中的任一叶结点所包含的黑结点数不一致；

flowchart TB
a[6<br>bh_l = 1<br>bh_r = 2<br>bh_l != bh_r]
b[2<br>bh = 1]
a--->b
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]

c[15<br>bh = 2]
a--->c

d[11<br>bh = 1]
e[18<br>bh = 1]
c--->d
c--->e

f[8<br>bh = 1]
g[14<br>bh = 1]
d--->f
f--->f1[NULL<br>bh = 0]
f--->f2[NULL<br>bh = 0]
d--->g
g--->g1[NULL<br>bh = 0]
g--->g2[NULL<br>bh = 0]

e--->e1[NULL<br>bh = 0]
h[20<br>bh = 1]
e--->h
h--->h1[NULL<br>bh = 0]
h--->h2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Red
class b1 Black
class b2 Black
class c Red
class d Black
class e Black
class f Red
class g Red
class e1 Black
class h Red
class f1 Black
class f2 Black
class g1 Black
class g2 Black
class h1 Black
class h2 Black

因此结点 2 只能为黑；

三、性质

RBT 总共有3条性质：

从根结点到叶结点的最长路径不大于最短路径的2倍
有n个内部结点的红黑树高度h<=2log_2(n+1)
新插入红黑树中的结点初始着为红色

这里我们先介绍前两条性质；

3.1 性质1

当从根结点出发，到任一叶结点的简单路径最短时，这条路径上的结点必然都是黑色，如最短简单路径：6 --> 2 ---> NULL 当某条路径最长时，这条路径必然是由黑结点与红结点相间构成，如：6 ---> 15 ---> 11 ---> 14 ---> NULL 可以看到这两条路径的长度分别为：3 和 5 ，而

若我们在最长路径中插入一个结点使其长度变为最短路径的两倍，即最长路径长度变为：6 ，那么根据红黑性质——不红红 与 根叶黑 ，对应的路径上其结点的颜色一定是：黑 ---> 红 ---> 黑 ---> 红 ---> 黑 ---> 黑 ，其根结点的黑高为： bh = 3 ；
最短路径保持不变，即最短路径长度为：3 ，并且该路径上的结点均为黑色，即：黑 ---> 黑 ---> 黑，其根结点的黑高为：bh = 2
显然此时的最短路径与最长路径，其根结点不满足红黑性质——黑路同，因此我们可以得到结论：从根结点到叶结点的最长路径 一定小于 最短路径的2倍

两种计算路径长度的方法

这里有朋友可能会好奇，为什么这里的性质说的是 不大于 而我们得到的结论是 一定小于？对于这个问题，我给出的解释是：我这里给出的实例所计算路径长度的方法与性质1的表述是不一致的：

方法一：计算完整路径长度，即从根结点到外部结点的总长度
方法二：计算内部路径长度，即从根结点到内部叶结点的总长度

前面我所展示的路径长度计算方法使用的是方法一，因此我们会得出 严格小于 这个结论；当我们采用方法二进行计算时，那么其最短路径长度与最长路径长度分为为：

最短路径：6 ---> 2 ，长度为 2
最长路径：6 ---> 15 ---> 11 ---> 14 ，长度为 4

可以看到此时的最长路径长度就与最短路径长度的两倍相等；因此 性质1 的表述是以方法二的方式计算路径长度得出的结论，而 严格小于 也属于 不大于 的范畴，所以，我们如果通过方法一的方式计算路径长度，我们同样也可以说 不大于；希望大家能够准确辨别空叶结点 与 内部叶结点 这二者的区别，切记不能将二者混为一谈！！！

插入法

性质1的验证，我们还有一个更简便的方法——插入法；这里我们以下图进行简单的说明：

flowchart LR
a[黑]
b[黑]
c[黑]
a--->b--->c
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black
class c Black

在这条仅由黑色块组成的路径中，我们需要插入红色块，并且保证该路径的起点与终点为黑色，且插入的红色块不能连续，那么我们能够插入的红色块最多只有2块：

flowchart LR
a[黑]
b[黑]
c[黑]
a--->d[红]--->b--->e[红]--->c
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black
class c Black
class e Red
class d Red

当我们去掉终点的黑色块后，我们不难发现，这时的红色块与黑色块的数量是相同的：

flowchart LR
a[黑]
b[黑]

a--->d[红]--->b--->e[红]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black

class e Red
class d Red

每个黑色块后都紧跟一个红色块，这样我们就能得到以下结论：

当计算终点黑色块时，红色块的总数比黑色块少 1
当不计算终点黑色块时，红色块的总数与黑色块相等

因此对于最短路径长度为 N 的 RBT ，其最长路径长度为：

计算终点的空叶结点时，最长路径长度为 2 * N - 1
不计算终点的空叶结点时，最长路径长度为 2 * N

这也进一步验证了性质1：

从根结点到叶结点的最长路径不大于最短路径的 2 倍

3.2 性质2

由性质1可知，在红黑树中，其最长路径所包含的红结点是最多的，且不管是用方法一计算长度还是方法二计算长度，其红结点的数量一定不会超过黑结点的数量，即对于长度为 2N 的最长路径：

由方法一计算得出：其红结点的数量一定是 N - 1 ，黑结点的数量一定是 N + 1
由方法二计算得出：其红结点的数量一定是 N，黑结点的数量一定是 N

当我们只分析 内部结点 时，即采取 方法二 的方式计算一条路径的长度，那么对于 n 个内部结点的红黑树，其树高为 h ，这也就表明该 RBT 的最长路径长度为 h ；

对于一棵 RBT 而言，当其最长路径中的红结点数量最多时，其黑高最小；

在这棵 RBT 中，其仅计算内部结点的最长路径长度为 h ，这样我们就能得到红结点最多时，其红黑结点的数量均为 \frac{h}{2} ；而我们要计算根结点的黑高时，我们需要去掉根节点，并加上路径的终点——空叶结点，这也就是说，根结点的黑高至少为 \frac{h}{2} ；由二叉树的性质我们可知，对于结点数量为 n ，树高为 h 的二叉树，其结点数量 n 与树高 h 之间的关系为：

满二叉树时，n 最大，n = 2^{h} - 1
只存在一条路径时，n 最小，n = h

在 RBT 中，其内部结点数 n 与其黑高 bh 之间的关系为：n \geq 2^{bh} - 1 ，该结论我们可以通过数学归纳法进行证明；

内部结点数与黑高关系证明

由 分治思想 我们可以得到，RBT 的内部总结点数是由三部分组成：

根节点
左子树的内部结点总数
右子树的内部结点总数

因此我们要求 RBT 的内部结点总数 n 就需要获取其左右子树中的结点总数；假设对于一棵 RBT ，其任一结点 x 的黑高为 bh_x ，以该结点为根的子树的内部结点总数为 n_x ；当该结点为空叶结点时，其黑高 bh_{x} = 0 ，其内部结点数为：n_{x} = 2^{bh_{x}} - 1 = 2^0 - 1 = 1 - 1 = 0，此时结论成立；在 RBT 中，其任一结点 x 的左右子树的黑高至少为：bh_{x} - 1 这是因为当结点 x 的子树根结点为黑结点时，其子树的黑高为：bh_{x}- 1 ；

flowchart TB
a[bh = 2] ---> b[bh = 1]
a--->c[bh = 1]
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]
c--->c1[NULL<br>bh = 0]
c--->c2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black
class c Black
class b1 Black
class c1 Black
class b2 Black
class c2 Black

当结点 x 的子树根结点为红结点时，其子树的黑高为：bh_{x}；

flowchart TB
a[bh = 1] ---> b[bh = 1]
a--->c[bh = 1]
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]
c--->c1[NULL<br>bh = 0]
c--->c2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Red
class c Red
class b1 Black
class c1 Black
class b2 Black
class c2 Black

因此我们可以假设：任一结点 x 其左右子树的内部结点数量为：

$$ n_{x_l} \geq 2^{bh_x - 1} - 1 \ n_{x_r} \geq 2^{bh_x - 1} - 1 $$

那么对于以结点 x 为根的子树，其内部结点数量 n_x 为：

$$ \begin{align*} n_x &= n_{x_l} + n_{x_r} + 1 \ n_x &\geq 2^{bh_x - 1} - 1 + 2^{bh_x - 1} - 1 + 1 \ n_x &\geq 2 * 2^{bh_x - 1} - 1 \ n_x &\geq 2^{bh_x} - 1 \end{align*} $$

性质2的证明

在前面我们已经证明了，一棵高度为 h 的 RBT ，其黑高 bh \geq \frac{h}{2} ；现在我们只需要将黑高 bh 带入到内部结点 n 与黑高 bh 的公式 n \geq 2^{bh} - 1 中，就可以得到性质2：

$$ \begin{align*} n &\geq 2^{bh} - 1 \ n &\geq 2^{\frac{h}{2}} - 1 \ n + 1 &\geq 2^{\frac{h}{2}} \ \log_2 (n + 1) &\geq \frac{h}{2} \ 2 * \log_2 (n + 1) &\geq h \end{align*} $$

当一棵 RBT 的黑高为 bh = h 时，其对应的树高为与内部结点数分别为：

当最长路径中不存在红结点时，树高最小为 h ，对应的内部结点数最少，为 2^h - 1
当最长路径中红结点数量最多时，树高最大为 2h ，对应的内部结点数最大，为 2^{2h} - 1

可见，RBT 的适度平衡，由 AVL 的高度平衡，降低到了任一结点左右子树的高度，相差不超过 2 倍。这种调整同时也降低了动态操作时的调整频率。

RBT与AVL

对于一棵动态查找树，若插入和删除操作比较少，查找操作比较多，则采用 AVL 比较合适，否则采用 RBT 比较合适。由于维护 AVL 这种 高度平衡 所付出的代价比获得的效益大的多，因此在实际应用中，RBT 的应用更为广泛，如 C++ 中的 map/set 、JAVA 中的 TreeMap/TreeSet 就是用 RBT 实现的。