红黑树-白红宇

红黑树

阅读量：7205 次

发布时间：2019-06-29

本文共 4491 字，大约阅读时间需要 14 分钟。

一、本文内容

以一种简明易懂的方式介绍红黑树背后的逻辑实现2-3-4树，以及红黑树的插入、删除操作，重点在2-3-4树与红黑树的对应关系上，并理清红黑树相关操作的来龙去脉。抛弃以往复杂的实现，而分析红黑树的一种简单实现LLRB。

二、算法应用

红黑树，给人以强烈的第一听觉冲击力——红与黑，好像很高端的感觉。事实上的确如此，红黑树是一种高级数据结构，在C++、Java的标准库里作为set、map的底层数据结构实现，以及linux中进程的公平调度。

三、2-3-4树

标题是红黑树，为什么讲2-3-4树？因为红黑树就是2-3-4树的一种等价形式，更准确地来说，我们用红黑树来完成2-3-4树的各种操作（如插入、删除）。原因就是2-3-4树的实现即维护太麻烦。所以理解2-3-4树才能真正理解红黑树。而历史就是这么发展的，了解过去，现在的一切才有了意义。算法导论关于红黑树这一节就忽略了这一点，让人知其然而不知其所以然。

OK，暂时先忽略复杂的红黑树，从简单的2-3-4树开始。

1、定义

2-3-4树是一种泛化的BST，它的每个结点允许1,2或者3个键(key)，那么对应的有三种结点：

2-node：一个key，两个孩子；

3-node：二个key，三个孩子；

4-node：三个key，四个孩子。

注：k-node表示有k个链接（link）。泛化的BST还有2-3树，B树等。

从图中可以看出2-3-4树的另一个性质：它是完全平衡的（等高），即从根结点到叶子结点距离相等。

2、插入操作

2-3-4树本身就是一种查找树（中序遍历有序），故其查找操作同二叉查找。

2-3-4树的插入操作类似二叉查找树，先是查找操作失败（从根结点查找到叶子结点），然后在底部的叶子结点插入。

因为2-3-4树的结点有三种类型，所以操作有点差异。对于2-node和3-node，分别直接插入可变成3-node，4-node；但是对于4-node若直接插入则违反了定义。在4-node插入之前，先分裂4-node成2个2-node，再将待插入的key插入对应的2-node。如下图，H查找失败，在H插入4-node（由三个key F、G、J组成）之前，先对该4-node分裂（将三个key的中间值提上父节点，剩余的二个key分别作为中间key的左右孩子），然后再将H插入2-node J中。这样操作的结果是查找到达底部叶子结点时，始终是2-node或者3-node。

插入算法思想：自下而上的算法由原作者Bayer在1972年提出，自上而下的算法由Guibas-Sedgewick（红黑树这个名字来源于他们）在1978年提出，然后30年后也就是2008年Sedgewick教授又改进了红黑树的操作，也就是后面要介绍的LLRB。

自上而下的算法思路是，从根结点向下的查找过程中，遇到4-node就分裂，最后在底部的叶子结点插入。

那么为什么遇到4-node就分裂呢？4-node不是2-3-4树的一种合法结点类型吗？

答案可以从后面LLRB的算法思路可以得出。

因为遇到4-node就分裂就保证了当前结点不是4-node，则分裂孩子的4-node有两种情形：

分裂4-node的case 1

分裂4-node的case 2

注：上面的变换在树中任意位置都成立。

下面两张图是完整的插入过程（只有分裂结点类型为4-node的根结点才会导致树高增1）：

3、平衡性分析

2-3-4树的树高在最坏情况下为lgN（所有结点都是2-node型），最好情况下为lg4 N = 1/2 lgN（所有结点都是4-node型），2-3-4树的查找、插入操作都是lgN。

四、红黑树

终于到了高富帅——红黑树。。。

从2-3-4树的介绍可以看出，对2-node、3-node、4-node的不同数据类型进行转换，但所涉及的大部分任务使用这种直接的表示方法来实现并不方便。所以可以用

一种统一的方式完成转换，而只需很小的开销。这就是红黑树存在的意义，既有BST的标准搜索过程，又有2-3-4树的简单插入平衡过程。

下面介绍LLRB（Left-leaning red-black trees），而不是标准的红黑树。

1、定义

LLRB有三个特点：

（1）用BST来表示2-3-4树；

（2）用红边(红链接)来连接2-node来表示3-node和4-node（如下图）；

（3）3-node必须是向左倾斜的（两者的大者作为根）。

LLRB相对于标准的RB多了特点3，在标准的RB中右向倾斜的红链接是允许的。对于特点2，在物理上用一个bit（红或黑）来存储以表示指向该结点的红链接。

红链接来连接3-node或者4-node的内部key，而黑链接则连接外部的key；为了理解，可以消除红链接并将它们连接的结点都折叠起来（即将看做红链接连

接的点缩为一个点），则可以看出黑链接个数不变。

2-3-4树与红黑树是一一对应的关系

且上下关系中不允许2个连续的红边

由特点3可以推出LLRB的一个特性，红黑树与2-3-4树一一对应。

2、插入算法

同样地，在LLRB中查找操作同BST。

在插入之前要知道一个操作：旋转。它有两种情况：左旋，右旋。

左旋右旋

插入算法思路：即前面介绍的2-3-4树

具体实现时，插入一个结点时，始终是红结点，即用红边链接该结点。对于2-node、3-node直接插入（k-node有k个插入点），如违反上面的左红链接和连续的红链接，则旋转作调整。对于4-node（左右都为红链接），先分裂，物理实现是一个翻转（左右红链接变黑，父链接变红）。

2-node插入的两种case

3-node插入的三种case

4-node分裂操作

由4-node的分裂可知黑高度不变，分裂操作即翻转在图片上对应为红链接向上传递。

在介绍2-3-4树时，4-node分裂操作有两种情况，4-node的parent是2-node和3-node；再结合k-node有k个插入点，则总共有6种情况。

4-node的分裂case 1

4-node的分裂case 2

看了上面两幅图后，也许会让人觉得红黑树太复杂了，这么多case，其实不然，在LLRB实现中只有两种操作：旋转、翻转。旋转的目的是保持平衡，翻转的目的是分裂4-node。

看了下面的LLRB插入算法，你就会明白上面4-node的翻转、旋转其实是分开的两个过程（翻转自上而下，旋转自下而上），只是为了统一这个完整的过程而画在了一起，才会有那么多case。

LLRB的插入算法：

首先结合2-3-4树的插入算法思路，先自上至下查找（遇到4-node则翻转），然后在底部叶子结点插入，因为在自上至下的过程中，可能会产生不满足LLRB的性质的情况，故插入结点后需要自下至上调整以恢复LLRB性质。

下图是插入算法的核心代码，第2是分裂即翻转，第1是插入操作，第3、4是调整。

从插入算法可以看出，如果自下而上再分裂4-node，则会出现它的parent也可能是4-node，祖父结点也可能是4-node；我们可以一直向上分裂，这也正是上面提到的自下而上的思路（原作者：Bayer）；而更简单的方法是，在沿树向下的过程中，遇到4-node就分裂，这也正是自上而下与自下而上的区别。