hashmap 里红黑树操作 balanceInsertion 的一个疑问？我懵了，你呢

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1592 天前的主题，其中的信息可能已经有所发展或是发生改变。

                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 真香

第 1 条附言 · 2019-12-22 19:37:05 +08:00

手机这段代码看的效果不好，这里附上 balanceInsertion 的源码 https://paste.ubuntu.com/p/nFYGJv3fGr/ 大家将就看一下吧

xpp

null

子树

节点

8 条回复 • 2019-12-23 15:05:24 +08:00

crackhopper

2019-12-23 11:12:48 +08:00

我觉得你的算法最后需要把 xpp 那个红色，变成黑色。然后调整前后，黑色深度变了。

另外红黑树算法不是一个直观的对 2-3-4 树算法的变换么，2-3-4 树算法怎么样，对应红黑树算法怎么调整。

amiwrong123

2019-12-23 11:32:53 +08:00

@crackhopper
“你的算法”指的是第二个图呗。把 xpp 那个红色，变成黑色，那好像就更不对了啊。而且我第二个图肯定是错误的思路，只是我想论证为什么它是错误的。

什么！！！还他么有个 2-3-4 树啊，我已经学不过来了。学完这些树，自挂东南枝

crackhopper

2019-12-23 11:38:26 +08:00

@amiwrong123 红黑树性质：红色不能相邻。另外 2-3-4 树来理解红黑树更容易。你值得拥有。（红色+黑色节点就是模拟 2-3-4 树的节点的）

amiwrong123

2019-12-23 11:46:48 +08:00

@crackhopper
虽然它值得拥有，但是我现在可能没时间去拥有它😂（刚百度了一下，好像没咋看懂）。而且 hashmap 刚好有红黑树的所有实现，我合计从代码里理解红黑树，应该会更加深刻。

hehheh

2019-12-23 12:59:46 +08:00

红黑树的 case 表太多了，我以前花了 1 天时间去专门理解不同的 case 是怎么处理的，然后现在全忘光了。维基百科上讲的挺好的。

amiwrong123

2019-12-23 13:13:01 +08:00 via Android

@hehheh
好吧，回头我看看维基百科。其实看完 hashmap 源码，感觉这些 case 思路也比较清晰了啊，感觉也没那么多。

“现在全忘了”，难道这就是大家不回我的原因吗😂

hehheh

2019-12-23 14:43:41 +08:00

@amiwrong123 不回你的原因是很多人根本不会去手写红黑树，除了无聊在校大学生，比如若干年前的我。还有就是我觉得这个面试不会问，最多问你红黑树的大致原理以及为什么发明这个东西。

amiwrong123

2019-12-23 15:05:24 +08:00

@hehheh
好吧，手写红黑树那可太难了。我也就是看看源码，再自己理解下。

从面试角度说，确实应该不会问这么细。大致原理现在我也了解了（其实就是看看博客），就是现在正在看 hashmap 源码，刚看到链表转为红黑树那儿（超过 8 个就树化那个函数），然后以深度遍历的方式看着看着，就看到了这里😂