@zqbinggong
2018-03-12T19:58:22.000000Z
字数 3962
阅读 970
红黑树
算法导论
红黑树在二叉搜索树的基础上,增加了颜色这一属性,目的是为了控制树的高度
1. 每个结点的颜色要么是黑色,要么是红色
2. 根节点是黑色的
3. 每个叶结点(NIL)是黑色的
4. 红色结点必有两个黑的孩子
5. 每个结点的黑高相等
一个有n个内部节点的红黑树的黑高至多为
启发式证明:如果没有红色结点,则红黑树是完全二叉树,沿着一个分支不断增添红结点即可得到结论
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
对于可能出现的6中情况
转化关系:case1可能变成case2或case3,也可能一直循环到变成性质2的破坏;case2会在一次左旋后变成case3
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
删除操作分为4种情况
之所以这么分,主要是为了确定局部中其他点的颜色,case1局部点的颜色是确定的,而其他case则不然,详见原版书中插图。case1经过染色和对x.p左旋后进入后三种情况;case2会导致循环,本质上相当于将双色点x不断上直到根结点;case3通过染色和对w右旋进入case4;case4进行染色和对x.p的左旋后,通过手动设置x指向根结点而终止循环
这里即使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
向树中插入一个关键字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)
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