红黑树构造

Question

最近，我一直在搜索树，我遇到了红黑树，令我困惑的是，在r-b树中，根节点应该是黑色的，这很好，现在我将如何决定传入节点是红色还是黑色。

我已经看过了维基文章，但还没有找到解决这个问题的方法。我可能是错的，但如果有人能指导我通过确切的材料，我会很高兴。

编辑，例如，如果我的密钥是{7，2，4，1，9，10，8}

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

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

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

谢谢。

Answer 1

请看麻省理工学院开放式课件中关于红黑树的讲座。

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

我发现他们很有帮助。

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

Answer 2

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