[Java] hashmap 里红黑树操作 balanceInsertion 的一个疑问?我懵了,你呢
Link Share :https://www.v2ex.com/t/631271#reply0
- via RSS
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 真香
作者暂无likerid, 赞赏暂由本网站代持,当作者有likerid后会全部转账给作者(我们会尽力而为)。Tips: Until now, everytime you want to store your article, we will help you store it in Filecoin network. In the future, you can store it in Filecoin network using your own filecoin.
Support author:
Author's Filecoin address:
Or you can use Likecoin to support author: