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