红黑树 - 建设

最近，我一直在经历搜索树，我遇到了红黑树，令我困惑的一点是，在RB树中，根节点应该是黑色的，这很好，现在我将如何决定传入节点是否呈现红色或黑色。红黑树 - 建设

我已阅读维基文章，但尚未找到解决方案。我可能是错的，但如果有人能指导我完成确切的材料，我会很高兴。

[编辑] 也就是说，例如，如果我的密钥是{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

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

谢谢。

2010-04-04 Chaitanya

事情是，你永远不会一次画你的整棵树。您总是一个接一个地插入节点并更正树的其余部分 – 2010-04-04 14:40:55

传入的新节点总是先着色RED，然后检查树属性。 – bashmohandes 2010-10-18 22:41:57

看看麻省理工学院开放课件上有关红黑树的讲座。

我发现他们是非常有帮助的。

现在，如果我没记错的话，你总是插入新节点为黑色节点，然后进行必要的修改（重新涂漆和/或旋转）

2010-04-04 01:41:05

是的，我看过视频，但没有找到答案。谢谢你，因为这让我清楚地理解了其他概念。 – Chaitanya 2010-04-04 02:44:29

实际上，您将每个新节点插入为RED（而不是黑色）节点，然后继续进行更正。原因是保持以下属性为真：“对于每个节点，从节点到后代叶子的所有路径都包含相同数量的黑色节点。”如果将新节点插入黑色节点，则会增加其中一个路径上的黑色节点数。 – 2011-09-23 19:06:46

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

2014-10-08 13:08:12 akashchandrakar

回答