红黑树删除节点
2020-12-09 16:52:49 0 举报红黑树节点删除自平衡
作者其他创作
大纲/内容
3
删除节点
7
33
5
30
19
38
8
p
15
13
18
right
sib
if (p == p.parent.left) p.parent.left = null;
1. p的颜色为黑色 且 兄弟节点的颜色为黑色兄弟节点的右子节点为黑色2. 设置sib节点颜色为红色 3. 设置sib节点的左子节点为 黑色4. sib节点右旋
43
左旋 替换节点父节点19
1. 兄弟节点颜色 设置为 父节点颜色2.父节点的颜色 设置为 黑色3. 兄弟节点右子节点 设置为 黑色
s
x
NIL
删除18，没有孩子节点
兄弟节点为黑色 并且兄弟节点的两个子节点都是黑色1. 将兄弟节点设置为 红色2. 将p的父节点作为 替换节点3. 将p 颜色设置为黑色
x=root
parent
找到待删除节点19。 如果节点19左右孩子都非空 ，找到节点19的 后继节点为30如果后继节点的左子节点非空 左子节点为替换节点 否则右子节点为替换节点
删除节点 5，有左右孩子节点
0 条评论
下一页
