chap13 红黑树

红黑树 算法导论

内容

红黑树性质

红黑树在二叉搜索树的基础上，增加了颜色这一属性，目的是为了控制树的高度
1. 每个结点的颜色要么是黑色，要么是红色
2. 根节点是黑色的
3. 每个叶结点（NIL）是黑色的
4. 红色结点必有两个黑的孩子
5. 每个结点的黑高相等

一个有n个内部节点的红黑树的黑高至多为$2\lg(n+1)$
启发式证明：如果没有红色结点，则红黑树是完全二叉树，沿着一个分支不断增添红结点即可得到结论

基本操作

旋转

1. 旋转操作是一种能够保持二叉搜索树性质的局部操作，它不是局限于红黑树的，换句话说它可能会破坏红黑树的性质
2. 左旋，认右孩子为爸爸，因而条件是有右孩子
3. 右旋，认左孩子为爸爸，因而条件是有左孩子

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

插入

1. 插入操作会破坏红黑树的性质2或4，然而这两种性质不会同时破坏，最多破坏一个。初始时，性质2的破坏只会出现在，z被插入一棵空树并成为根节点；性质4的破坏，则出现在z.p也是红色的，注意到在case1的调整中，z的上升，可能最终会将性质4的破坏转换成2的破坏（也可能转成case2或3）。而2的破坏，只需一个赋值语句即可调整。

2. 对于可能出现的6中情况

   • z的叔结点y是红的———— case1
   • z的叔结点y是黑的
     z是一个右孩子——————case2
     z是一个左孩子——————case3

3. 转化关系：case1可能变成case2或case3，也可能一直循环到变成性质2的破坏；case2会在一次左旋后变成case3

4. 最终，性质2的破坏只需一个赋值操作，出现在fixup过程的末尾；case3需要一次右旋操作。注，直接由case2进行右旋会导致性质5的破坏

rb-insert(T,z)

y = T.nil
x = T.root
while x != T.nil #find the parent of z
    y = x
    if z.key < x.key
        x = x.left
    else x = x.right
z.p = y
if y == T.nil
    T.root = z
esle if z.key < y.key
    y.left = z
else y.right = z
z.left = T.nil
z.right = T.nil
z.color = red
rb-insert-fixup(T,z)

rb-insert-fixup(T,z)

while z.p.color == red #violate the prop4
    if z.p == z.p.p.left
        y = z.p.p.right #uncle node
        if y.color == red                            #case1
            z.p.color = black  
            y.color = balck
            z.p.p.color = red
            z = z.p.p
        else 
            if z = z.p.right                         #case2
                z = z.p
                left-rotate(T,z) #left rotate z.p
            z.p.color = black                        #case3
            z.p.p.color = red
            right-rotate(T,z.p.p)
    else
        same as then clause with "right" and "left" exchanged
T.root.color = black  #fix prop2

删除

1. 如果y是黑色的；删除操作会导致性质2，4，5的破坏，通过双重染色，对性质5的破坏转成了性质1的破坏。具体来说，性质2源于删除的是根结点，而后继是红结点；性质4源于后继的右孩子x和后继的父亲都是红结点所致；性质5是显然的，删去一个非根黑结点必会导致黑高的不等

2. 删除操作分为4种情况

   • x的兄弟w是红的-------------------------------------------case1
   • x的兄弟w是黑的的
     　　　　w的右孩子是黑的
     　　　　　　　　w的左孩子是黑的-----------------------------case2
     　　　　　　　　w的左孩子是红的-----------------------------case3
     　　　　w的右孩子是红的-------------------------------------case4

3. 之所以这么分，主要是为了确定局部中其他点的颜色，case1局部点的颜色是确定的，而其他case则不然，详见原版书中插图。case1经过染色和对x.p左旋后进入后三种情况；case2会导致循环，本质上相当于将双色点x不断上直到根结点；case3通过染色和对w右旋进入case4；case4进行染色和对x.p的左旋后，通过手动设置x指向根结点而终止循环

4. 对rb-delete的分析
   
   • s1：y指向z，x指向y即z的孩子，y-original-color = z.color
   • s2：y指向z的后继，x指向y的右孩子，y-original-color = y.color
   • 先是y，y的作用主要体现在它的original-color这一属性，它会决定是否进入fixup过程，对于situation1来说，所有性质的破坏都源于删去了一个黑结点导致，当然具体违反哪些取决于x；对于situation2来说，由于在最后通过
     y.color = z.color使得z的颜色得意保留，因而所有性质的破坏都源于后继y原本是黑的导致；
   • 其次，对于x，x是作为fixup的参数的。首先作为参数的原因是，红黑树性质的破坏，最为关键的是性质5，因而，fixup的潜在第一步就是将某个结点进行双重染色，而这个结点就是x。原因从y的分析过程可以看出，黑高性质的破坏是从结点x开始的，因而只需对x双重染色即可。清楚了原因之后，我们对于x的选择就明朗了，那就是需要被双重染色的结点就是x需要指向的结点，因而situati1指向z的孩子，situation2指向y的右孩子

这里即使v是哨兵也要指定父亲的原因在于红黑树中T.nil是作为树的叶结点存在的，这是它与chap12中区别
同一分支的transplant过程可以看成是将u结点给砍下来，把v给接进去，砍下来的u，可以供做他用
Transplant(T,u,v)

if u.p == T.nil
    T.root = v
esle if u == u.p.left
    u.p.left = v
else u.p.right = v
 v.p = u.p

rb-delete(T,z)

y = z
y-original-color = y.color
##########################delete situation 1
if y.left == T.nil
    x = z.right
    rb-transplant(T,z,z.right)
else if z.right == T.nil
    x = z.left
    rb-transplant(z,z.left)
 ##########################delete situation 2
 else y = tree-minimum(z.right)
    y-original-color = y.cplor
    x = y.right
    #######################可以参考chap12的过程，较为简便
    if y.p == z
        x.p = y
    else
        rb-transplant(T,y,y.right)
        y.right = z.right
        y.right.p = y
    rb-transplant(T,z,y)
    y.left = z.left
    y.left.p = y
    y.color = z.color #z的颜色得以保留，从而导致下一行对s2的正确
if y-original-color == black
    rb-delete-fixup(T,x)

rb-delete-fixup(T,x)

while x != T.root and x.color == black 
    if x == x.p.left
        w = x.p.right
        if w.color == red
            w.color = black
            x.p.color = red
            ledt-rotate(T,x,p)
            w = x.p.right
        if w.left.color == balck and w.right.color == black
            w.color = red
            x = x.p
        else 
            if w.right.color = black
                w.left.color = black
                w.color = red
                right-rotate(T,w)
                w = x.p.right
            w.color = x.p.color
            x.p.color = black
            w.right.color = black
            left-rotate(T,x.p)
            x = T.root #以终止while循环
    esle
        same as then clause with "right" and "left" exchanged
x.color = black

习题

关于红黑树的一些小性质的补充（to be continued）

1. 13.3-6 可以使用栈，来去掉父指针
2. 13.4-7 先插再删同一个结点，得到的红黑树可能与原来的不一样

13-1 持久动态集合

向树中插入一个关键字k
persistent-tree-insert(T.root t,k)

if t == NIL
    x.key = k
    x.left = x.right = NIL
esle 
    x.key = t.key
    x.left = t.left
    x.right = t.right
    if k < t.key
        x.left = persistent-tree-insert(t.left,k)
    else x.right = persistent-tree-insert(t.right,k)

13-2 红黑树上的连接操作

rb-join(Ty,x,T2)

z.left = Ty
z.right = T2
z.p = Ty.p
z.key = x
if Ty.p.left == Ty
    Ty.p.left = z
else Ty.p.right = z

13-3 AVL树

13-4 treap 树

代码实现

java