红黑树删除与调整
2019-05-22 16:06:11 0 举报红黑树删除
作者其他创作
大纲/内容
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调整至新位置
调
0 条评论
下一页
