第十三章 红黑树

红黑树可以理解为平衡特质的二叉搜索树。

红黑树的特质：

1. 每个节点都有颜色，红色或者黑色
2. 根节点是黑色的
3. 每个叶节点（NIL）是黑色的
4. 如果一个节点是红色的，那么他的俩个子节点是黑色的
5. 对每个节点，从该节点开始到其所有叶子节点的简单路径上的黑色阶段数目相等
   这样做的好处是可以控制树的高度，增加树的访问效率。

旋转

旋转的目的是为了平衡树，减少树的高度。旋转分为左旋和右旋。

左旋

左旋x节点
left-rotate(T,x)
y = x.right
x.right = y.left
if y.left != T.nil
  y.left.p = x
y.p = x.p
if x.p == T.nil
  T.root = y
else if x = x.p.left
  x.p.left = y
else x.p.right =y
y.left = x
x.p =y

右旋

右旋x节点
right-rotate(T,x)
y = x.left  
x.left = y.right   
if y.right != T.nil
  y.right.p = x
y.p = x.p
if x.p == T.nil
  T.root = y
else if x.p.right = x
  x.p.right = y
else x.p.left = y
y.left = x
x.p = y

插入

向红黑树中插入新的结点。具体做法是，将新结点的 color 赋为红色，然后以二叉排序树的插入方法插入到红黑树中去。之所以将新插入的结点的颜色赋为红色，是因为：如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑结点，这个是很难调整的。但是设为红色结点后，可能会导致出现两个连续红色结点的冲突，那么可以通过颜色调换和树旋转来调整，这样简单多了。

接下来，讨论一下插入以后，红黑树的情况。设要插入的结点为N，其父结点为P，其 祖父结点为G，其父亲的兄弟结点为U（即P和U 是同一个结点的两个子结点）。如果P是黑色的，则整棵树不必调整就已经满足了红黑树的所有性质。如果P是红色的（可知，其父结点G一定是黑色的），则插入N后，违背了红色结点只能有黑色孩子的性质，需要进行调整。

调整时分以下三种情况：

第一、N的叔叔U是红色的。将P和U重绘为黑色并重绘结点G为红色。现在新结点N有 了一个黑色的父结点P，因为通过父结点P或叔父结点U的任何路径都必定通过祖父结点G， 在这些路径上的黑结点数目没有改变。但是，红色的祖父结点G的父结点也有可能是红色 的，这就违反了性质3。为了解决这个问题，我们在祖父结点G递归向上调整颜色。如图2.14

image

第二、N的叔叔U是黑色的，且N是左孩子。对祖父结点G 的一次右旋转; 在旋转产生的树中，以前的父结点P现在是新结点N和以前的祖父节点 G 的父结点，然后交换以前的父结点P和祖父结点G的颜色，结果仍满足红黑树性质。如图 2.15。在(b)中，虚线代表原来的指针，实线代表旋转过后的指针。所谓旋转就是改变图中所示的两个指针的值即可。当然，在实际应用中，还有父指针p也需要修改，这里为了图示的简洁而省略掉了。

image

第三、N的叔叔U是黑色的，且N是右孩子。我们对P进行一次左旋转调换新结点和其父 结点的角色，就把问题转化成了第二种情况。如图 2.16所示。

image

insert(T,z)
  y =T.nil  待插入位置
  x = T.root
  while  x != T.nil
    y = x
    if z.key < x.key
       x = x.left
    else x = x.right
  z.p = y
  if  y == T.nil
    T.root = z
  else if z.key < y.key
    y.left = z
  else y.right = z
  z.left = T.nil
  z.right = T.nil
  z.color = red
  fixup(T,Z)  旋转，保持红黑树特性

红黑树的调整

fixup(T,z)
while z.p.color == red
        if  z.p == z.p.p.left  挂在左子树
            y = z.p.p.right
           if   y.color == red   //case1 叔叔节点是红色
               z.p.color = black
               y.color = black
               z.p.p.color = red
               z = z.p.p
        else if z = z.p.right   //case2 叔叔节点是黑色， 在Z 挂在右子树上
                z = z.p
                left-rotate(T,z)  // 左旋z的父节点
        z.p.color = black
        z.p.p.color = red
        right-rotate(T，z.p.p)
    else  //相同的情况处理下右子树
T.root.color = black

删除

如果需要删除的结点有两个孩子，我们的做法是找到这个结点的中序后继，将后继结点中的数据拷贝至待删除结点，然后删除后继结点。而后继结点必然最多只有一个子结点，这样我们就把删除两个孩子的结点转为删除一个孩子的结点。在删除的过程中，我们只关心树是否仍然保持红黑树的性质，数据是否组织正确，而不关心这个结点是最初要删除的结点还是我们从中复制出值的那个结点。

接下来，我们只讨论删除只有一个儿子的结点，如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子。这里，体现出来，在红黑树里特别指定叶子结点为NIL结点的作用，NIL结点经常可以充当正常结点使用以使得算法的表达更加容易。

如果我们删除一个红色结点，它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏属性2和3。通过被删除结点的所有路径只是少了一个红色结点，这样可以继续保证属性4。另一种简单情况是在被删除结点是黑色而它的儿子是红色的时候。如果只是去除这个黑色结点，用它的红色儿子顶替上来的话，会破坏属性4，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持属性4。这是比较简单的两种情况，我们不再讨论。

现在，需要详细讨论的就是如果待删除结点和它的子结点都是黑色的时候，这种比较复杂的情况。有些参考资料上为了表达形式上的简洁，把要讨论的情况分成了四类或者五类，而我认为，把情况细分为六类是比较合理的，这样更利于理解。而且不同于其他的讲解的地方是，我在这里调整了这六种情况的排序。先讲解最简单的，最后讲最复杂的，而不是追求形式上完善，这一点希望读者能够理解。

先来约定涉及到的结点的名称。我们先用待删除结点的孩子代替待删除结点，并且记这个孩子为N，记它的新的父结点为P，它的兄弟结点，也就是父结点的另外一个孩子为S， 记S的左孩子为[图片上传失败...(image-8fb4d-1618992889794)]

，记S的右孩子为[图片上传失败...(image-d3cb99-1618992889794)]

。

情况一。N是新的根。在这种情况下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所有属性都保持着。

情况二。P为红色，S和S的两个孩子都是黑色的。将P置为黑色，S置为红色。这样，不经过N的路径上的黑色结点数目并没有发生变化，而经过N结点的路径上黑色结点的数目 增加了1，刚好添补了这条路径上删除的黑色结点。所以红黑树又重新达到了平衡。

image

情况三。S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情况下我们在N的父亲上做左旋转，这样S成为N的父亲和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以属性3 没有被违反。但是，N现在增加了一个黑色祖先: 要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。此时，如果一个路径不 通过N，则有两种可能性:

1. 它通过N 的新兄弟。那么它以前和现在都必定通过S 和N 的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
2. 它通过N 的新叔父，S 的右儿子。那么它以前通过S、S 的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和 S 的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。

在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了属性4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色

image

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

image

情况五。S是红色。在这种情况下我们在N的父亲上做左旋转，把红色兄弟转换成N的 祖父。我们接着对调N的父亲和祖父的颜色。尽管所有的路径仍然有相同数目的黑色节点，现在N有了一个黑色的兄弟和一个红色的父亲，所以我们可以接下去按二、三或四情况来处 理。N它的新兄弟SL是黑色，因为它未旋转前是红色S的一个儿子。

image

情况六。N的父亲、S和S的儿子都是黑色的。在这种情况下，我们简单的重绘S为红 色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。 因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。 但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反属性3。要修正这个问题，我们要从情况一开始，在P上做重新平衡处理。

image

好了。今天就到这里了。大家自己画画看。下节课，我们讲具体的代码实现