红黑树详解

作者: ITsCLG | 来源:发表于2019-11-08 21:29 被阅读0次

作为一名年轻的叫狮，开发斜杠能力，做一名斜杠青年，小编私以为还是很重要的，没有什么工作是绝对的稳定，真正稳定的，是你的才华和能力。这一周，小编在工作之余，上网翻阅了各种资料，认识了一遍红黑树，并把查阅到的这些资料整理归纳了一遍，至少也是一种知识的存档。

一、导论

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，是一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

二、基本性质

在算法导论里，是这样去定义一棵红黑树的：

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点（NIL）是黑色【注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！】

（4）如果一个节点是红色的，则它的子节点必须是黑色的。

（5）对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑色节点【也就是说从根节点（如下图13根节点）到其所有的nil黑节点路径里的黑节点数就是一样的。确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。】

对于红黑树来说，任意节点到空的叶子节点的所有路径中，没有一条路径会大于其他路径的两倍（换句话说就是任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍）

图1

红黑树使用红黑二色进行“着色”，目的是利用颜色值作为二叉树的平衡对称性的检查，只要插入的节点“着色”满足红黑二色的规定，最短路径与最长路径不会相差的太远，红黑树的节点分布就能大体上达至均衡。

三、红黑树的应用

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(logn)，效率非常之高。

例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

四、红黑树的时间复杂度和相关证明

红黑树的时间复杂度为: O(logn)

下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

证明：

“一棵含有n个节点的红黑树的高度至多为2log(n+1)”转换一下就是“高度为h的红黑树，它的包含的内节点个数至少为 2^(h/2)-1个”。

我们只需要证明后面那个命题，即可证明原命题为真；即只需证明“高度为h的红黑树，它的包含的内节点个数至少为 2^(h/2)-1个”。

从某个节点x出发（不包括该节点）到达一个它子孙外部节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x's black height)，记为bh(x)。关于bh(x)有两点需要说明：

第1点：根据红黑树的“特性(5)，即从一个节点到该节点的子孙外部节点的所有路径上包含相同数目的黑节点”可知，从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的！

第2点：根据红黑色的“特性(4)，即如果一个节点是红色的，则它的子节点必须是黑色的”可知，从节点x出发达到叶节点“所经历的黑节点数目”>= “所经历的红节点的数目”。假设x是根节点，则可以得出结论“bh(x) >= h/2”。进而，我们只需证明“高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个”即可。

到这里，我们将需要证明的定理已经由“一棵含有n个节点的红黑树的高度至多为2log(n+1)”转变成只需要证明“高度为h以x为根的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个”。

下面通过"数学归纳法“开始论证高度为h以x为根的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个”。

（1）当树的高度h=0时，内节点个数是0，bh(x) 为0，2^bh(x)-1 也为 0。显然，原命题成立。

（2）考虑x的左右子节点，它们包含的节点个数至少为 2^(bh(x)-1)-1。推导理由如下：对于节点x(x为根节点)，其黑高度为bh(x)。对于节点x的左右子树，当它们为红色时，黑高度为 bh(x)；当它们为黑色时，黑高度为bh(x)-1。因此，x的左右子节点所包含的节点个数至少为2^(bh(x)-1)-1（因为黑高度最少为bh(x)-1）。

（3）根据（2），我们已知“x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2^(bh(x)-1)-1 个”；所以，节点x所包含的节点至少为 (2^(bh(x)-1)-1 ) + (2^( bh(x)-1)-1) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2^bh(x)-1。

因此，原命题成立。

由（1）、（2）得出，“高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个”。

因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

因此，从根节点到任意节点最多经历2log(n+1)步，因此红黑树的时间复杂度为O(lgn)。

五、树的平衡性的修正方法

红黑树主要的特征：

① 节点都有颜色；

② 在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则。

首先第一个特征很好解决，在节点类中添加一个数据字段，例如boolean型变量，以此来表示节点的颜色信息。第二个特征比较复杂，红黑树有它的几个规则，如果遵循这些规则，那么树就是平衡的。

在红黑树中插入的节点都是红色的，这不是偶然的，因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小。原因是：插入黑色节点总会改变黑色高度（违背规则4），但是插入红色节点只有一半的机会会违背规则3。另外违背规则3比违背规则4要更容易修正。红黑树在插入后可能会导致树的不平衡，所以要进行分析，看是否需要变色，左旋，右旋。

1、变色

改变节点颜色比较容易理解，因为它违背了规则3。

2、左旋

左旋是将E的右子树绕E逆时针旋转，使得E的右子树成为E的父亲，同时修改相关节点的引用，旋转之后，要求二叉查找树的属性依然满足。

左旋（RR）

左旋有个很萌萌哒的动态示意图，可以方便理解：

左旋动图

3、右旋

右旋是将S的左子树绕S顺时针旋转，使得S的左子树成为S的父亲，同时注意修改相关节点的引用，旋转之后要求仍然满足搜索树的属性。

右旋（LL）

当然咯，右旋也有个萌萌的动态图：

右旋动图

六、红黑树的插入

① 插入节点为根节点

由于原树为空，所以只会违反红黑树的规则2，所以只要把根节点涂黑即可；

② 插入节点的父节点是黑色的

那不会违背红黑树的规则，什么也不需要做；

③ 当前节点的父节点是红色，且当前节点的父节点的另一个节点（叔叔节点）也是红色。

处理策略：

（01）父节点设置黑色

（02）叔叔节点设置黑色

（03）祖父节点设置红色

（04）设置祖父节点为当前节点

（5）未完，然后又将爷爷节点当作插入节点看待，一直进行上述操作。直到当前节点为根节点，然后将根节点变成黑色。

④当前节点的父节点是红色，叔叔节点是黑色

1）父亲节点为爷爷节点的左孩子，新插入节点为父节点的左孩子（左左）

处理策略：

（01）将父亲节点和爷爷节点颜色互换（父节点变为黑色，爷爷节点变为红色）

（02）设祖父节点为当前节点，对当前节点进行一次右旋

2）父亲节点为爷爷节点的右孩子，新插入节点为父节点的右孩子（右右）

处理策略：

（01）将父亲节点和爷爷节点颜色互换（父节点变为黑色，爷爷节点变为红色）

（02）对爷爷节点进行一次左旋

3）父亲节点为爷爷节点的左孩子，新插入节点为父节点的右孩子（左右）

处理策略：

对父亲节点进行一次左旋，然后就变成了情况1），按照情况1）再进行处理

4）父亲节点为爷爷节点的右孩子，新插入节点为父节点的左孩子（右左）

处理策略：

对父亲节点进行一次右旋，然后就变成了情况2），按照情况2）再进行处理

接下来，我们通过一个例子来看看如何通过插入数据来生成一棵红黑树。这里，我们插入的数据为275、711、260、515、442、800、900、50、270、20、30。

插入275，满足①

根节点，涂为黑色。

插入275

插入711，满足②

插入711

插入260，满足②

插入260

插入515

插入515

满足情况③

第一步设置父节点711设置黑色，第二步叔叔节点260设置黑色、第三步设置祖父节点275设置红色，第四步设置祖父节点为当前节点。

调整1

由于当前节点275为根节点，修改为黑色。

调整2

插入442

插入442

满足情况④中的1），第一步将父亲节点515和爷爷节点711颜色互换（父节点变为黑色，爷爷节点变为红色），然后对爷爷节点711进行一次右旋。

调整1

调整2

插入800

插入800

满足情况③，第一步设置父节点711设置黑色，第二步叔叔节点442设置黑色、第三步设置祖父节点515设置红色，第四步设置祖父节点515为当前节点。

调整

插入900

插入900

满足情况④中的2）

第一步将父节点800与祖父节点711的颜色进行交换。

第一步

第二步设置祖父节点711作为新的当前节点，以当前节点为支点左旋。调整得到下图

第二步

插入50，270，保持不变

插入50、270

插入20

插入20

满足情况③，进行调整如下：

调整

插入30

插入30

满足情况④中的3），第一步对父亲节点20进行一次左旋，得到下图

步骤1

满足情况④中的1），第一步将父亲节点30和爷爷节点50颜色互换（父节点变为黑色，爷爷节点变为红色），然后对爷爷节点50进行一次右旋。

步骤2

步骤3

插入过程完毕。

七、红黑树的删除

相较于插入操作，红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子。

删除一个节点有以下四种情况：

① 删除的节点没有孩子

② 删除的节点只有左子树

③ 删除的节点只有右子树

④ 删除的节点拥有左子树和右子树

其实只有上面前三种情况，对于第④种情况，可以找到待删除节点的直接后继节点，用这个节点的值替代待删除节点，接着情况转变为删除这个直接后继节点，情况也变为前三种之一。

对于情况②和③，也就是待删除的节点只有左子树或这有右子树的情况，有很多组合在红黑树中是不可能出现的，因为他们违背了红黑树的性质。

情况②和③中不存在的情况有（其中D表示要删除的节点，DL和DR分别表示左子和右子）：

不存在的情况1

上述情况都违背了红黑树的性质5【对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑色节点】。

不存在的情况2

上述两种情况明显违背了性质4【如果一个节点是红色的，则它的子节点必须是黑色的】。

我们把删除的节点分为两大类：删除红色节点和黑色节点。

1、删除红色节点

1.1 删除红色的叶子节点（D表示待删除的节点，P表示其父亲节点）

1.1

上面这两种情况其实处理方式都一样，直接删除D就好！

1.2 删除的红色节点只有左子树或只有右子树

1.2

上述两种情况明显违背了红黑树的性质4【如果一个节点是红色的，则它的子节点必须是黑色的】，根本不存在这种情况。

1.3 删除的红色节点有左右子树（或左右孩子）

1.3

假设删除节点为X，先找到该节点的左孩子节点DL，若DL为叶子节点，则直接交换DL与X的值，再删除DL节点；否则从DL的后继节点中找到最大值节点S【从右子树查找】，交换S节点与要删除节点X的数值，再删除新的S节点【此时的S节点一定是叶子节点】，如果该S节点为红色，直接删除，否则进行下一步的情况判断。

2、删除黑色节点

2.1删除的黑色节点有左右子树

假设删除节点为X，找到该节点的左孩子节点DL，若DL为叶子节点，则直接交换DL与X的值，再删除DL节点；否则从该节点DL的后继节点中找到最大值节点S【从右子树查找】，交换S节点与要删除节点X的数值，再删除新的S节点【此时的S节点一定是叶子节点】，如果该S节点为红色，直接删除，否则进行下一步的情况判断。

2.2删除的黑色节点仅有左子树或者仅有右子树

排除上述的情况，只存在以下两种情形：

2.2

处理方法：用D的孩子（左或右）替换D，并将D孩子的颜色改成黑色即可（因为路径上少了一个黑节点，所已将红节点变成黑节点以保持红黑树的性质）。

2.3删除黑色的叶子节点

对于这种情况，相对复杂，我们可以分为5种情况来讨论：

2.3.1：兄弟节点为黑色，且远侄子节点为红色。

① D为左孩子对的情况，这时D的远侄子节点为S的右孩子。

2.3.1①

没有上色的节点表示黑色红色均可，注意如果SL为黑色，则SL必为NULL节点。

这个时候，如果我们删除D，这样经过D的子节点（NULL节点）的路径的黑色节点个数就会减1，但是我们看到S的孩子中有红色的节点，如果我们能把这棵红色的节点移动到左侧，并把它改成黑色，那么就满足要求了，这也是为什么P的颜色无关，因为调整过程只在P整棵子树的内部进行。

调整过程为，将P和S的颜色对调，然后对P树进行类似AVL树RR型的操作，最后把SR节点变成黑色，并删除D即可。

2.3.1① 左旋调整

② D为右孩子的情况，此时D的远侄子为S的左孩子。

2.3.1②

同样，将P和S的颜色对调，然后再对P树进行类似AVL树LL型的操作，最后将SL变成黑色，并删掉D即可。结果如下图：

2.3.1 ② 右旋调整

2.3.2：父亲节p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色的情况。

2.3.2

如果删除D，那经过P到D的子节点NULL的路径上黑色就少了一个，这个时候我们可以把P变成黑色，这样删除D后经过D子节点（NULL节点）路径上的黑色节点就和原来一样了。但是这样会导致经过S的子节点（NULL节点）的路径上的黑色节点数增加一个，所以这个时候可以再将S节点变成红色，这样路径上的黑色节点数就和原来一样啦！

所以做法是，将父亲节点P改成黑色，将兄弟节点S改成红色，然后删除D即可。如下图：

2.3.2调整

2.3.3：父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色的情况

2.3.3

方法是将兄弟节点S的颜色改成红色，这样删除D后P的左右两支的黑节点数就相等了，但是经过P的路径上的黑色节点数会少1，这个时候，我们再以P为起始点，继续根据情况进行平衡操作（这句话的意思就是把P当成D（只是不要再删除P了），再看是那种情况，再进行对应的调整，这样一直向上，直到新的起始点为根节点）。结果如下图：

2.3.3调整

2.3.4：兄弟节点S为黑色，远侄子节点为黑色，近侄子节点为红色

① D为左孩子的情况，此时近侄子节点为S的左孩子

2.3.4 ①

做法是，将SL右旋，并将S和SL的颜色互换，这个时候就变成了情况2.3.1中的 ①。

2.3.4 ①调整

根据2.3.1中的 ①再进行节点的删除。

② D为右孩子的情况，此时近侄子节点为S的右孩子

2.3.4 ②

做法是将S和SR颜色对调，然后对SR进行左旋操作，这样就变成了情况2.3.1中的② ，结果如下图：

2.3.4 ②调整

根据2.3.1中的② 再进行节点的删除。

2.3.5：待删除节点D的兄弟节点S为红色

① D是左节点的情况

2.3.5 ①

调整做法是将父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，然后将P树进行AVL树种的RR型操作，结果如下图：

2.3.5 ①调整

这个时候我们会发现，D的兄弟节点变成了黑色，这样就成情况2.3.2。

② D是右节点的情况

2.3.5 ②

将P和S的颜色互换，也就是将P变成红色，将S变成黑色，然后对P进行类似AVL树的LL操作。结果如下图：

2.3.5 ②调整

此时D的兄弟节点变成了黑色，这样就成了我们情况2.3.2。

我们来看一个具体的删除例子：

红黑树例子

删除节点442

节点442为左孩子。兄弟节点800为黑色，且远侄子节点900为红色。满足2.3.1中的情况①，调整过程为，将父节点515和兄弟节点800的颜色对调，然后对父节点515进行RR型的操作，也就是左旋。最后把远侄子节点900变成黑色，并删除D即可。结果如下：

删除节点442

删除节点270

节点270为右孩子。兄弟节点30为黑色，且远侄子节点20为红色。满足2.3.1中的情况②，D为右孩子的情况。同样，将父节点260和兄弟节点30的颜色对调，然后再对以父节点260为根的树进行LL型的操作，也就是右旋。最后将远侄子节点20变成黑色，并删掉节点270即可。结果如下图：