红黑树删除节点
2019-08-23 10:09:03 0 举报
treemap 删除节点流程图
作者其他创作
大纲/内容
1.如果p的父节点为空,root=replacement2.如果p为父节点的左子节点,p的父节点的左子节点=replacement3.如果p为父节点的右子节点,p的父亲节点的右子节点=replacement
p是否左右节点都不为空
找一个待删除节点的继承者节点s
1.如果p为父节点的左子节点,p的父节点的左子节点置空2.如果p为父节点的右子节点,p的父节点的右子节点置空3.p的父节点置空
p是否为黑色节点
替换节点replacement选择为p的右子节点
是
replacement是否不为空
否
p的左子节点、右子节点、父节点置为空
P的父节点是否为空
替换节点replacement选择为p的左子节点
结束
1.p.key=s.key2.p.value=s.value3.p地址=s地址
P没有左右子节点,没有父节点,表示当前数据结构中只有一个节点,将此节点直接移除即可
p的父节点不为空,左右子节点为空,表示p是叶子节点
删除节点开始
replacement的父节点地址=p的父节点地址
replacement父节点是否为空
p的左字节点是否为空
节点删除,数据修正
节点删除数据修正
0 条评论
下一页