红黑树删除操作
2019-09-27 09:17:14 22 举报
红黑树的删除操作作图示意
作者其他创作
大纲/内容
8
2
4
7
3
删除结点存在左右子结点
5
10
右旋
1
染红兄弟结点,平衡传递至父结点
9
左旋
6
兄弟结点的右子节点为红色
染色
叔叔结点是黑色,染红叔叔结点,最后父结点必须是黑色。
删除结点没有左右子结点
删除存在一个结点的孩子
删除结点1【】中表示待删除结点
取后继结点
叔叔结点是红色,染黑叔叔结点,染红父结点
此时叔叔结点是黑色
此时兄弟结点3,没有左右子孩子,或均为黑色
染红兄弟结点,染黑右子结点
左旋兄弟结点
删除结点4【】中表示待删除结点
此时结点和兄弟结点均为黑色,直接染红兄弟结点
直接删除结点,如果结点时黑色需额外判断
平衡传递至父结点9,其兄弟节点为黑色,
此时兄弟结点存在左右子结点,且右子结点是红色,需染黑右子结点,染红兄弟结点,然后左旋;再将兄弟结点的颜色染为父结点的颜色,父结点和兄弟结点的左子结点染为黑色,再右旋
此时结点是红色,则直接染黑, 并退出
这里为什么要染红兄弟节点呢?满足黑高,所以兄弟节点必然也必须少一个黑色
相当于替换右孩子的值,来删除
兄弟结点是红色
0 条评论
回复 删除
下一页