红黑树刨析（删除部分）
文章目录
- 红黑树删除节点情景分析
- 情景1：删除节点左右子树都为空
- 情景1.1：删除节点为红色
- 情景1.2：删除节点为黑色
- 情况1.2.1：删除节点的兄弟节点是红色
- 情景1.2.2：删除节点的兄弟节点是黑色
- 情景1.2.2.1：删除节点的兄弟节点是黑色，兄弟节点的右节点是红色，兄弟节点的左节点是空或者红色
- 情景1.2.2.2：删除节点的兄弟节点是黑色，兄弟节点的左节点是红色，兄弟节点的右节点是空（右节点是红色按照情况1.2.2.1讨论就可以了）
- 情景1.2.2.3：删除节点的兄弟节点是黑色，兄弟节点无孩子
- 情景2：删除节点有一个子树（左子树或者右子树）
- 情景3：删除节点有两个子树
红黑树删除节点情景分析
情景1：删除节点左右子树都为空
情景1.1：删除节点为红色
那么可以直接将p删除，不影响平衡性
暂时无法在飞书文档外展示此内容
以下这两种情况都符合
情景1.2：删除节点为黑色
删除节点为黑色的话就不太平衡了，此时我们就需要看情况讨论了
情况1.2.1：删除节点的兄弟节点是红色
将父亲节点和兄弟节点颜色互换，然后再将父亲节点左旋，此时这就变成了情景1.2.2。
情景1.2.2：删除节点的兄弟节点是黑色
如果兄弟节点为黑色，那么只有两种情况
情景1.2.2.1：删除节点的兄弟节点是黑色，兄弟节点的右节点是红色，兄弟节点的左节点是空或者红色
此时如果我们删除黑色节点p，那么就不平衡了，我们看一下pp - ppr - pprr三个节点，这三个点在一条线上，我们可以借助pprr这个红色节点变成黑色节点来保持平衡。首先让pp和ppr互换颜色，然后再将pp左旋，那么删除p之后，右边没有黑色节点，直接让pprr变成黑色就行了。
情景1.2.2.2：删除节点的兄弟节点是黑色，兄弟节点的左节点是红色，兄弟节点的右节点是空（右节点是红色按照情况1.2.2.1讨论就可以了）
直接让兄弟右旋，然后将兄弟和侄子互换颜色，就变成了情景1.2.2.1。
情景1.2.2.3：删除节点的兄弟节点是黑色，兄弟节点无孩子
情景1.2.2.3.1：删除节点的兄弟节点是黑色，兄弟节点无孩子，父亲节点是红色
删除节点P之后，左右两边不平衡了，可以直接将父节节点变成黑色，兄弟节点变成红色，这样就平衡了。
情景1.2.2.3.2：删除节点的兄弟节点是黑色，兄弟节点无孩子，父亲节点是黑色
直接将兄弟节点变成红色，这样就平衡了。但是经过pp的路径上的黑色节点数会少1，这个时候在以pp作为起始点，继续平衡操作，这里可以把pp和ppr当作一个节点pp这样一直向上，直到新的起始点为根节点。
情景2：删除节点有一个子树（左子树或者右子树）
以下情景不满足红黑树性质不可能出现：
只有下面两种情况可能出现：
删除节点是黑色，子节点是红色
那么可以直接让子孩子替换p，颜色变成黑色就可以了。
情景3：删除节点有两个子树
首先找到删除节点的后继节点，再将后继节点和删除节点替换，问题就变成删除替换节点的问题，而且替换节点要么无子树，要么有一个节点，问题就变回了情景1或者情景2。
JDK1.8中hashMap中的删除红黑树节点的源码，我做了一部分的改进，方便阅读。
final void removeTreeNode(MyHashMap<K, V> map, Node<K, V>[] tab,
boolean movable) {
/**
* 链表的处理
*/
int n;
// 如果当前哈希表为空直接返回
if (tab == null || (n = tab.length) == 0)
return;
// 计算当前节点在hash表的索引位置
int index = (n - 1) & hash;
// fisrt : t头节点
TreeNode<K, V> first = (TreeNode<K, V>) tab[index];
// 如果索引位置的红黑树为空
if (first == null) {
return;
}
// root:根节点
TreeNode<K, V> root = first;
// rl : root的左节点
TreeNode<K, V> rl;
// succ：节点的后继节点
TreeNode<K, V> succ = (TreeNode<K, V>) next;
// pred：节点的前驱节点
TreeNode<K, V> pred = prev;
// 如果根节点为空，则当前节点就是头节点，直接删除
if (pred == null) {
first = succ;
tab[index] = succ;
// 根节点不为空，当前节点为中间某个节点，删除中间节点
} else {
// 前驱的后继
pred.next = succ;
}
// 后继的前驱
if (succ != null) {
succ.prev = pred;
}
// 如果root的父节点不为空，说明该节点并不是真正的红黑树根节点，需要重新查找根节点
if (root.parent != null) {
root = root.parent;
}
// 通过root节点来判断此红黑树是否太小, 如果是太小了则调用untreeify方法转为链表节点并返回
// (转链表后就无需再进行下面的红黑树处理)
// 太小的判定依据：根节点为null，或者根的右节点为null，或者根的左节点为null，或者根的左节点的左节点为null
// 这里并没有遍历整个红黑树去统计节点数是否小于等于阈值6，而是直接判断这几种情况，
// 来决定要不要转换为链表，因为这几种情况一般就涵盖了节点数小于6的情况，这样执行效率也会变高
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
/**
* 红黑树的处理
*/
TreeNode<K, V> p = this;
TreeNode<K, V> pl = left;
TreeNode<K, V> pr = right;
// replacement：替换节点
TreeNode<K, V> replacement;
if (pl != null && pr != null) {
// 找到当前节点的后继
TreeNode<K, V> s = pr;
TreeNode<K, V> sl = s.left;
while (sl != null) {
s = sl;
sl = s.left;
}
// 交换p和s的颜色
boolean c = s.red;
s.red = p.red;
p.red = c;
TreeNode<K, V> sr = s.right;
TreeNode<K, V> pp = p.parent;
// 如果p的后继节点s恰好是p的右节点，那说明pr没有左节点
// 那么就可以直接将pr替换为p
if (s == pr) {
// 先处理p
p.parent = s;
p.left = null;
p.right = sr;
if (sr != null) {
sr.parent = p;
}
// 处理s
s.right = p;
s.left = pl;
pl.parent = s;
s.parent = pp;
if (pp == null) {
root = s;
} else if (p == pp.left) {
pp.left = s;
} else {
pp.right = s;
}
} else {
// 将p和s互换
TreeNode<K, V> sp = s.parent;
p.parent = sp;
if (s == sp.left) {
sp.left = p;
} else {
sp.right = p;
}
p.left = null;
p.right = sr;
if (sr != null) {
sr.parent = p;
}
s.parent = pp;
if (pp == null) {
root = s;
} else if (p == pp.left) {
pp.left = s;
} else {
pp.right = s;
}
s.left = pl;
s.right = pr;
pr.parent = s;
}
// 如果sr不等于null，那需要p和sr替换掉
if (sr != null) {
replacement = sr;
// 如果sr等于null，此时p无子树，直接删掉就可以
} else {
replacement = p;
}
// 走到这里说明pr为null，pl不为null
} else if (pl != null) {
replacement = pl;
// 走到这里说明pl为null，pr不为null
} else if (pr != null) {
replacement = pr;
}
// 到这里，说明p的左右节点都为null
else {
replacement = p;
}
// 删掉当前节点p
if (replacement != p) {
TreeNode<K, V> pp = replacement.parent = p.parent;
// 当p只有一个子树的时候，p的父节点可能为null
if (pp == null) {
root = replacement;
} else if (p == pp.left) {
pp.left = replacement;
} else {
pp.right = replacement;
}
// 删掉p节点
p.left = p.right = p.parent = null;
}
// 如果p节点是红色，那不影响树的结构
TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) {
TreeNode<K, V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left) {
pp.left = null;
} else {
pp.right = null;
}
}
}
}
static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root,
TreeNode<K, V> x) {
TreeNode<K, V> xp, xpl, xpr;
while (true) {
// 如果x为null或者是根节点，说明已经删除完了
if (x == null || x == root) {
return root;
// 父节点为null，说明是根节点
} else if ((xp = x.parent) == null) {
x.red = false;
return x;
// 如果x是红色的，那么直接让它变成黑色的就行了
// 因为父节点是黑色的，x节点直接代替他成为黑色的就行了
// 这对应情景1.1或情景2
} else if (x.red) {
x.red = false;
return root;
// x既不是根节点，也不是红色
// x是父亲的左节点
} else if ((xpl = xp.left) == x) {
// 此时对应于情景1.2.1，父兄换色，然后对x在进行一次平衡
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null) {
// TODO： 这里应该不可能出现
System.out.println("..........");
x = xp;
} else {
TreeNode<K, V> sl = xpr.left, sr = xpr.right;
// 此时xpr只能是黑色
// 这里if判断成功的可能条件：
// 1.sl == null,sr == null (对应情景1.2.2.3)
// 2.sl == null,sr == black (不可能)
// 3.sl == black,sr == null (不可能)
// 4.sl == black,sr == black (不可能)
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
} else {
// 进入这里的可能条件
// 1.sl == null,sr == red (对应情景1.2.2.1)
// 2.sl == red,sr == null (对应情景1.2.2.2)
// 3.sl == red,sr == red (对应情景1.2.2.1)
// 4.sl == black,sr == red (不存在)
// 4.sl == red,sr == black (不存在)
// 条件2
if (sr == null) {
// 情景1.2.2.2
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ? null : xp.right;
}
// 此时就变成了场景1.2.2.1
if (xpr != null) {
// 父兄换色
xpr.red = xp.red;
if ((sr = xpr.right) != null) {
sr.red = false;
}
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
} else {
// 如果xpl为红色，那xp和xpl的孩子肯定为黑色
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null) {
x = xp;
} else {
TreeNode<K, V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
xpl.red = true;
x = xp;
} else {
if (sl == null) {
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
}