Left-leaning Red-Black Trees

I think this is the easiest algorithm to learn and code. Robert Sedgewick’s Java code is always succinct. I have learnt how to code Tries based on his code. Now his Red-black tree code is easy to remember.

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

Though the properties of this type of tree are different from the original Red-black tree I think it is sufficient to remember this condensed code.

These are the three lines and some small methods that we should remember mainly.

        if ( isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if ( isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if ( isRed(h.left) && isRed(h.right)) colorFlip(h);

Original binary tree before rotation

Screen Shot 2014-06-02 at 9.43.10 AM

Final tree

Screen Shot 2014-06-02 at 9.50.41 AM

I think the fundamental rules are these apart from the other Red-black tree rules.

  1. Disallow right-leaning red nodes.
  2. Disallow more than two consecutive red nodes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: