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.

The thing is, you never paint your entire tree in one shot. You always insert your nodes one by one and correct the rest of your tree — Gab Royer
The incoming new node always colored RED first, then you do the check on the tree properties. — bashmohandes

Gab Royer Gab Royer · Accepted Answer · 2010-04-04T01:41:05

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)

red-black tree - construction

2 Answers