红黑树失黑修正
2019-07-24 17:25:42 1 举报
红黑树失黑修正
作者其他创作
大纲/内容
90
34
25
23
86
80
58
60
LB-1 过程：右旋 90，染红 90，染黑 80，转化为 LB-2R
红黑树失黑修正
利用 LB-3 把这棵树修正好：（右旋兄弟 86、再左旋父亲 60，然后染黑 60）
LB-2R （没有红色侄子，且父亲为红色，兄弟为黑色）
第二次 LB-2B 过程：染红 80第三次 LB-2B 过程：递归到根节点 58，结束修正
对于 LB-1，我们不能直接解决，但是我们可以利用一次旋转，触发递归深度为 1 的递归，将它转化为不需要递归的 LB-2R 或者 LB-3
LB-3 （有红色侄子）
100
等价 2-3-4 树
这是红黑树失黑修正过程中唯一可能出现对数递归的情况。这时要染红兄弟，然后递归修正父亲
删除100
递归深度3
1.左旋
59
LB-1 父黑兄红
删除25
删除60
例子2：删除100
触发 LB-1 修正，只不过递归后会触发 LB-2R，此时按照 LB-2R 进行修正：（LB-1 过程：右旋 90，染红 90，染黑 80，转化为 LB-2R。LB-2R 过程：染红 86，染黑 90）
删除23
修正方法是 1 或 2 次旋转，然后 1 或 2 次重染色
删除59
第一次 LB-2B 过程：染红 34，转化为 LB-2B
1.右旋
LB-2R 过程：染红 86，染黑 90
2.左旋
LB-2B (没有红色侄子，且父亲为黑色，兄弟为黑色)
（左旋 58，染黑 90，同时要注意维护根节点）
只需要对父亲和兄弟各做一次重染色即可
0 条评论
回复 删除
下一页
