红黑树删除与调整

X

ε

Y

γ

α

β

Z

整

C

δ

B

ζ

A

E

除

x的兄弟结点w的右孩子为黑(左孩子为红)置w的左孩子为黑色置w为红色对w作右旋w调整至新位置

D

x ->

Ω

w ->

红

黑

x的兄弟结点w的右孩子为红(左孩子可红可黑)置w与x的双亲结点同色置x的双亲结点为黑色置w的右孩子为黑色对x的双亲结点作左旋x指向根结点

红黑树性质

3.每个叶结点(Nil)是黑色的

new w ->

<- 左旋

y为从树中删除的结点或者移至树内的结点

<- 右旋

删

删除后调整

new x ->

x的兄弟结点w的左右孩子都为黑色置w为红色x上移至其双亲结点

记录被删除结点的颜色

树

2.根结点是黑色的

置x为黑

new x = T.root

x的兄弟结点w为红色置兄弟结点为黑色置双亲结点为红色对双亲结点作左旋w调整至新位置

调