红黑树 - 构造
最近，我一直在遍历搜索树，遇到红黑树，让我困惑的是，在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
我们是否有随机抛掷来决定节点的颜色是红色还是黑色。或者是其他一些过程。
谢谢。
Recently, I have been going through search trees and I encountered red-black trees, the point confusing me is, In r-b tree, the root node should be black thats fine, now how will I decide whether the incoming node assumes red or black color.
I have gone through the wiki article but have not found a solution for this. I might be wrong, but I would be happy if someone can guide me through the exact material.
[Edit]
That is for example, if my keys are {7, 2, 4, 1, 9, 10, 8}
Here 7 is root and it assumes black color, but what color does 2 assume? How do we decide that? And how do we decide what color the other nodes assume?
7 - (Black)
2 9
1 4 8 10
NIL NIL NIL NIL NIL NIL NIL NIL
Do we have a random toss that decides the color of the node to be red or black. Or is it some other process.
Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
看一下MIT开放课件上关于红黑树的讲座。
http://ocw.mit .edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/
我发现它们非常有帮助。
现在，如果我没记错的话，您总是将新节点插入为黑色节点，然后进行必要的更正（重新绘制和/或旋转）
Look at the lecture about red-black trees on MIT open courseware.
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/
I found them to be very helpful.
Now if I remember correctly, you always insert new node as black node and then proceed to the necessary corrections (repainting and/or rotations)
传入节点必须为红色，因为如果将传入节点着色为黑色，则新插入节点的所有叶到根路径的高度将增加 1，这将违反每个根到叶路径必须的 RB 树属性包含相同数量的黑色节点。如果您想更深入地了解 RB 树的插入，请参阅此内容 http:// www.youtube.com/watch?v=6QOKk_pcv3U
The incoming node must be colored RED because if you color an incoming node to be black than height of all leaf to root path for newly inserted node is going to increase by one which is going to violate RB tree property that every root to leaf path must contain equal number of black nodes.Refer this if you want more insight in insertion of RB tree http://www.youtube.com/watch?v=6QOKk_pcv3U