[关闭]
@zqbinggong 2018-03-12T19:58:22.000000Z 字数 3962 阅读 970

chap13 红黑树

红黑树 算法导论

内容


红黑树性质

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

一个有n个内部节点的红黑树的黑高至多为
启发式证明:如果没有红色结点,则红黑树是完全二叉树,沿着一个分支不断增添红结点即可得到结论


基本操作

旋转

  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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注