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

2019-12-22 18:50:21 +08:00
 amiwrong123
                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 友们的指点啊!

其实有点思路,但又不知道对不对:

不行了,我已经懵了,说得有点乱,见谅。PS:v 友推荐的 draw.io 真香

3653 次点击
所在节点    Java
8 条回复
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
@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 个就树化那个函数),然后以深度遍历的方式看着看着,就看到了这里😂

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/631271

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX