hashmap 里红黑树操作 balanceInsertion 的一个疑问？我懵了，你呢
amiwrong123 · 2019-12-22 18:50:21 +08:00 · 3726 次点击这是一个创建于 1817 天前的主题，其中的信息可能已经有所发展或是发生改变。
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/ 大家将就看一下吧
 |
1
crackhopper 2019-12-23 11:12:48 +08:00
我觉得你的算法最后需要把 xpp 那个红色，变成黑色。然后调整前后，黑色深度变了。
另外红黑树算法不是一个直观的对 2-3-4 树算法的变换么，2-3-4 树算法怎么样，对应红黑树算法怎么调整。 |
 |
2
amiwrong123 OP @crackhopper
“你的算法”指的是第二个图呗。把 xpp 那个红色，变成黑色，那好像就更不对了啊。而且我第二个图肯定是错误的思路，只是我想论证为什么它是错误的。 什么！！！还他么有个 2-3-4 树啊，我已经学不过来了。学完这些树，自挂东南枝 |
|
3
crackhopper 2019-12-23 11:38:26 +08:00
@amiwrong123 红黑树性质：红色不能相邻。另外 2-3-4 树来理解红黑树更容易。你值得拥有。（红色+黑色节点就是模拟 2-3-4 树的节点的）
|
|
4
amiwrong123 OP @crackhopper
虽然它值得拥有，但是我现在可能没时间去拥有它😂（刚百度了一下，好像没咋看懂）。而且 hashmap 刚好有红黑树的所有实现，我合计从代码里理解红黑树，应该会更加深刻。 |
 |
5
hehheh 2019-12-23 12:59:46 +08:00
红黑树的 case 表太多了，我以前花了 1 天时间去专门理解不同的 case 是怎么处理的，然后现在全忘光了。维基百科上讲的挺好的。
|
|
6
amiwrong123 OP |
|
7
hehheh 2019-12-23 14:43:41 +08:00
@amiwrong123 不回你的原因是很多人根本不会去手写红黑树， 除了无聊在校大学生，比如若干年前的我。还有就是我觉得这个面试不会问，最多问你红黑树的大致原理以及为什么发明这个东西。
|
|
8
amiwrong123 OP @hehheh
好吧，手写红黑树那可太难了。我也就是看看源码，再自己理解下。 从面试角度说，确实应该不会问这么细。大致原理现在我也了解了（其实就是看看博客），就是现在正在看 hashmap 源码，刚看到链表转为红黑树那儿（超过 8 个就树化那个函数），然后以深度遍历的方式看着看着，就看到了这里😂 |
Select Language