我在红黑树中插入了节点 36，结果如下红黑树：
我的问题是在这种特殊情况下如何处理双红？是案例2还是3？
问问题
482 次
2 回答
1
基于维基百科的属性和案例...
36将插入到案例 5 下，22向左旋转。
父母 P 是红色的，但叔叔是黑色的或不在那里。
维基百科只是说“叔叔是黑人”，但是，看看代码，你会看到那个案例触发了。
请注意，没有的树36已经无效，因为属性 5（从任何给定节点到其叶节点的所有路径都包含相同数量的黑色节点）没有被保存：
- 20 到 15 包含 1 个黑色节点
- 20 到 30 包含 2 个黑色节点
假设插入顺序是20, 15, 22, 30, 36......
所有节点都插入为红色。
22将插入到案例 2 下。
父母是黑人。
30将插入案例 3 下，制作黑色和22红色。1520
父母和叔叔是红色的；两者都被重新漆成黑色，祖父母变成红色。
36将插入到案例 5 下，22向左旋转。
父母 P 是红色的，但叔叔是黑色的或不在那里。
于 2013-11-06T09:38:41.640 回答
0
22没有左孩子
所以..
案例一：重组
我们将离开旋转
30 --> 根“黑色”
22--> 左孩子“红”
36--> 右孩子“红”
于 2019-07-02T02:18:45.617 回答