red-black tree - construction

Question

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.

Answer 1

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)

Answer 2

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