红黑树删除图解
2022-05-12 09:18:40 0 举报红黑树删除图解
作者其他创作
大纲/内容
U
P
L
删除V
NIL
PP
S
红弟弟
黑兄一红豆—LL
R
红色节点下必然有两个黑子
平衡的核心就是移除将‘双黑’转回‘单黑’节点
V
《双黑 黑兄红豆》
直到递归到‘双黑节点’的父节点为红节点。此时将红父节点设置为黑节点，然后‘双黑节点’转回‘单黑节点’
U顶上成为‘双黑节点’
红色 + 双黑 = 黑 + 单黑
P右旋
LL：S在P的左边，红豆在S的左边
删除VU顶上成为‘双黑节点’
S左旋
将L设置为P的颜色
红哥哥
U替换掉V的位置
LR：S在P的左边，红豆在R的左边
PPP
若P为黑节点。P转为‘双黑节点’U为‘单黑节点’
♥♥： 要删除的结点为 v ，u 是用来替换 v 的孩子结点（注意，当 v 是叶结点时， u 是 NULL结点，且NULL结点我们还是当做黑色结点处理）
重新设置V为黑色，使其回归‘单黑节点’
RL：S在P的右边，红豆在R的左边
《非双黑 一红一黑》
黑兄一红豆—RL
删除VU顶替
黑兄一红豆—RR
删除VU顶替成为‘双黑节点’
P左旋
红色 + 双黑 = 黑色 + 单黑调整右子为红色
R设置为S的颜色（黑）S颜色设置跟随P的颜色
设置P颜色为黑色。U转为‘单黑节点’
U设置为黑色
P右旋S设为黑色右孩子设置为红色
《双黑 黑兄两黑豆》
黑兄一红豆—LR
S转为红色节点
将R设置为P的颜色
递归：若P的父节点为黑节点。PP转为‘双黑节点’P转为‘单黑节点’
《双黑 红兄弟》
S右旋
L设为S的颜色，S设置为P的颜色
RR：S在P的右边，红豆在R的右边
P颜色设置为黑，U转为‘单黑节点’
0 条评论
下一页
