1

最近在搜索树，遇到了红黑树，困惑的一点是，在rb树中，根节点应该是黑色的就好，现在我将如何决定传入节点是红色还是黑色.

我已经浏览了 wiki 文章，但没有找到解决方案。我可能是错的，但如果有人能指导我了解确切的材料，我会很高兴。

[编辑] 例如，如果我的键是 {7, 2, 4, 1, 9, 10, 8}

这里 7 是根，它呈现黑色，但 2 呈现什么颜色？我们如何决定呢？我们如何决定其他节点采用什么颜色？

                                  7 - (Black)
                   2                              9
           1                   4        8                    10
        NIL   NIL          NIL  NIL   NIL  NIL            NIL  NIL

我们是否有随机折腾来决定节点的颜色是红色还是黑色。或者是其他一些过程。

谢谢你。

4

2 回答 2

1

看 MIT 开放课件上关于红黑树的讲座。

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/

我发现它们非常有帮助。

现在，如果我没记错的话，您总是将新节点插入为黑色节点，然后进行必要的更正（重新绘制和/或旋转）

于 2010-04-04T01:41:05.843 回答
1

传入节点必须为红色，因为如果将传入节点着色为黑色，则新插入节点的所有叶到根路径的高度将增加一，这将违反每个根到叶路径必须的 RB 树属性包含相同数量的黑色节点。如果您想更深入地了解 RB 树http://www.youtube.com/watch?v=6QOKk_pcv3U

于 2014-10-08T13:08:12.250 回答