红黑树删除节点情景分析

情景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 smallreturn;}/*** 红黑树的处理*/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替换为pif (s == pr) {// 先处理pp.parent = s;p.left = null;p.right = sr;if (sr != null) {sr.parent = p;}// 处理ss.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的左右节点都为nullelse {replacement = p;}// 删掉当前节点pif (replacement != p) {TreeNode<K, V> pp = replacement.parent = p.parent;// 当p只有一个子树的时候，p的父节点可能为nullif (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 (不存在)// 条件2if (sr == null) {// 情景1.2.2.2sl.red = false;xpr.red = true;root = rotateRight(root, xpr);xpr = (xp = x.parent) == null ? null : xp.right;}// 此时就变成了场景1.2.2.1if (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;}}}}}
}