【Java集合】HashMap的删除操作源码详解
目录
HashMap中的removeNode()删除元素方法会触发一系列的TreeNode类的方法，依次为：removeTreeNode()、untreeify()、balanceDeletion()、rotateLeft()、rotateRight()。
下面我们将按照添加删除流程依次详细讲解方法源码。
调用开始位置：
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
......
// 找到目标节点了
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果目标节点是红黑树
if (node instanceof TreeNode){
// 调用红黑树的删除节点方法
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
}
......
}
......
}1、removeTreeNode()
1.1 removeTreeNode()方法图解
本图解忽略红黑树的颜色，请注意。下面的图解是代码中的最复杂的情况（p既有左子树也有右子树的情况，代码中的情况12），即流程最长的那个，p 节点不为根节点，p 节点有左右节点，s 节点不为 pr 节点，s 节点有右节点。
另外，第一次调整和第二次调整的是根据代码而设定的，将第一次和第二次调整合起来看会更容易理解（看第一和第三张图）。如下：
- 第一次调整 + 第二次调整：将 p 节点和 s 节点进行了位置调换，选出要替换掉 p 节点的 replacement
- 这个操作关键点就是找到与p节点进行位置对调的s节点。将p节点与s节点对调，是为了在删除p节点后，能够更加简单方便地维护二叉搜索树结构。那么什么样的位置能让删除p后，能更加简单的进行后续处理呢，也就是我们该如何选定s节点。其实很容易就能想到，当要删除的节点p只有一棵子树甚至没有子树的时候，我们对后续的操作越方便。所以在选择s节点的时候，就按照让p的子树越少越好的原则来选，在removeTreeNode中选择s节点的标准就是选择刚刚大于p节点的节点，因为这个节点必定没有左子树了，如果有左子树的话它也不会是刚刚大于p节点的节点，这样也就满足了该位置最多只有一颗子树的条件。这一步的具体讲解见代码12.1-12.3
- 第二个关键操作就是寻找replacement节点，用来替换掉p节点。removeTreeNode的规则就是取s和p交换位置前s的右子节点sr作为要用来替代p节点的replacement节点（如果sr为空的话就不用找代替节点了）。p和s交换位置之后，sr就是p的唯一子树的根节点，直接将sr替换到p的原位置即可，不需要做其他操作就能维持二叉搜索树结构。
- 第三次调整：将 replacement 节点覆盖掉 p 节点。可见第三张和第四张图的变化。
1.2 removeTreeNode()方法源码
删除树节点操作，谁调用该方法就删除谁，并且在删除完后进行红黑树平衡操作。
还要根据movable判断删除节点后是否移动其他节点，即删除完成之后，需否需要执行moveRootToFront()方法，将红黑树根节点root放到数组桶中。movable参数在remove()方法调用时默认是true。
该方法在HashMap里removeNode方法中使用，被要删除的节点调用的。该删除操作相当于将链表结构和红黑树结构节点之间的关联重新梳理，修正两部分，第一部分是链表的关系修正，第二部分是树的关系修正，然后自平衡操作即可。
/**
* 红黑树的节点移除
* @param movable 如果为false，则在删除后不移动其他节点，不用执行moveRootToFront()方法。
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// --- 链表的处理start ---
int n;
// 1.table为空或者length为0直接返回
if (tab == null || (n = tab.length) == 0)
return;
// 2.根据调用者的hash计算出索引的位置，也就是 根据将要被移除的node节点的hash进行计算
int index = (n - 1) & hash;
// 3.first：当前index位置的节点，root：当前index位置的节点，作为根节点，rl：root的左节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// 4.succ：目标节点(也就是this节点，调用removeTreeNode方法要删除掉的节点)node.next节点，pred：目标节点node.prev节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
// 下面的5-7步的操作就是在链表结构上对node目标节点进行删除
// 5.如果pred节点为空，则代表目标节点node为头节点，
if (pred == null){
// 则将table索引位置和first都指向succ节点(node.next节点)
tab[index] = first = succ;
}
// 6.否则将pred的next属性指向succ节点(node.next节点)
else{
// 这块有一点点饶，主要是因为他这个变量搞得，其实等同于 node.prev.next = node.next;
// 原来是 pred.next = node -> node.next = succ
// 现在是 pred.next = node.next = succ，跳过了node，也就相当于把node删除了（前驱节点与后继节点相连，跳过node节点）
pred.next = succ;
}
// 7.如果succ节点(node.next节点)不为空，
if (succ != null){
// 则将succ.prev(node.next.prev)节点设置为pred(node.prev), 与前面对应（后继节点与前驱节点相连，跳过node节点）
// 等同于 node.next.prev = node.prev
succ.prev = pred;
}
// 8.如果first节点为null，则代表该索引位置没有节点则直接返回
// 这个if其实可以放在上方第3点后面，第4点前面，因为直接判断索引位置就是null，压根不用在找下个节点
if (first == null){
return;
}
// 9.如果root的父节点不为空，说明该节点并不是真正的红黑树根节点，需要重新查找根节点
if (root.parent != null){
// 从该root节点开始去查找根节点，得到根节点之后，将root指向真正的红黑树根节点
root = root.root();
}
// 10.通过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;
}
// --- 链表的处理end ---
// --- 红黑树的处理start ---
// 11.p：目标节点node，pl：p的左节点，pr：p的右节点，replacement：用来替换掉被删除节点的节点
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// 12.如果p的左和右节点都不为空时。这种情况是最复杂的
if (pl != null && pr != null) {
// 12.1-12.3操作就是用来定位节点p和节点s，为第一次调整做准备
/**
* 这里说明一下p和s的作用
* p就是目标节点，也就是我们要删除的节点，这个没什么可说的。
* 但是p节点不能直接在原位置将其删除，因为如果P有左右子树的话，将p删除后应该对其子树进行移动处理，需要在其中选出合适的节点放置在p原有的位置来代替p，并且重新维护搜索二叉树结构。毕竟删除后p的原有位置不能是空的，需要有新的节点来顶替上。
* 如果直接在p的原位置删除的话，后续的处理操作有很大的难度，从两颗子树中找到合适的节点来代替p原有的位置是一件很麻烦的事情，因为有很多个可选择的节点，这个选择标准不好把控，而且就算是选出来也需要进行一些列的操作来维护二叉搜索树结构（需要照顾到两棵子树的结构）。所以最好是将p移动到一个对后续操作更加简单位的位置上
* s节点就是要在删除p前，应该将p移动到的位置，将p与s节点进行位置交换，后续的处理就会更加简单
* 那么什么样的位置能让删除p后，能更加简单的进行后续处理呢，也就是我们该如何选定s节点？
* 其实很容易就能想到，当要删除的节点p只有一棵子树甚至没有子树的时候，我们对后续的操作越方便。想想看如果p没有子树，那么删除了p之后，也不需要做其他操作来维护二叉搜索树结构了，只需要后续进行红黑树平衡操作即可，如果p只有一棵子树，那也很简单，直接将这颗子树的根节点替换到p的原有位置即可维持二叉搜索树结构
* 所以在选择s节点的时候，就按照让p的子树越少越好的原则来选
* 在removeTreeNode中选择s节点的标准就是选择刚刚大于p节点的节点，因为这个节点必定没有左子树了，如果有左子树的话它也不会是刚刚大于p节点的节点，这样也就满足了该位置最多只有一颗子树的条件。
* 并且s节点如果刚刚大于p节点，那么将s和p节点交换位置，其他的节点都不需要变换位置，因为s是刚刚大于p节点的节点，所以将s放到p的位置，能让他继续保持和p节点一样的与pp、pl、pr等其他节点相同的位置关系。虽然交换后s和p的位置关系有问题（s应该是大于p的，交换之后p却成了s的左子树节点），但是后续删除p节点即可。具体的变化可以对比第一次调整前和第二次调整后的两张图片
*
*/
// 12.1 将s指向pr(p的右节点)，这是为了保证查找s节点是找到的节点都是比p大的 sl：s的左节点
TreeNode<K,V> s = pr, sl;
// 12.2 从p节点的右子节点开始，向左一直查找，跳出循环时，s为没有左节点的节点。这也就保证了最后定位到的s节点是刚刚比p大的节点
while ((sl = s.left) != null){
s = sl;
}
// 12.3 交换p节点和s节点的颜色
boolean c = s.red; s.red = p.red; p.red = c;
// s的右节点
TreeNode<K,V> sr = s.right;
// p的父节点
TreeNode<K,V> pp = p.parent;
// --- 第一次调整和第二次调整：将p节点和s节点进行了位置调换，并且选出要替换掉 p 节点的 replacement ---
// 12.4 第一次调整：将 p 节点和 s 节点进行了位置调换
// 如果p的右节点即为s节点，则将p和s交换位置，原先是s.parent = p；p.right = s；
if (s == pr) {
p.parent = s;
s.right = p;
}
else {
// 将sp指向s的父节点
TreeNode<K,V> sp = s.parent;
// 将sp作为p的父节点
if ((p.parent = sp) != null) {
// 如果s节点为sp的左节点，则将sp的左节点指向p，此时sp的的左节点s变成了p节点
if (s == sp.left){
sp.left = p;
}
// 否则s节点为sp的右节点，则将sp的右节点指向p，此时sp的的右节点s变成了p节点
else{
sp.right = p;
}
// 完成了p和s的交换位置
}
// s的右节点指向p的右节点
if ((s.right = pr) != null)
// 如果pr不为空，则将pr的父节点指向s，此时p的右节点变成了s的右节点
pr.parent = s;
}
// 12.5 第二次调整：将第一次调整后独立出来的节点再次插入新构造出来的红黑树结构的对应位置，并且选出要替换掉 p 节点的 replacement
// 12.5.1 将第一次调整后独立出来的节点再次插入新构造出来的红黑树结构的对应位置
// 将p的左节点赋值为空，pl已经保存了该节点
p.left = null;
// 将p节点的右节点指向sr，如果sr不为空，则将sr的父节点指向p节点，此时s的右节点变成了p的右节点
if ((p.right = sr) != null)
sr.parent = p;
// 将s节点的左节点赋值为pl，如果pl不为空，则将pl的父节点指向s节点，此时p的左节点变成了s的左节点
if ((s.left = pl) != null)
pl.parent = s;
// 将s的父节点赋值为p的父节点pp
// 如果pp为空，则p节点为root节点, 交换后s成为新的root节点
if ((s.parent = pp) == null)
root = s;
// 如果p不为root节点, 并且p是pp的左节点，则将pp的左节点赋值为s节点
else if (p == pp.left)
pp.left = s;
// 如果p不为root节点, 并且p是pp的右节点，则将pp的右节点赋值为s节点
else
pp.right = s;
// 12.5.2 寻找replacement节点，用来替换掉p节点。removeTreeNode的规则就是取s和p交换位置前s的右子节点sr作为要用来替代p节点的replacement节点,如果sr节点为null，则直接将p删除即可
// 12.5.2.1 如果sr不为空，则replacement节点为sr，因为s没有左节点，所以使用s的右节点来替换p的位置
if (sr != null)
replacement = sr;
// 12.5.2.1 如果sr为空，则s为叶子节点，replacement为p本身，只需要将p节点直接去除即可
else
replacement = p;
}
// 13.承接12点的判断，如果p的左节点不为空，右节点为空，replacement节点为p的左节点，原理上面也讲过了，因为只有一颗子树，直接将子树的根节点替换到p的位置即可，不需要重新维护二叉搜索树结构
else if (pl != null)
replacement = pl;
// 14.如果p的右节点不为空,左节点为空，replacement节点为p的右节点，原理同上
else if (pr != null)
replacement = pr;
// 15.如果p的左右节点都为空, 即p为叶子节点, replacement节点为p节点本身，直接将p删除即可
else
replacement = p;
// 16.第三次调整：使用replacement节点替换掉p节点的位置，将p节点移除
// 16.1 如果p节点不是叶子节点（上面只有当p没有子树的时候，才会将replacement指向p），则将p删除后需要再将replacement节点替换到p的位置
if (replacement != p) {
// 16.1.1 将p节点的父节点（此时p的父节点是已经交换完位置后p的父节点，也就是第三张图中的sp节点）赋值给replacement节点的父节点, 同时赋值给pp节点
TreeNode<K,V> pp = replacement.parent = p.parent;
// 16.1.2 如果p没有父节点, 即p为root节点，则将root节点赋值为replacement节点即可
if (pp == null)
root = replacement;
// 16.1.3 如果p不是root节点, 并且p为pp（第三张图的sp节点）的左节点，则将pp的左节点赋值为替换节点replacement
else if (p == pp.left)
pp.left = replacement;
// 16.1.4 如果p不是root节点, 并且p为pp的右节点，则将pp的右节点赋值为替换节点replacement
else
pp.right = replacement;
// 16.1.5 p节点的位置已经被完整的替换为replacement, 将p节点清空, 以便垃圾收集器回收
p.left = p.right = p.parent = null;
}
// 16.2 完成了p节点的删除并将替代节点放置到p的位置后，判断如果p节点不为红色，则进行红黑树删除平衡调整(如果删除的节点是红色则不会破坏红黑树的平衡无需调整，在红黑树的文章中讲过)
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// 16.3 如果p节点为叶子节点（即无子树）, 则简单的将p节点去除即可，无需做其他操作
if (replacement == p) {
TreeNode<K,V> pp = p.parent;
// 16.3.1 将p的parent属性设置为空
p.parent = null;
if (pp != null) {
// 16.3.2 如果p节点为父节点的左节点，则将父节点的左节点赋值为空
if (p == pp.left)
pp.left = null;
// 16.3.3 如果p节点为父节点的右节点，则将父节点的右节点赋值为空
else if (p == pp.right)
pp.right = null;
}
}
// 根据movable判断删除节点后是否要将红黑树根节点root放到数组桶中
if (movable)
// 18.将root节点移到数组桶中
moveRootToFront(tab, r);
// --- 红黑树的处理end ---
}
1.3 为什么 sr 是 replacement 的首选，p 为备选？
首先我们看 sr 是什么？从代码中可以看到 sr 第一次被赋值时，是在 s 节点进行了向左穷遍历结束后，因此此时 s 节点是没有左节点的，sr 即为 s 节点的右节点。而从上面的第一次调整和第二次调整我们知道，p 节点已经跟 s 节点进行了位置调换，所以此时 sr 其实是 p 节点的右节点，并且 p 节点没有左节点，因此要移除 p 节点，只需要将 p 节点的右节点 sr 覆盖掉 p 节点即可，因此 sr 是 replacement 的首选，而如果 sr 为空，则代表 p 节点为叶子节点，此时将 p 节点直接移除即可。
2、balanceDeletion()
2.1 balanceDeletion()方法源码
红黑树的删除平衡调整，第一个输入参数是整棵红黑树的根节点，第二个输入参数是待删除节点或删除节点的替代节点。代码注释的标号对应着下一节流程讲解的步骤。
在removeTreeNode()方法中调用这个方法的时候已经完成了对节点的删除，并且已经将替代节点放到了删除节点的位置。传入的参数是已删除节点的替代节点，在方法中只需要做平衡处理即可。
/**
* 红黑树的删除平衡调整
* @param root 整棵红黑树的根节点
* @param x 待删除节点或删除节点的替代节点，在removeTreeNode方法中调用时传入的就是replacement删除节点的代替节点
*
* @return 返回重新平衡后的根节点
*/
static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root, TreeNode<K, V> x) {
// x 当前要删除的节点
// xp x节点的父节点
// xpl xp节点的左节点
// xpr xp节点的右节点
TreeNode<K, V> xp, xpl, xpr;
// 循环操作，平衡局部之后继续判断调整。注意，传进来的x节点子树的黑节点数，肯定是比x的兄弟节点子树的黑节点数少1
for (; ; ) {
// 前三个分支就是处理结束的返回条件
// 如果x节点为空，或x节点是根节点 ①
if (x == null || x == root) {
// 直接返回根节点
return root;
// 当xp节点为空时，说明x为根节点（这个分支说明是循环后更新x后，使得x指向了root）。这个if分支也完成了对xp的赋值 ②
} else if ((xp = x.parent) == null) {
// 将x节点设置为黑色，并返回x节点
x.red = false;
return x;
// 如果x不是root(有父节点)，且x为红色，直接把x变成黑色，让x子树的黑节点+1。多次循环可到达此分支 ③
} else if (x.red) {
// 将x的颜色设置为黑色
x.red = false;
return root;
}
// 接下来两个分支，x必为黑色，只是区分x为左子节点还是右子节点 ④
// 如果x是xp的左孩子。此分支也完成了对xpl的赋值
else if ((xpl = xp.left) == x) {
// 如果x节点为xpl节点
if ((xpr = xp.right) != null && xpr.red) {
// 如果xpr节点不为空，且xpr节点是红色的
// 将xpr设置为黑色，xp设置为红色
xpr.red = false;
xp.red = true;
// 左旋
root = rotateLeft(root, xp);
// 重新将xp节点指向x节点的父节点，并将xpr节点指向xp的右节点
xpr = (xp = x.parent) == null ? null : xp.right;
} // 如果xpl为黑色，则不会进入到上面的if分支中
// 若xpr节点不存在，即x的兄弟为空
if (xpr == null) {
// 则将x节点指向xp节点向上调整，继续以x父节点调整平衡
x = xp;
} else {
// sl xpr节点的左节点
// sr xpr节点的右节点
TreeNode<K, V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// 若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的
// 将xpr节点变成红色
xpr.red = true;
// 则将x节点指向xp节点向上调整
x = xp;
} else {
// sr和sl中存在一个红节点
if (sr == null || !sr.red) {
// 此处说明sl是红节点,将sl节点设置为黑色
sl.red = false;
// 将xpr节点设置为红色
xpr.red = true;
// 右旋
root = rotateRight(root, xpr);
// 将xpr节点重新指向xp节点的右节点
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr != null) {
// 如果xpr节点不为空,让xpr节点与xp节点同色
xpr.red = (xp == null) ? false : xp.red;
// 当sr节点不为空，将其变成黑色
if ((sr = xpr.right) != null) {
sr.red = false;
}
}
// 存在xp节点
if (xp != null) {
// 将xp节点设置为黑色
xp.red = false;
// 进行左旋
root = rotateLeft(root, xp);
}
// 将x节点指向root进行下一次循环时跳出
x = root;
}
}
}
// 和上边分支的操作是对称的
// 如果x是xp的右孩子。此分支也完成了对xpl的赋值
else {
// 当x节点是右节点 1.1
if (xpl != null && xpl.red) {
// 当xpl节点存在且为红色
// 将xpl变为黑色，xp变为红色
xpl.red = false;
xp.red = true;
// 右旋
root = rotateRight(root, xpl);
// 将xpl节点重新指向xp节点的左节点
xpl = (xp = x.parent) == null ? null : xp.left;
} // 如果xpl为黑色，则不会进入到上面的if分支中 1.2
// 经过上面if，不管它有没有执行，x的兄弟xpl肯定为黑色节点了 2.1
if (xpl == null) {
// 如果xpl节点不存在，则xp节点没有子节点了
// 将x节点指向xp节点向上调整
x = xp;
// 2.2
} else {
// sl xpl节点的左节点
// sr xpl节点的右节点
TreeNode<K, V> sl = xpl.left, sr = xpl.right;
// 这种情况说明xpl的孩子里没有红色节点 2.2.1
if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
// 若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的
// 将xpl节点变成红色
xpl.red = true;
// 则将x节点指向xp节点向上调整
x = xp;
// 这种情况说明xpl的孩子里有红色节点 2.2.2
} else {
// 如果sr为红色，则走此分支；sr其他情况则不会 2.2.2.1.1和2.2.2.2.1
if (sl == null || !sl.red) {
// 此处说明sr是红节点,将sr节点设置为黑色
sr.red = false;
// 将xpr节点设置为红色
xpl.red = true;
// 左旋
root = rotateLeft(root, xpl);
// 将xpl节点重新指向xp节点的左节点
xpl = (xp = x.parent) == null ? null : xp.left;
}
// 如果xpl节点存在 2.2.2.1.2和2.2.2.2.2
if (xpl != null) {
// xpl最终会旋转到之前xp的位置，并保持xp的颜色
xpl.red = (xp == null) ? false : xp.red;
// 如果sl节点存在
if ((sl = xpl.left) != null) {
//将sl节点变为黑色
sl.red = false;
}
}
// 如果xp节点存在 2.2.2.1.3和2.2.2.2.3
if (xp != null) {
// 将xp节点设置为黑色
xp.red = false;
// 右旋
root = rotateRight(root, xp);
}
// 将x节点指向root进行下一次循环时跳出
x = root;
}
}
}
}
}
2.2 balanceDeletion()方法流程详解
提前说明一下，当说到“x节点子树的黑节点数n”是指：从x节点到它的子树的任意一个叶子节点的路径上的黑色节点个数都等于n。
整个函数是一个循环过程，可能会经过若干次循环。不管是刚调用此函数的第一次循环，或者是以后的循环，每次循环体刚开始时，x节点子树的黑节点数，肯定是比x的兄弟节点子树的黑节点数少1，这是由removeTreeNode函数来做保证的（在removeTreeNode中调用balanceDeletion方法时，如果删除的是红色节点是不需要调用balanceDeletion来做平衡处理的，只有删除黑色节点才需要，因为只有删除黑色节点才会导致左右的黑色节点树不一致。所以由于删掉了一个黑色节点，所以替代节点x的黑节点数少1）。既然知道了x的黑节点数，比x的兄弟节点的黑节点数少1，那么就需要通过调整来维持红黑树平衡。
①-③分支都是方法的结束返回条件
①
if (x == null || x == root)分支，如果x是root，则直接返回root。上一次循环执行了x = root后，会进入此分支。此分支是balanceDeletion()方法的结束条件。
②
else if ((xp = x.parent) == null)分支，x的父节点xp为null，但xp为null说明x为root，但这样的话则只会进入上面的if (x == null || x == root)分支了，所以我认为此分支不可能进入。此分支是balanceDeletion()方法的结束条件。
③
else if (x.red)分支，说明x不是root节点，且x为红色。这好办，直接把x变成黑色，让x的黑节点数+1。这样x的黑节点数就和x的兄弟节点的黑节点数一样了，也就到达了平衡。此分支是balanceDeletion()方法的结束条件。
④
接下来的两个分支，说明x不是root节点，且x为黑色，所以调整过程要稍微复杂一点了。但这两个分支是完全对称的，一个是x节点为其父节点的左节点，一个是x节点为其父节点的右节点。这里只讲解else if ((xpl = xp.left) == x)的else分支。
接下来这个大图是整个函数的else if ((xpl = xp.left) == x)的else分支的所有过程，每个过程都有标号以方便讲解。节点除标明为黑色或者红色外，灰色则代表不清楚此节点的颜色。建议读者对照着大图、源码和本博客同时进行查阅。
下面全部是进入到else if ((xpl = xp.left) == x)的else分支的流程，会对内部的每一个分支进行讲解。进入到这个分支时，x一定是xp的右孩子，并且x一定是黑色。
1.1
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 && xpl.red)这个分支可能执行，可能不执行。
如果xpl为红色，那么则会进入此if (xpl != null && xpl.red)分支，如下图所示。如果xpl为红色，那么xp和xpl的孩子的颜色都必为黑色节点。而之前说过，刚开始时x的黑节点数，比x的兄弟节点的黑节点数少1，我们假设x的黑节点数为n，那么xpl作为它的兄弟节点，xpl的黑节点数则为n+1，由于xpl是红色的不属于黑色节点，那么可推理出xpl的两个孩子的黑节点数也为n+1。
xpl.red = false;
xp.red = true;将xpl置为黑色，xp置为红色。这是xpl和x的黑色节点数差1，就需要将x那一侧的增加一个黑色节点，所以将xpl和xp交换颜色，然后对xp右旋，这样就可以把黑色的xpl移到上一层去
root = rotateRight(root, xp);进行右旋，将xpl移到了上一层，完成了一层的平衡，现在就差x那一层的黑色节点数还没左右一致，步骤1的操作就算是完成了，对x这一层的平衡会在步骤2中进行。
xpl = (xp = x.parent) == null ? null : xp.left;根据xp的父节点是否为null，来更新xpl的指向
总结：
如果xpl为红色，且执行完if (xpl != null && xpl.red)分支后，如上图所示。调整后，x的兄弟节点变成了一个黑色节点。对比（1）和（4）发现，通过旋转操作后，使得x和一个黑节点数为n+1的黑色节点成为了兄弟。
1.2
如果xpl为黑色，那么则不会进入此if (xpl != null && xpl.red)分支，如下图所示。xpl的黑节点数为n+1，比x多1。
这种情况的最终结果就是这样：
对比1.1（xpl为红色）和1.2（xpl为黑色）两种情况：
对比xpl为红色和xpl为黑色的两种情况的最终结果，如下图所示，可以发现两种情况最终结果的共同点是：x的兄弟节点必为黑色，但此时兄弟节点的黑节点数多1，所以还需要调整。而两种情况的差异点是：xp的颜色。这也是后面要执行xpl.red = (xp == null) ? false : xp.red（把xp的颜色赋给xpl）的原因。
2.1
if (xpl == null)
x = xp;如果xpl为null，那么则不会进入此if (xpl != null && xpl.red)分支，会进入到这个if (xpl == null)分支，如下图所示。但是xpl为null的情况应该是不可能存在的，因为初始状态xp的左孩子的黑节点必须比右孩子的黑节点多1才可以，下面这种情况并不符合，所以这种情况不可能出现。
2.2
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 || !sl.red) {
if (sr != 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 == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
接下来讲解if (xpl == null)的else分支里的逻辑（根据上一条分析，所以是认为不可能进入if (xpl == null)分支的），在大图中是虚线以下的过程。
虚线下的过程，只能操作到x节点，xp节点（x的父节点），xpl节点（x的兄弟节点），sl节点（x的兄弟节点的左孩子）和sr节点（x的兄弟节点的右孩子），即只能操作这上下三层节点。这也是为什么虚线上的过程最后总会调整为xpl节点为黑色节点的情况，因为这样的话，xpl节点的两个孩子sl和sr的黑节点数就为n，而x节点本身的黑节点数也为n。只有找到了黑节点数都为n的节点们后，才方便进行调整，那之后就根据各种情况来再平衡就好了。
if (xpl == null)的else分支的初始状态如下图（注意，此初始状态是从过程( 4 )而来的，所以虚线下的过程都是过程( 4 )接下来的过程。这里就不再画出从过程( 6 )而来的初始状态了）。由于xpl的黑节点数为n+1，则它自身为黑色，所以推理出，它的左右孩子的黑节点则为n。
很有必要说明一下if ((sl == null || !sl.red) && (sr == null || !sr.red))分支和它的else分支的各种情况，如下图所示，它的else分支里，sl和sr中必有一个节点是红色的。而且在else分支里，当sr为红色时，必然还会进入if (sl == null || !sl.red)子分支。
2.2.1
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}如果进入了if ((sl == null || !sl.red) && (sr == null || !sr.red))分支，如下图所示。那么说明“sl为null或sl为黑色”和“sr为null或sr为黑色”这两件事都必须同时成立，如图过程( 8 )。这个时候，x的兄弟节点的两个孩子都是黑色节点，这样的话根本没有操作空间使得x和x的兄弟节点平衡（但凡x的兄弟节点的两个孩子有一个红色节点，也不至于这样）。
所以在if ((sl == null || !sl.red) && (sr == null || !sr.red))分支内，将xpl设为红色，这样xpl和它的兄弟节点平衡了（黑节点数一样），但由于这里是通过让xpl的黑节点数少1来使得平衡的，且xp的颜色我们又没有变过（这里考虑了虚线上的两种情况的差异点，即xp刚开始的颜色可能是红色，也可能是黑色），所以不管xp的初始颜色是什么，xp必然比xp的兄弟节点的黑节点数少1，所以还是不平衡的，就将x指向xp，然后继续循环。如果xp初始为黑色，那么xp的黑节点数为n+1，xp的兄弟节点的黑节点数为n+2。如果xp初始为红色，就如过程（9）所示，xp的黑色节点数为n，xp的兄弟节点的黑色节点数为n+1。
下图即为该分支的转化过程，xpl设置为红色，并且将x指向xp
2.2.2
else {
if (sl == null || !sl.red) {
if (sr != 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 == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
如果进入了if ((sl == null || !sl.red) && (sr == null || !sr.red))的else分支，如下图所示。那么说明“sl为null或sl为黑色”和“sr为null或sr为黑色”这两件事不会同时都成立。观察逻辑可以发现，else分支里可以分为两种情况：
- 如果sl为黑色，那么sr为红色。即(sl == null || !sl.red) 成立，(sr == null || !sr.red)不成立，如图（10）
- 如果sl为红色，此时不管sr的颜色是什么都会进入else分支。即(sl == null || !sl.red)不成立，如图（17）
其实这两种情况的共同点就是sr和sl中至少有一个是红色节点。
2.2.2.1 情况一
情况一是“sl为黑色，sr为红色”，这种情况(sl == null || !sl.red) 成立，(sr == null || !sr.red)不成立，对应上面说的第一种情况。
如下图所示，为这种情况的开始过程和结束过程。发现过程( 16 )时，整个树已经平衡了，结束后会将x指向root（x = root），下次循环就会直接退出了。且过程( 10 ) 里xp这个位置，对应到过程( 16 )里则变成了xpl这个节点，且过程( 10 )里xp的颜色还可能为黑色，那么过程( 16 )的xpl会和过程( 10 )里xp的颜色一致（虚线下的三行过程都保证了这一点）。这是通过将xp的颜色赋给xpl（xpl.red = (xp == null) ? false : xp.red），再右旋xp（rotateRight(root, xp)）来保证的，这样，就把虚线上的差异点考虑在内了。
下面是这个情况的具体执行过程
2.2.2.1.1
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ? null : xp.left;
}“sl为黑色，sr为红色”，这种情况会进入到if (sl == null || !sl.red) 分支。
开始状态
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);将sr置为黑色，xpl置为红色，将xpl左旋
左旋之后的结果
xpl = (xp = x.parent) == null ? null : xp.left;根据x的父节点xp是否为null来更新xpl的指向，如果xp不为null，则将xpl指向xp的左子节点
2.2.2.1.2
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}进入到if (xpl != null)分支，如果xp不为空，则将xpl的颜色设置为和xp的颜色一样，然后在if ((sl = xpl.left) != null)判断中更新sl的指向，以前sl指向的是旧的xpl的左子节点，经过步骤（13）xpl的位置更新了，所以需要重新更新sl的位置，然后如果sl不为null，则将sl节点染成黑色
2.2.2.1.3
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}进入到if (xp != null)分支，如果xp不为null，则将xp置为黑色，然后将xp进行右旋
这是情况一经过处理之后的结果
最后x = root;结束处理，这样在下一轮循环时就会直接返回。
2.2.2.2 情况二
情况二是“sl为红色”，这种情况(sl == null || !sl.red) 不成立，对应上面说的第二种情况。
如下图所示，为这种情况的开始过程和结束过程。发现过程( 20 )时，整个树已经平衡了，结束后会将x指向root（x = root），下次循环就会直接退出了。同样的，过程( 17 )里xp这个位置对应过过程( 20 )里会保持相同位置的节点颜色一致。
下面是这个情况的具体执行过程
2.2.2.2.1
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ? null : xp.left;
}因为这种情况sl为红色，所以不可能进入到这个if分支
开始状态
2.2.2.2.2
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}进入到if (xpl != null)分支，如果xp不为空，则将xpl的颜色设置为和xp的颜色一样，然后在if ((sl = xpl.left) != null)判断中更新sl的指向，但是因为这种情况并没有进入if (sl == null || !sl.red) 分支，所以xpl的位置并没有改变，最后如果sl不为null，则将sl节点染成黑色
2.2.2.2.3
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}进入到if (xp != null)分支，如果xp不为null，则将xp置为黑色，然后将xp进行右旋
这是情况二经过处理之后的结果
最后x = root;结束处理，这样在下一轮循环时就会直接返回。
2.2.2.3 情况一和情况二对比
虚线下的第二行过程（过程( 10 )到过程( 16 )）和第三行过程（过程( 17 )到过程( 20 )），除了开始过程和结束过程外，中间过程里图中只给那些调整过程中黑节点数不变的节点标注出来了黑节点数，其他没有标注出来的节点只需要在结束过程里进行确认就好了。
之所以虚线下的第二行过程和第三行过程要进行区分，是因为sr是否为红色，需要进行的调整操作是不一样的。比如过程过程( 10 )如果走的是第三行过程的流程，如下图所示，最终会造成sl和xp这两个兄弟节点不是平衡的。
2.2 总结
- 和balanceInsertion一样，此balanceDeletion方法同样只处理三层树的结构。
- 每次循环体里，除非进入那些直接return的终点，那么循环体开始时，x节点总是比x节点的兄弟节点的黑节点数少1的。
- 虚线下的过程，其主要技巧（指的是虚线下第二行和第三行。第一行是先让自己和兄弟平衡，但却是通过不是让自己加1，而是让兄弟减1，所以还需要x往上移动，往更高层借红色节点）是通过借用颜色为红色的兄弟节点的左右孩子，只要有一个孩子是红色的，就可以借用。而借用其实就是，通过旋转操作把红色节点弄到自己的子树里，然后通过红色变黑色，让自己子树的黑节点数加1，从达到平衡。
- 大图中，到达虚线时的过程，x的兄弟节点总会是黑色的。根据前提“x节点总是比x节点的兄弟节点的黑节点数少1”，而兄弟节点又是黑色，可以推理出“x的兄弟节点的两个孩子的黑节点数，和x节点一样大”，找到了一样大的节点，之后才好处理。
相关文章：【Java集合】HashMap系列（一）——底层数据结构分析
【Java集合】HashMap系列（二）——底层源码分析
【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树
【Java集合】HashMap的扩容操作源码详解
【Java集合】HashMap的添加操作源码详解
相关文章
- Java入门系列之集合HashMap源码分析
- Java入门系列之集合Hashtable源码分析
- java安全编码指南之:输入校验
- Java注解-最通俗易懂的讲解
- [转]获取JAVA[WEB]项目相关路径的几种方法
- 如何配置openjdk的 java home
- 肝了！一篇文章搞定1000道大厂Java面试题
- Java ArrayList源码剖析
- java.io.ByteArrayOutputStream 源码分析
- java.io.BufferedOutputStream 源码分析
- Android系统原理与源码分析（1）：利用Java反射技术阻止通过按钮关闭对话框
- 七步让Java程序通过JDBC连接数据库
- java 动态代理深度学习(Proxy,InvocationHandler),含$Proxy0源码
- windows 批处理把所有java源码导入一个txt文件中
- java.util.concurrent解析——ThreadPoolExecutor源码解析
- Java_DES 加密和解密源码
- 浅析Java中for循环里对list进行add操作踩坑
- java项目之疫情网课管理系统（springboot+vue源码）
- 【转】Java学习—什么是时间复杂度
- Java程序员从笨鸟到菜鸟之（五十二）细谈Hibernate（三）Hibernate常用API详解及源码分析--csdn 曹胜欢
- 记一次未解决的异常：java.lang.NoClassDefFoundError: net/sf/json/JSONObject
- Java显式锁学习总结之六：Condition源码分析
- 源码分析netty服务器创建过程vs java nio服务器创建
- 曹工说Spring Boot源码（25）-- Spring注解扫描的瑞士军刀，ASM + Java Instrumentation，顺便提提Jar包破解
- 源码编译OpenJdk 8，Netbeans调试Java原子类在JVM中的实现（Ubuntu 16.04）
- java 基础 Long类型 判断是否相等
- JAVA练习题：求水仙花数