红黑树的特性和实现

深藏阁楼爱情的钟 2022-05-26 01:45 151阅读 0赞

平衡二叉搜索树的形式多样，且各具特色。比如，[伸展树][Link 1]实现简便、无需修改节点 结构、分摊复杂度低，但可惜最坏情况下的单次操作需要n时间，故难以适用于对可靠性和稳定性要求极高的场合。  
反之，[AVL树][AVL]尽管可以保证最坏情况下的单次操作速度，但需在节点中嵌入平衡因子等标识;更重要的是，删除操作之后的重平衡可能需做多达logn次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。

红黑树即是针对后一不足的改进。通过为节点指定颜色，并巧妙地动态调整，红黑树可保证: **在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。尽管最坏情况下需对多达logn个节点重染色，但就分摊意义而言仅为O(1)个**

当然，为此首先需在AVL树“适度平衡”标准的基础上，进一步放宽条件。实际上，红黑树所采用的“适度平衡”标准，可大致表述为:**任一节点左、右子树的高度，相差不得超过两倍。**

#### 定义与条件 ####

为便于对红黑树的理解、实现与分析，这里不妨下图所示统一地引入n + 1个外部节点，以保证原树中每一节点(现称作内部节点，白色八角形)的左、右孩子均非空—尽管有可能其中之一甚至二者同时是外部节点。  
![这里写图片描述][70]

这些外部节点的引入只是假想式的，在具体实现时并 不一定需要兑现为真实的节点。如此扩展之后的便利 之处在于，我们的考查范围只需覆盖真二叉树。

由红、黑两色节点组成的二叉搜索树若满足以下条件，即为红黑树(red-black tree):

*  (1) 树根始终为黑色
 *  (2) 外部节点均为黑色
 *  (3) 其余节点若为红色，则其孩子节点必为黑色
 *  (4) 从任一外部节点到根节点的沿途，黑节点的数目相等

条件(1)和(2)意味着红节点均为内部节点，且其父节点及左、右孩子必然存在。  
条件(3)意味着红节点之父必为黑色，因此树中任一通路都不含相邻的红节点。

由此可知，在从根节点通往任一节点的沿途，黑节点都不少于红节点。除去根节点本身，沿 途所经黑节点的总数称作该节点的黑深度(black depth)–根节点的黑深度为0，其余依此类推。故条件(4)亦可等效地理解和描述为“所有外部节点的黑深度统一”。  
由条件(4)可进一步推知，在从任一节点通往其任一后代外部节点的沿途，黑节点的总数亦 必相等。除去(黑色)外部节点，沿途所经黑节点的总数称作该节点的黑高度(black height)。 如此，所有外部节点的黑高度均为0，其余依此类推。  
特别地，根节点的黑高度亦称作全树的黑高度，在数值上与外部节点的黑深度相等。

在红黑树与4阶[B-树][B-]之间，存在极其密切的联系; 经适当转换之后，二者相互等价!

具体地，自顶而下逐层考查红黑树各节点。每遇到一个红节点，都将对应的子树整体提升一 层，从而与其父节点(必黑)水平对齐，二者之间的联边则相应地调整为横向。

![这里写图片描述][70 1]

照此理解，此时的关键码也被赋予了对应的颜色。对照红黑 树的条件，(2,4)B-树中的每个节点应包含且仅包含一个黑关键码，同时红关键码不得超过两个。 而且，若某个节点果真包含两个红关键码，则黑关键码的位置必然居中。

与前文介绍二叉平衡树的其他成员的时候一样，接下来将学习在插上，删除的等操作的时候如何保障其红黑树的特性。

#### 红黑树的节点新增 ####

红黑数的新增过程，经调用查找之后，确认目标节点尚不存在。于是，在查找终止的位置x处创建节点，并随即将其染成红色(除非此时全树仅含一个节点)。

现在，对照红黑树的上述四项条件，唯有(3)未必满足，此时x的父亲也可能是红色。

因新节点的引入，而导致父子节点同为红色的此类情况，称作“双红”(double red)。 此时，当前节点x的兄弟及两个孩子(初始时都是外部节点)，始终均为黑色。

将x的父亲与祖父分别记作p和g。既然此前的红黑树合法，故作为红节点p的父亲，g必然存 在且为黑色。g作为内部节点，其另一孩子(即p的兄弟、x的叔父)也必然存在，将其记作u。 以下，视节点u的颜色不同，分两类情况分别处置。

**双红修正-u为黑色**  
![这里写图片描述][70 2]

此时红黑树条件(3)的违反，从B-树角度等效地看，即同一节点不应包含紧邻的红色关键码。

故按如上图(c’)所示，只需令黑色关键码与紧邻的红色关键码互换颜色。从图(c)红黑树的角度看，这等效于按中序遍历次序，对节点x、p和g及其四棵子树，做一次局部“3 + 4”重构（对于“3 + 4”重构，详见：[https://blog.csdn.net/canot/article/details/78946450][AVL]）。  
由于该3+4重构过程中，根节点b最终肯定为黑色，不会导致向上传播的现象。

**双红修正-u为红色**  
节点u为红色的情况。此时，u的左、右孩子非空且均为黑色，其黑高度必与x的兄弟  
以及两个孩子相等。

![这里写图片描述][70 3]

如上图的a，b两种情况。此时红黑树条件(3)的违反，从B-树角度等效地看，即该节点因超过4度而发生上溢。  
从图(c)红黑树的角度来看，只需将红节点p和u转为黑色，黑节点g转为红色，x保持红色。从图(c’)B-树的角度来看，等效于上溢节点的一次分裂。  
如此调整之后局部子树的黑高度复原。然而，子树根节点g转为红色之后，有可 能在更高层再次引发双红现象。 即B-树中的上溢的传播，此时可以等效地将g视作新插入的节点，同样地分以上两类情况如法处置。请注意， 每经过一次这样的迭代，节点g都将在B-树中(作为关键码)上升一层，而在红黑树中存在双红缺陷的位置也将相应地上升两层，故累计至多迭代O(logn)次。若最后一步迭代之后导致原树根的分裂，并由g独立地构成新的树根节点，则应遵 照红黑树条件(1)的要求，强行将其转为黑色。此时，全树的黑高度随即增加一层。

#### 红黑树节点删除 ####

假设删除节点为x。在删除x的过程中，如果x不是叶子节点，在将x与其中序遍历中的后继节点交换。此时x则一定为叶子节点，并且一定无左孩子，假设其删除后的接替节点即右孩子为r。并设p = \_hot为x的父亲。

![这里写图片描述][70 4]

如上图所示，除了其接替者r， x还应有另一个孩子—左孩子w，且w必为(黑色的)外部节点 NULL。  
如图(a)和(a’)所示，若x为红色，则在删除x并代之以r后，条件 (3~4)依然满足;  
反之，若x为黑色， 则要看其替代者r的颜色，如图(b)和(b’)所示，若r为红色，则只需将其翻转为黑色，即可使条件(3~4)重新满足。

然而如图(c)和(c’)所示，若x和r均为黑色，则为使条件(3~4)重新成 立，还需要做略微复杂一些的处理。  
**因某一无红色孩子的黑节点被删除，而导致的此类复杂情况，称作“双黑”(double black) 现象。**

原黑节点x的兄弟必然非空(保证节点到所有外部节点到黑节点数量一致)，将其记作s;  
x的父亲记作p，其颜色不确定(八角形示意)。以下视s和p颜色的不同组合，按四种情况分别处置。

#### 双黑修正—1 ####

![这里写图片描述][70 5]

既然节点x的另一孩子w = NULL，故从B-树角度看节点x被删除之后的情况（上图a’），  
可以等效地理解为: **关键码x原所属的节点发生下溢;**此时，t和s必然属于B-树的同一节点，且该节点就是下溢节点的兄弟。故可参照B-树的调整方法，下溢节点从父节点借出一个关键码(p)， 然后父节点从向下溢节点的兄弟节点借出一个关键码(s)，调整后的效果如图(b’)。

从红黑树的角度(图(b))来看， 上述调整过程等效于，对节点t、s和p 实施“3 + 4”重构。  
此外，根据红黑树与B-树的对应关系不难理解，若这三个节点按中序遍历次序重命名为a、b和c，则还需将a 和c染成黑色，b则继承p此前的颜色。 就上图具体实例而言，也就是将t和p染成黑色，s继承p此前的颜色。注意，整个过程中节点r保持黑色不变。

#### 双黑修正—2 ####

![这里写图片描述][70 6]

节点s及其两个孩子均为黑色时，视节点p颜色的不同，又可进一步分为两种情况。  
先考虑p为红色的情况。如上图所示。

在对应的B-树中，关键码x的删除导致其所属的节点下溢。但因此时关键码s所在节点只有两 个分支，故下溢节点无法从父节点借出关键码(p)。

按照前文的[B-树平衡算法][B-]，此时应如图(b’)所 示，将关键码p取出并下降一层，然后以之为“粘合剂”， 将原左、右孩子合并为一个节点。从红黑树角度看，这 一过程可如图(b)所示等效地理解为: s和p颜色互换。

由图(b)(及其对称情况)可知，经过以上处理，红黑树的所有条件都在此局部得以恢复。另外，由于关键码p原为红色，故如图8.30(a’)所示，在关键码p所属节点中，其左或右必然还有一个黑色关键码(当然， 不可能左、右兼有)–这意味着，在关键码p从其中取 出之后，不致引发新的下溢。至此，红黑树条件亦必在 全局得以恢复，删除操作即告完成。

#### 双黑修正–3 ####

![这里写图片描述][70 7]

接下来，再考虑节点s、s的两个孩子以及节点p均为黑色的情况。 如图(a)所示，在对应的B-树中，因关键码x的删除，导致其所属节点发生下溢。

因此可如图(b’)所示，将下溢节点与其兄弟合并。从红黑树的角度来看，这一过程可如图(b)所示等效地理解为: 节点s由黑转红。

由图(b)可知，经以上处理，红黑树所有条件都在此局部得到恢复。

然而，因s和x在此之前均为黑色，故如图(a’)所示，p原所属的B-树节点必然仅含p这一个关 键码。于是在p被借出之后，该节点 必将继而发生下溢，故有待于后续进一步修正。

从红黑树的角度来看，此时的状态可等效地理解为: 节点p的父节点刚被删除。当然，可以 按照本节所介绍的算法，视具体的情况继续调整。  
实际上稍后总结时将会看出，这也是双黑修正过程中，需要再次迭代的唯一可能。幸运的是， 尽管此类情况可能持续发生，下溢的位置也必然不断上升，故至多迭代O(logn)次后必然终止。

#### 双黑修正-4 ####

最后，考虑节点s为红色的情况。

![这里写图片描述][70 8]

如图a所示作为红节点s的父亲，节点p必为黑色;  
同时，s的两个孩子也应均为黑色。  
于是从B-树的角度来看，只需如图(b’)所示，令关键码s与p互换 颜色，即可得到一棵与之完全等价的B-树。而从红黑树的角度来看， 这一转换对应于以节点p为轴做一次旋转，并交换节点s与p的颜色。

经过这一转换之后，情况已经发生了微妙而本质的变化。仔细观察图(b)不难发现， 在转换之后的红黑树中，被删除节点x(及其替代者节点r)有了一个新的兄弟s’–与此前的 兄弟s不同，s’必然是黑的!这就意味着，接下来可以套用此前所介绍其它情况(1和2)的处置方法，继续并最终完成双黑修正。

[Link 1]: https://blog.csdn.net/canot/article/details/79968748
[AVL]: https://blog.csdn.net/canot/article/details/78946450
[70]: /images/20220526/d91ed45ff5f44acab19d9c0c73cb718d.png
[B-]: https://blog.csdn.net/canot/article/details/79999164
[70 1]: /images/20220526/e9287fcef244453288b81e7534c03869.png
[70 2]: /images/20220526/46b67a1d6abd48abbb5cdbae5bb8b9d7.png
[70 3]: /images/20220526/ab171f1de3d747f5ba9889b5d504e5a5.png
[70 4]: /images/20220526/45d92c888a9044da96a92cb0e4d21e2d.png
[70 5]: /images/20220526/1c7c725b103d40de9bb14ab7344b21b1.png
[70 6]: /images/20220526/eec6672f8d124689ad86fa7bb7d1914e.png
[70 7]: /images/20220526/39f639b448804c33b145ba2f82043cbc.png
[70 8]: /images/20220526/19094070afac438c8d9347551e8baaae.png