if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//两个连续的 if，但第一个 if 不一定执行
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
源码是 1.8。现在假设已经进入了if ((xppr = xpp.right) != null && xppr.red)的 else 分支，里面有两个连续的 if，但第一个 if 不一定执行。其实第一个 if 的效果就是调整 x 和 xp 之间的左右关系，如果 x 是 xp 的右孩子，那么要调整为左孩子，再执行第二个 if。示意图如下（标记了 1,2 是因为 x 和 xp 的引用会互换，所以这两个节点必须看真实的标号； xpp 到 xppr 是虚线表示 xpp 的右孩子要么没有，要么是黑色；）：
但是我发现，如果 x 是 xp 的右孩子，那么我不调整，好像也是对的啊。示意图如下：
其实我心里感觉不调整肯定是错的，但是我又无法说服自己，越想越乱，急需 v 友们的指点啊！
其实有点思路，但又不知道对不对：
- 第一个图的初始状态，x （以后称为 2 号节点）的左右子树的黑节点数量肯定是相等的，我观察了一下，最终状态时，2 号节点的左子树会给 1 号节点当右孩子（左旋操作），2 号节点的右子树会给 xpp 当左孩子（右旋操作），所以这就是调整之后能再次平衡的原因吗？（那 1 号节点，xppr 的黑节点个数就不用考虑了吗？）
- 再看第二个图（第二个图，x 和 xp 引用不会互换，所以照常称呼），也是分析初始状态的子树，xp 的左子树还是 xp 的左边，xp 的右子树也就是 x，也还在 xp 的右边，只不过更深了而已。那好像看起来也对啊？
- 还有就是，是不是可以认为 balanceInsertion 的循环过程就是，从下到上地调整，每循环完成一次后，就会使得 x 的左右子树平衡，然后再另 x 引用往上移动，然后再次循环。简单的说，balanceInsertion 的每次循环结束，都会保证 x 引用的左右平衡。
不行了，我已经懵了，说得有点乱，见谅。PS：v 友推荐的 draw.io 真香
Select Language