红黑树删除
2017-03-10 16:09:21 0 举报
红黑树删除是一种自平衡二叉查找树，它的删除操作同样分为三种情况：被删除节点是叶子节点、被删除节点只有一个子节点、被删除节点有两个子节点。在第一种情况下，直接将该节点删除；在第二种情况下，用其子节点直接替换；在第三种情况下，找到右子树中小于该节点的最小节点来替代该节点，然后删除该最小节点。红黑树的删除操作会通过旋转和重新着色来保持它的性质。
作者其他创作
大纲/内容
P
K
X
删除节点是红色，且只有一个右子节点
K+1
B
L
K+2
左旋P，从新设置B
中间有K-2
K 指的是包括该节点的后面的路径的黑节点个数
将X的父节点P的颜色赋值给X的兄弟节点B，将X的父节点设置为黑色，X的兄弟节点B的右子点设置为黑色
NULL
删除节点为红色，只有一个子节点，无论是左子还是右子，都不影响
N
\bB设置为P的颜色，P，R设置为黑色
被删除节点没有子节点的话，无论被删除节点是什么颜色，都不影响红黑树特性
\b原先: N 黑，X红，G 左边这条路是 K+1 黑，去除 N 后，左边这条路为 K，把 X变为黑，则 K+1
删除的节点N是黑色的，那么就相当于，这一边少了一个黑色，现在让X替换了之前的位置。如果X是红色的，替换X为黑色，解决问题
设置P为当前节点X
删除节点是红色，且只有一个左子节点
右旋B
\bX为黑，X不为根，X的兄弟为红
R
修复B? .相当于转换成了下面的情况
修复B
镜像
X为黑色节点，且X不是跟节点，X的兄弟节点是红色的（自然，兄弟的子节点是黑色的)
\bX为黑，X的兄弟为黑，X的兄弟B的两个孩子为黑
删除节点为红色，且只有一个节点
T
X的父P变红，x的兄变黑
删除节点有两个子节点
\b原先: N 黑，X黑，G 左边这条路是 K+2黑，去除 N 后，左边这条路为 K+1，由于X本身就是黑，无法通过变X增加黑的数目
X为黑，X的兄弟节点B为黑，B的左节点为红，B的右节点为黑
\bX的兄弟变为红
\bP右旋
X是黑色的且X是根，直接结束
X（之前的T）
X这边的路径少了一个黑，让B变成红，但是P这条路径少了一个黑，情况就相当于把要处理的节点变成了P，让要处理节点网上升了。
\b左旋P，这样导致，但是因为不确定 B 之前的左子节点是什么颜色，于是让 P 变为 黑色，无论是之前P本来就是黑色，还是因为设置P为黑色，P这边的路径必然比R那边的路径多1，于是，让R 变成黑色，由于是B代替了原来P的位置，于是，把B 设置为原来 P 的颜色
X为黑色，X的兄弟B为黑色，兄弟B的右子节点为红色，B的左节点任意颜色
兄弟B的左孩子变为黑，兄弟B变为红
T (包括T，K-1)
\b左旋P
\b复制T 的内容到 X （颜色不变），不改变红黑树特性，删除 X，现在转换为删除 X 的情况。由于：如果 X 有两个子节点，那么，X 的后继节点必然是 右子节点或者右子节点最左的子孙节点，且该节点要么是没有子节点，要么是只有右节点，现在相当于删除 原来 T 的情况，
0 条评论
回复 删除
下一页
