红黑树-删除
2019-01-28 17:32:56 0 举报红黑树删除过程分析
作者其他创作
大纲/内容
注意从这里过来的被删节点P已经不是最初的P了
兄弟节点染成父节点颜色，父节点染黑，兄弟节点的同向子节点染黑，以父节点为原点，以X方向旋转，将父节点设置为新的X
p的子节点
P是黑色的
N
兄弟节点是红色的
将兄弟节点染黑，父节点染红，以父节点为原点，以自己为方向旋转
将兄弟节点染红，再把兄弟节点的反向子节点染黑，以兄弟节点为原点，以兄弟节点的方向进行旋转
结果:兄弟节点变为祖父节点，兄弟节点的反向子节点成为了新的兄弟节点
将X染黑
找到P的中序后继节点S，将P的键值替换为S的键值，然后将S设置为被删节点P
Y
将P替换为子节点N，移除P
兄弟节点的反向子节点和兄弟节点调换了位置，兄弟节点一定变成了黑色，并且拥有一个红色的子节点
P
到这里已经推导出P没有子节点
兄弟节点变了
被删节点 P —start
这里所说的反向子节点是指：假如节点X是X父节点的左节点，那么它的右节点就是它的反向子节点，反过来它的左节点就是它的同向子节点，
这里所说的以自己为方向旋转是指：如果X是X父节点的左节点，那么以自己为方向旋转就是左旋，反之就是右旋
平衡红黑树X
结束
X是黑色
兄弟节点的同向子节点为黑色
新的X为之前X的父节点
删除P
X
开始
兄弟节点的两个子节点都为空或者都为黑色
P有一个子节点
到这里已经推导出P没有子节点，并且是红色
P 有两个子节点
将兄弟节点染红，将X的父节点设置为新的X
收藏
收藏
0 条评论
下一页
