红黑树

1. 红黑树

1.1 红黑树的应用场景

红黑树需要具备的性质：

每一个节点或者为红色或者为黑色；
根节点是黑色的；
如果一个节点是红色的，那么其子节点必须是黑色的；
从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。

1.2 红黑树的旋转

1.2.1 左旋

rbtree_rotate_left.jpg

1.2.2 右旋

rbtree_rotate_right.jpg

2. 红黑树的插入

红黑树插入节点

Case1：叔叔节点为红色，

Case2：叔叔节点为黑色，当前节点为父节点的左子树;

Case3：叔叔节点为黑色，当前节点为父节点的右子树；

2.2 循环的停止条件

在2.1小节讨论了红黑树插入节点的三种可能情况，颜色修正、左旋或者右旋之后事情并没有结束，而是将某个节点作为新的当前节点继续迭代。那么什么时候递归可能结束呢？当初学习红黑树很少看到有对这个问题进行讨论，下面我们探讨一下。不难发现，Case-3经过一次调整之后变为父节点的左子树即Case-2的情形。故我们仅需要对于前两种情况进行讨论。

对于Case-1，经过一次调整，祖父节点着色为黑色且作为新的当前节点；

image

rbtree_insert_0.jpg

对于Case-2，经过重新着色和旋转，P节点取代了原来G节点的位置且为黑色。无论原来G节点的父节点为黑色还是红色，都不会违反红黑树的定义。因此无需继续调整。在上述操作中，我们并没有改变当前节点，当前节点仍为S节点。

rbtree_insert_1.jpg

3. 红黑树的删除

// TODO

待删除的节点没有子节点，直接删除
2）待删除的节点只有一个子节点，则直接删除并将用子节点替代该节点
3）待删除节点有两个子节点，则使用该节点的后继节点代替，并将后继节点作为新的待删除节点，此时待删除节点
伪代码

RB-DELETE(T, z)
if left[z] = nil[T] or right[z] = nil[T]         
   then y ← z                                  // 若“z的左孩子” 或 “z的右孩子”为空，则将“z”赋值给 “y”；
   else y ← TREE-SUCCESSOR(z)                  // 否则，将“z的后继节点”赋值给 “y”。
if left[y] ≠ nil[T]
   then x ← left[y]                            // 若“y的左孩子” 不为空，则将“y的左孩子” 赋值给 “x”；
   else x ← right[y]                           // 否则，“y的右孩子” 赋值给 “x”。
p[x] ← p[y]                                    // 将“y的父节点” 设置为 “x的父节点”
if p[y] = nil[T]                               
   then root[T] ← x                            // 情况1：若“y的父节点” 为空，则设置“x” 为 “根节点”。
   else if y = left[p[y]]                    
           then left[p[y]] ← x                 // 情况2：若“y是它父节点的左孩子”，则设置“x” 为 “y的父节点的左孩子”
           else right[p[y]] ← x                // 情况3：若“y是它父节点的右孩子”，则设置“x” 为 “y的父节点的右孩子”
if y ≠ z                                    
   then key[z] ← key[y]                        // 若“y的值” 赋值给 “z”。注意：这里只拷贝z的值给y，而没有拷贝z的颜色！！！
        copy y's satellite data into z         
if color[y] = BLACK                            
   then RB-DELETE-FIXUP(T, x)                  // 若“y为黑节点”，则调用
return y