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 的右孩子要么没有,要么是黑色;):
其实我心里感觉不调整肯定是错的,但是我又无法说服自己,越想越乱,急需 v 友们的指点啊!
其实有点思路,但又不知道对不对:
不行了,我已经懵了,说得有点乱,见谅。PS:v 友推荐的 draw.io 真香
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.