沉下心来分析HashMap的源码（五）红黑树的删除

红黑树的删除逻辑和HashMap中的删除逻辑，是有不同的，因为在HashMap中需要维护next的属性，以便于在tree转为linkedlist的时候，比较的方便。

所以我们先从普通的红黑树的删除逻辑说起。

红黑树的删除操作

删除操作首先需要做的也是BST（二叉搜索树）的删除操作，删除操作会删除对应的节点，如果是叶子节点就直接删除，如果是非叶子节点，会用对应的中序遍历的后继节点来顶替要删除节点的位置（当前节点右子树的最左节点）。删除后就需要做删除修复操作，使的树符合红黑树的定义，符合定义的红黑树高度是平衡的。

删除修复操作在遇到被删除的节点是红色节点（从2-3树的逻辑上面来看，红色节点直接删除即可，剩下的部分直接的补到红色节点相连的黑色节点即可）或者到达root节点时，修复操作完毕。

删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条（经过的黑色节点是一致的约束）。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。

删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。

删除修复操作分为四种情况(删除黑节点后)：

待删除的节点的兄弟节点是红色的节点。
待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。
待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的(兄弟节点在右边)，如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的。
待调整的节点的兄弟节点是黑色的节点，且右子节点是是红色的(兄弟节点在右边)，如果兄弟节点在左边，则就是对应的就是左节点是红色的。

情况1

case1 由于兄弟节点是红色节点的时候，无法借调黑节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，根据RBTree的定义，兄弟节点的子节点是黑色的，就可以从它的子节点借调了。

case 1这样转换之后就会变成后面的case 2，case 3，或者case 4进行处理了。上升操作需要对C做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。

之所以要做case 1操作是因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。

情况2

case 2的删除操作是由于兄弟节点可以消除一个黑色节点，因为兄弟节点和兄弟节点的子节点都是黑色的，所以可以将兄弟节点变红，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点，继续向上调整，直到整颗树的颜色符合RBTree的定义为止。

case 2这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合RBTree的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到了局部的平衡了，但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。

情况3

case 3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成case 4状态了，在case 4状态下可以将D，E节点都阶段过来，通过将两个节点变成黑色来保证红黑树的整体平衡。

之所以说case-3是一个中间状态，是因为根据红黑树的定义来说，下图并不是平衡的，他是通过case 2操作完后向上回溯出现的状态。之所以会出现case 3和后面的case 4的情况，是因为可以通过借用侄子节点的红色，变成黑色来符合红黑树定义4.

情况4

Case 4的操作是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的，这样的话，整棵树还是符合RBTree的定义的。

Case 4这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义。

删除操作的总结

红黑树的删除操作是最复杂的操作，复杂的地方就在于当删除了黑色节点的时候，如何从兄弟节点去借调节点，以保证树的颜色符合定义。由于红色的兄弟节点是没法借调出黑节点的，这样只能通过选择操作让他上升到父节点，而由于它是红节点，所以它的子节点就是黑的，可以借调。

对于兄弟节点是黑色节点的可以分成3种情况来处理，当所以的兄弟节点的子节点都是黑色节点时，可以直接将兄弟节点变红，这样局部的红黑树颜色是符合定义的。但是整颗树不一定是符合红黑树定义的，需要往上追溯继续调整。

对于兄弟节点的子节点为左红右黑或者 (全部为红，右红左黑)这两种情况，可以先将前面的情况通过选择转换为后一种情况，在后一种情况下，因为兄弟节点为黑，兄弟节点的右节点为红，可以借调出两个节点出来做黑节点，这样就可以保证删除了黑节点，整棵树还是符合红黑树的定义的，因为黑色节点的个数没有改变。

具体的代码为：

/** From CLR */
	private void fixAfterDeletion(Node x) {
		while (x != root && colorOf(x) == BLACK) {
			if (x == leftOf(parentOf(x))) {
				Node uncle = rightOf(parentOf(x));

				if (colorOf(uncle) == RED) {
					setColor(uncle, BLACK);
					setColor(parentOf(x), RED);
					rotateLeft(parentOf(x));
					uncle = rightOf(parentOf(x));
				}

				if (colorOf(leftOf(uncle)) == BLACK && colorOf(rightOf(uncle)) == BLACK) {
					setColor(uncle, RED);
					x = parentOf(x);
				} else {
					if (colorOf(rightOf(uncle)) == BLACK) {
						setColor(leftOf(uncle), BLACK);
						setColor(uncle, RED);
						rotateRight(uncle);
						uncle = rightOf(parentOf(x));
					}
					setColor(uncle, colorOf(parentOf(x)));
					setColor(parentOf(x), BLACK);
					setColor(rightOf(uncle), BLACK);
					rotateLeft(parentOf(x));
					x = root;
				}
			} else { // symmetric
				assert x == rightOf((parentOf(x)));
				Node brother = leftOf(parentOf(x));

				if (colorOf(brother) == RED) {
					setColor(brother, BLACK);
					setColor(parentOf(x), RED);
					rotateRight(parentOf(x));
					brother = leftOf(parentOf(x));
				}

				if (colorOf(rightOf(brother)) == BLACK && colorOf(leftOf(brother)) == BLACK) {
					setColor(brother, RED);
					x = parentOf(x);
				} else {
					if (colorOf(leftOf(brother)) == BLACK) {
						setColor(rightOf(brother), BLACK);
						setColor(brother, RED);
						rotateLeft(brother);
						brother = leftOf(parentOf(x));
					}
					setColor(brother, colorOf(parentOf(x)));
					setColor(parentOf(x), BLACK);
					setColor(leftOf(brother), BLACK);
					rotateRight(parentOf(x));
					x = root;
				}
			}
		}

		setColor(x, BLACK);
	}

Published on Aug 06, 2019 in categories

上一篇沉下心来分析HashMap的源码（四）红黑树的插入
下一篇编码编不下去了怎么办？