数据结构之红黑树

1.简介

红黑树是一种自平衡二叉查找树（不是平衡二叉树，只不过红黑树近似于平衡的状态）,它相对于二叉查找树性能会更加高效(查找、删除、添加等操作需要O(log n),其中n为树中元素的个数),但实现较为复杂(需要保持自身的平衡)。

红黑树的规则：

1. 每个节点要么是红色，要么是黑色
2. 根节点是黑色
3. 所有叶节点(NIL)都是黑色
4. 如果一个节点是红色，那么它的两个孩子都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任意一个节点出发，到达其后代NIL节点的路径中都包含相同个数的黑节点

红黑树

图中每个节点附带一个整形数值，表示的是此节点的黑高度（从该节点到nil节点中包含的黑结点数，用 bh(x) 表示（x 表示此结点）），nil 的黑高度为 0，颜色为黑色。

为什么红黑树比二叉搜索树查找效率高呢？
因为根据红黑树5个规则可以避免二叉查找树退化成单链表的情况。但是，仅仅避免这种情况还不够，这里还要考虑某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长，那么，在对这些路径上的及诶单进行增删查操作时，效率也会大大降低。这个时候性质4和性质5用途就凸显了，有了这两个性质作为约束，即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。原因如下：
当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。

2.插入操作

红黑树的插入操作与二叉搜索树的一致，将新插入的节点初始化，颜色设置为红色后插入到指定位置，插入前有几种情形

接下来，将分析插入红色节点后红黑树的情况。假设要插入的节点为 N，N 的父节点为 P，祖父节点为 G，叔叔节点为 U。插入红色节点后(要被插入的节点都会被设置为红色)，会出现5种情况，分别如下：

情形1：

简单情形，插入的新节点 N 是红黑树的根节点，这种情况下，我们把节点 N 的颜色由红色变为黑色。

情形2：

简单情形，N 的父节点是黑色，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

情形3：

N 的父节点是红色（节点 P 为红色，其父节点必然为黑色），叔叔节点 U 也是红色。由于 P 和 N 均为红色，此时需要进行调整。这种情况下，先将 P 和 U 的颜色染成黑色，再将 G 的颜色染成红色。但需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整。绿色的节点代表任何节点，这里的a节点就是空节点（nil）

情形4：

N 的父节点为红色，叔叔节点为黑色。N 是 P 的左孩子，且节点 P 是 G 的左孩子。此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色。绿色的节点代表任何节点

情形5：

N 的父节点为红色，叔叔节点为黑色。节点 N 是 P 的右孩子，且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋，调整 N 与 P 的位置。然后G右旋。把N变为黑色。绿色的节点代表任何节点，这里的节点b就是空节点（nil）

3.删除操作

红黑树的删除操作分成2个部分：
1.按照二叉搜索树的删除逻辑一样删除节点。
2.重新调整删除节点后的树，使之重新成为红黑树。

在二叉查找树删除节点时，分为 3 种情况：

• 若该删除节点本身是叶子节点，则可以直接删除；
• 若只有一个孩子节点（左孩子或者右孩子），则直接让其孩子节点顶替该删除节点；
• 若有两个孩子结点，则找到该节点的后继节点，用后继节点的值替换删除节点，然后删除后继节点。

以上三种情况最终都需要删除某个节点，此时需要判断删除该节点是否会破坏红黑树的性质。判断的依据是：
1.如果删除结点的颜色为红色，则不会破坏。
2.如果删除结点的颜色为黑色，则肯定会破坏红黑树的第 5 条性质，此时就需要对树进行调整。
删除红色节点比较简单，下面看看个例子：

下面我们讨论删除黑色节点的情况
下面我们讨论删除黑色节点的情况
下面我们讨论删除黑色节点的情况

第一种简单情况：

被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。

第二种复杂情况：删除的节点和它的儿子二者都是黑色

讨论前我们假设节点之间的关系，删除x后，被N替换，这里的x最多只有一个孩子，为什么？因为当我们删除含有一个节点的情况满足，当我们删除一个节点有2个孩子时，可以转换为删除这个节点的后继几点，那么该后继节点最多也就只有一个孩子（还是右孩子）。

• 情形1：
  新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合。

  
  

• 情形2：
  S 为红色，其他节点为黑色。这种情况下可以对 N 的父节点进行左旋操作，然后互换 P 与 S 颜色。但这并未结束，还需要对S节点递归检查。

  
  

• 情形3：
  N 的父节点，兄弟节点 S 和 S 的孩子节点均为黑色。这种情况下可以简单的把 S 染成红色，所有经过 S 的路径比之前少了一个黑色节点，这样经过 N 的路径和经过 S 的路径黑色节点数量一致了。但经过 P 的路径比不经过 P 的路径少一个黑色节点，此时需要从情况一开始对 P 进行平衡处理。

  
  

• 情形4：
  S和它的子节点都是黑色的,而P为红色.这种情况下只需要将S与P的颜色进行交换

  
  

• 情形5：
  S为黑色,它的左子节点为红色,右子节点为黑色.这种情况下,我们在S上做右旋转,这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个右儿子是红色的黑色兄弟，所以我们进入了情形6。N和P都不受这个变换的影响。

  
  

• 情形6：
  S 为黑色，S 的右孩子为红色。N 的父节点颜色可红可黑，且 N 是其父节点左孩子。这种情况下，我们对 P 进行左旋操作，并互换 P 和 S 的颜色，并将 S_R 变为黑色。因为 P 变为黑色，所以经过 N 的路径多了一个黑色节点，经过 N 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径，则有以下两种情况:

• 该路径经过 N 新的兄弟节点 S_L ，那它之前必然经过 S 和 P。而 S 和 P 现在只是交换颜色，对于经过 S_L 的路径不影响。

• 该路径经过 N 新的叔叔节点 S_R，那它之前必然经过 P、 S 和 S_R，而现在它只经过 S 和 S_R。在对 P 进行左旋，并与 S 换色后，经过 S_R 的路径少了一个黑色节点，性质5被打破。另外，由于 S 的颜色可红可黑，如果 S 是红色的话，会与 S_R 形成连续的红色节点，打破性质4（每个红色节点必须有两个黑色的子节点）。此时仅需将 S_R 由红色变为黑色即可同时恢复性质4和性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。）。
  

  

总结：
红黑树虽然定义复杂，但是它的限制条件是相对AVL宽松的。所以在进行插入删除操作的时候出现违反限制条件的状况较少，因而重平衡操作出现的机会比AVL少。基于上述原因，许多需要进行频繁删插操作的场景都使用来红黑树：