红黑树的定义与性质
- 导读
- 一、基本概念
- 1.1 定义与性质
- 1.2 重要概念
- 二、重要推论
- 2.1 推论1
- 两种计算路径长度的技巧
- 插入法
- 2.2 推论2
- 内部结点数与黑高关系证明
- 推论2的证明
- RBT与AVL
- 结语
导读
大家好，很高兴又和大家见面啦！！！
在前面的内容中大家已经学习了两种树形查找结构：
- BST：二叉排序树，其允许是一棵空树，也可以是满足以下条件的树：
- 若左子树非空，则左子树上所有节点的值均小于根节点
- 若右子树非空，则右子树上所有节点的值均大于根节点
- 其左右子树也分别是一棵二叉排序树
- AVL：平衡二叉树，其是一棵能够进行自平衡旋转的BST
为了避免 BST的树高增长的过快而导致其查找效率降低，因此引入了能够将左右子树的高度差控制在− 1 ∼ 1 -1 \sim 1−1∼1 之间的 AVL；
AVL通过判断树的平衡因子，以此来决定是否需要进行平衡旋转：
- 当 平衡因子 不在 − 1 ∼ 1 -1 \sim 1−1∼1这个范围内时，则说明该树已经失衡，需要通过自平衡旋转使其恢复平衡
正因如此，当我们进行频繁的插入或删除运行时，就很容易破坏AVL的平衡特性，而导致其要求进行频繁的平衡旋转操作；
为了优化这种情况，于是大家又再一次引入了一种新的自平衡排序树——红黑树。
那什么是 红黑树 呢？相比于 AVL其又有哪些优势呢？从今天的内容开始，我们将会逐步揭开红黑树的神秘面纱；
下面就让我们一起进入今天的内容；
一、基本概念
1.1 定义与性质
红黑树（Red-Black Tree, RBT）是一种满足如下红黑性质 的 BST：
- 每个结点或是红色，或是黑色
- 根结点是 黑色
- 叶结点 （虚构的外部节点、
NULL结点）都是黑色 - 不存在两个相邻的红结点（红结点的父结点与孩子结点均为黑色）
- 对每个结点，从该结点出发，到任意叶结点的简单路径上，所含的黑结点的数量相同
上述的 五大根本性质 与 定义我们可以将其总结为十二个字：
- 左根右：RBT 是一种 BST，满足 左子树 ≤ 根节点 ≤ 右子树 左子树 \leq 根节点 \leq 右子树左子树≤根节点≤右子树
- 根叶黑：根结点、叶结点一定是黑色
- 黑路同：从任一结点出发，到达任一空叶结点的路径上经过的黑结点数量都相同
- 不红红：任何一条查找路径上不能连续出现两个红结点
1.2 重要概念
黑高：一个结点的黑高是指从该结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数
叶结点：在 RBT中，“叶结点”通常指“失败结点”（又名：空叶结点/NULL结点/外部结点）
下面我们就来通过一棵红黑树来进一步说明这些概念：
在上图中的这棵RBT 中，其 根结点 与 叶结点黑色，并且这些就是一定叶结点 一定是 NULL 结点；
对于任一结点，其黑高指的是从该节点开始，到任一叶结点的路径上，不包含该结点的黑结点数量：
- 根结点
6，其到任一 叶结点 的路径上都会包含2个黑结点，因此其黑高为2：6 ---> 2 ---> NULL，包含除结点6外的两个黑结点：2和NULL6 ---> 15 ---> 11 ---> 8 ---> NULL，包含除了结点6外的两个黑结点：11和NULL
- 结点
2，其到任一 叶结点 的路径上都会包含1个黑结点，因此其黑高为1：2 ---> NULL，包含除结点2外的一个黑结点：NULL
对于结点 6 而言，其左子树之所以为 黑 ，是因为其右子树 15 的黑高为 2 ，为了满足 黑路同 ，因此结点 2 只能为 黑 ；
若我们将 2 变为红色，则会导致从结点 6 出发，到左子树中的任一叶结点，与到右子树中的任一叶结点所包含的黑结点数不一致；
因此结点 2 只能为 黑；
二、要紧推论
从 RBT 的 五大基本性质中，我们可以得到RBT 的三条 重要推论：
- 从根结点到叶结点的最长路径不大于最短路径的2倍
- 有n个内部结点的红黑树高度h < = 2 l o g 2 ( n + 1 ) h<=2log_2(n+1)h<=2log2(n+1)
- 新插入红黑树中的结点初始着为红色
今天我们需要重点介绍前两条推论；
2.1 推论1
当从根结点出发，到任一叶结点的简单路径最短时，这条路径上的结点必然都是黑色，如最短简单路径：6 --> 2 ---> NULL
当某条路径最长时，这条路径必然是由黑结点与红结点相间构成，如：6 ---> 15 ---> 11 ---> 14 ---> NULL
可以看到这两条路径的长度分别为：3 和 5 ，而 5 < 3 ∗ 2 5 < 3 * 25<3∗2 ；
- 若我们在最长路径中插入一个结点使其长度变为最短路径的两倍，即最长路径长度变为：
6，那么根据红黑性质——不红红 与 根叶黑 ，对应的路径上其结点的颜色一定是：黑 ---> 红 ---> 黑 ---> 红 ---> 黑 ---> 黑，其根结点的黑高为：bh = 3； - 最短路径保持不变，即最短路径长度为：
3，并且该路径上的结点均为黑色，即：黑 ---> 黑 ---> 黑，其根结点的黑高为：bh = 2 - 显然此时的最短路径与最长路径，其根结点不满足红黑性质——黑路同，因此大家可以得到结论：从根结点到叶结点的最长路径一定小于最短路径的2倍
两种计算路径长度的途径
这里有朋友可能会好奇，为什么这里的性质说的是不大于而我们得到的结论是一定小于？
不一致的：就是对于这个疑问，我给出的解释是：我这里给出的实例所计算路径长度的方法与推论1的表述
- 方法一：计算完整路径长度，即从根结点到外部结点的总长度
- 方式二：计算内部路径长度，即从根结点到内部叶结点的总长度
前面我所展示的路径长度计算方法利用的是方法一，因此大家会得出严格小于 这个结论；
当我们采用办法二进行计算时，那么其最短路径长度与最长路径长度分为为：
- 最短路径：
6 ---> 2，长度为2 - 最长路径：
6 ---> 15 ---> 11 ---> 14，长度为4
可以看到此时的最长路径长度就与最短路径长度的两倍相等；
因此 推论1以办法二的方式计算路径长度得出的结论，而就是的表述严格小于 也属于 不大于的范畴，所以，我们如果通过方法一的方式计算路径长度，我们同样也允许说不大于；
希望大家能够准确辨别空叶结点 与 内部叶结点这二者的区别，切记不能将二者混为一谈！！！
插入法
推论1的验证，我们还有一个更简便的手段——插入法；
这里我们以下图进行方便的说明：
在这条仅由黑色块组成的路径中，我们需要插入红色块，并且保证该路径的起点与终点为黑色，且插入的红色块不能连续，那么我们能够插入的红色块最多只有2块：
当我们去掉终点的黑色块后，我们不难发现，这时的红色块与黑色块的数量是相同的：
每个黑色块后都紧跟一个红色块，这样我们就能得到以下结论：
- 当计算终点黑色块时，红色块的总数比黑色块少
1 - 当不计算终点黑色块时，红色块的总数与黑色块相等
因此对于最短路径长度为N NN 的 RBT，其最长路径长度为：
- 计算终点的空叶结点时，最长路径长度为2 ∗ N − 1 2 * N - 12∗N−1
- 不计算终点的空叶结点时，最长路径长度为2 ∗ N 2 * N2∗N
这也进一步验证了推论1：
- 从根结点到叶结点的最长路径不大于最短路径的2 22 倍
2.2 推论2
由推论1可知，在红黑树中，其最长路径所包含的红结点是最多的，且不管是用方法一计算长度还是方法二计算长度，其红结点的数量一定不会超过黑结点的数量，即对于长度为 2N 的最长路径：
- 由方法一计算得出：其红结点的数量一定是
N - 1，黑结点的数量一定是N + 1 - 由方法二计算得出：其红结点的数量一定是
N，黑结点的数量一定是N
当我们只分析内部结点 时，即采取 方法二 的方式计算一条路径的长度，那么对于 n 个内部结点的红黑树，其树高为 h ，这也就表明该 RBT 的最长路径长度为 h ；
对于一棵 RBT而言，当其最长路径中的红结点数量最多时，其黑高最小；
在这棵 RBT 中，其仅计算内部结点的最长路径长度为 h ，这样我们就能得到红结点最多时，其红黑结点的数量均为 h 2 \frac{h}{2}2h ；
而我们要计算根结点的黑高时，我们需要去掉根节点，并加上路径的终点——空叶结点说，根结点的黑高至少为就是，这也就h 2 \frac{h}{2}2h ；
由二叉树的性质我们可知，对于结点数量为n nn ，树高为 h hh的二叉树，其结点数量n nn 与树高 h hh之间的关系为：
- 满二叉树时，n nn 最大，n = 2 h − 1 n = 2^{h} - 1n=2h−1
- 只存在一条路径时，n nn 最小，n = h n = hn=h
在 RBT中，其内部结点数n nn 与其黑高 b h bhbh之间的关系为：n ≥ 2 b h − 1 n \geq 2^{bh} - 1n≥2bh−1，该结论我们可以借助数学归纳法 进行证明；
内部结点数与黑高关系证明
由 分治思想我们可以得到，RBT的内部总结点数是由三部分组成：
- 根节点
- 左子树的内部结点总数
- 右子树的内部结点总数
因此我们要求RBT的内部结点总数n nn就要求获取其左右子树中的结点总数；
假设对于一棵RBT，其任一结点x xx 的黑高为 b h x bh_xbhx，以该结点为根的子树的内部结点总数为n x n_xnx ；
当该结点为 空叶结点时 ，其黑高b h x = 0 bh_{x} = 0bhx=0，其内部结点数为：n x = 2 b h x − 1 = 2 0 − 1 = 1 − 1 = 0 n_{x} = 2^{bh_{x}} - 1 = 2^0 - 1 = 1 - 1 = 0nx=2bhx−1=20−1=1−1=0，此时结论成立；
在 RBT中，其任一结点x xx的左右子树的黑高至少为：b h x − 1 bh_{x} - 1bhx−1
这是因为当结点x xx的子树根结点为黑结点时，其子树的黑高为：b h x − 1 bh_{x}- 1bhx−1 ；
当结点 x xx的子树根结点为红结点时，其子树的黑高为：b h x bh_{x}bhx；
因此我们可以假设：任一结点x xx其左右子树的内部结点数量为：
n x l ≥ 2 b h x − 1 − 1 n x r ≥ 2 b h x − 1 − 1 n_{x_l} \geq 2^{bh_x - 1} - 1 \\ n_{x_r} \geq 2^{bh_x - 1} - 1nxl≥2bhx−1−1nxr≥2bhx−1−1
那么对于以结点x xx为根的子树，其内部结点数量n x n_xnx 为：
n x = n x l + n x r + 1 n x ≥ 2 b h x − 1 − 1 + 2 b h x − 1 − 1 + 1 n x ≥ 2 ∗ 2 b h x − 1 − 1 n x ≥ 2 b h x − 1 \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*}nxnxnxnx=nxl+nxr+1≥2bhx−1−1+2bhx−1−1+1≥2∗2bhx−1−1≥2bhx−1
推论2的证明
在前面我们已经证明了，一棵高度为h hh 的 RBT ，其黑高 b h ≥ h 2 bh \geq \frac{h}{2}bh≥2h ；
现在大家只需要将黑高b h bhbh带入到内部结点n nn 与 黑高 b h bhbh 的公式 n ≥ 2 b h − 1 n \geq 2^{bh} - 1n≥2bh−1中，就可以得到推论2：
n ≥ 2 b h − 1 n ≥ 2 h 2 − 1 n + 1 ≥ 2 h 2 log 2 ( n + 1 ) ≥ h 2 2 ∗ log 2 ( n + 1 ) ≥ h \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*}nnn+1log2(n+1)2∗log2(n+1)≥2bh−1≥22h−1≥22h≥2h≥h
当一棵 RBT 的黑高为 b h = h bh = hbh=h时，其对应的树高为与内部结点数分别为：
- 当最长路径中不存在红结点时，树高最小为h hh，对应的内部结点数最少，为2 h − 1 2^h - 12h−1
- 当最长路径中红结点数量最多时，树高最大为2 h 2h2h，对应的内部结点数最大，为2 2 h − 1 2^{2h} - 122h−1
可见，RBT 的 适度平衡 ，由 AVL 的 高度平衡 ，降低到了 任一结点左右子树的高度，相差不超过2 22 倍。这种调整同时也降低了动态处理时的调整频率。
RBT与AVL
对于一棵动态查找树，若插入和删除操作比较少，查找操作比较多，则采用AVL比较合适，否则采用RBT 比较合适。
由于维护 AVL 这种 高度平衡所付出的代价比获得的效益大的多，因此在实际应用中，RBT 的应用更为广泛，如 C++ 中的 map/set 、JAVA 中的 TreeMap/TreeSet 就是用 RBT 实现的。
结语
通过本文的学习，大家系统性地探讨了红黑树（Red-Black Tree, RBT）的核心定义与关键性质。
红黑树作为一种自平衡的二叉查找树，通过其独特的五大性质确保了树的近似平衡：
- 根叶黑：根结点与叶结点（空叶结点）均为黑
- 不红红：不存在连续的两个红结点
- 黑路同：从任一结点x xx出发，到达任一叶结点的简单路径上的黑结点数量相同
与AVL树对高度平衡的严格要求不同，红黑树以"适度平衡"换取了在频繁插入删除场景下更少的旋转操作，这使得它的实际应用更为广泛，如C++ STL中的map/set、Java的TreeMap/TreeSet
核心知识点回顾
最长路径不超过最短路径的两倍
- 这一特性源于"红结点不相邻"和"黑路同"的约束，保证了红黑树不会退化为近似链表的形态
树高 h ≤ 2 log 2 ( n + 1 ) h \leq 2 \log_2(n+1)h≤2log2(n+1)
- 此性质决定了红黑树的搜索效率为O ( l o g n ) O(log n)O(logn)，尽管平衡性略逊于AVL树，但维护成本更低
实际应用优势
在需要频繁动态更新的场景中，红黑树的统计性能更优，是效率与实用性平衡的典范
下一篇内容预告
在接下来的篇章中，我们将深入探讨红黑树最核心的操作——插入操作，重点分析：
- "红插"原则：新节点为什么默认为红色
- 平衡调整策略：变色与旋转（左旋、右旋）的组合运用
- 双红冲突处理：叔叔节点颜色不同时的差异化处理方案
掌握这些情况及其处理流程，是真正理解和应用红黑树的关键。敬请期待！
互动与分享
点赞 - 您的认可是我持续创作的最大动力
收藏⭐ - 方便随时回顾这些重要的基础概念
转发↗️ - 分享给更多可能需要的朋友
评论 - 欢迎留下您的宝贵意见或想讨论的话题
感谢您的耐心阅读！ 关注博主，不错过更多工艺干货。大家下一篇再见！