Red black trees : Understanding the constraints

This post is not an another article which describes RB Trees. This one tries to explain the need for node coloring constraints described in the RB Tree design.

What are RB-Trees

- These are balanced binary trees with each node having one extra property. `color`
- The node colors can be
       - Red
       - Black

Constraints while coloring the tree

1. Root is `black`
2. Red node can have only black children
3. For each path to every leaf in the tree, there are same number of black nodes.

Need for these constraints.

The need for the RB Trees and these constraints is to keep a binary tree as balanced as possible. In this section we will prove these constraints help us in doing so.

Let's start with an assumption that, there exists a completely balanced binary tree with height `h` and we color every node in this tree with a single color `black`.

Balanced binary tree with all nodes colored black

When a new node is inserted in to this binary tree, it creates an imbalance. Because path to one of the leaf is longer than the paths to other leaves.

Imbalance created after one node insertion

Constraint 3 tries to keep this imbalance in control. It enforces us to color one of the node as red in the new path (the one which is longer than others).

Leaf is colored red. Constraint 3 holds.

But we can still create imbalance by coloring every new node inserted in this new path as `red`. This way the new path can grow without a limit.

Constraint 3 holds, but still we can cause imbalance

Constraint 2 solves this problem. Now a red node cannot have red children. So at worst case, the path can grow up to twice the number of black nodes in that path (2 * h). (The node colors alternate from root to the leaf in the path)

Tree honoring constraint 2. (We recolored the tree)

There are two ways possible to color such path. One starts with `black` root and other with `red`.

If the root was colored `red`, the children of root should be colored `black` (Constraint 2). In this case a RB-Tree with only two nodes violates the constraint 3. So constraint 1 says color the root with `black`.

-Madhusoodan

Language support for "Conditional Method Call"

While going through the Hadoop HDFS code, I saw three lines of code repeated everywhere when a debug statement must printed (see below).

    if (DFSClient.LOG.isDebugEnabled()) {
        DFSClient.LOG.debug("...");
    }


Well everything is correct in this code. But when you start to see this first line repeating everywhere in the code it gets really annoying. There is a workaround but it has some cost. Let's see it.

Workaround 1.
Create a Logger class which has log level set. And checks whether it should emit the log to output stream.

    class Logger {
        public static final int DEBUG = 0;
        public static final int LOW = 1;
        public static final int MEDIUM = 2;
        public static final int HIGH = 3;

        private int level;
        private PrintStream strm;

        public Logger(PrintStream strm, int level) {
            this.level = level;
            this.strm = strm;
        }

         public void debug(String s) {
            if(level <= DEBUG)
                strm.println(s);
            }
        }
        ...
    }

To use this.
    Logger LOG = new Logger(strm, Logger.DEBUG);
    LOG.debug("Hello world!");


But this is going to affect the performance as the evaluation of the arguments happen before the level value is checked. If someone does a computation for printing then it would be wasted if log level is not set. Instead I propose a language support for this condition check before making a function call and evaluation of the arguments.

For language such as Java I propose a keyword preval which can used to mark the argument (must be boolean). Only this argument must be evaluated before doing the further argument processing. So the debug code may look something like.

    public void debug(String s, preval boolean shouldPrint) {
        strm.println(s);
    }

And should be used as
    DFSClient.LOG.debug("...", DFSClient.LOG.isDebugEnabled());

Well this is also annoying as you have to pass this boolean argument everytime you make call to debug. There is further room for improvement for languages which support methods with default arguments (with evaluation). Then the debug method could be written as

    public void debug(String s, 
        preval boolean shouldPrint=(this.level<=DEBUG)) {
        strm.println(s);
    }

To use this method we can either pass the argument explicitly or write
    DFSClient.LOG.debug("...");

This makes the code really crisp and cute (without those annoying if checks everywhere). If any Java language developer ever see this blogpost please try to implement this. (I couldn't find any place to suggest modifications to Java language)

Endianness of a machine

Have you ever thought which type of memory architecture (Little Endian or Big Endian) your machine has. Can you write a program to find this?

I recommend you to first try this minimizing the browser....

Tired up pulling your hairs off....
Here is the solution

#include<stdio.h>
int main(void) 
{
    int h = 1;
    char* chptr = (char*)&h;
    if(*(chptr + 1) == 0)
        printf("Little-Endian Machine.");
    else
        printf("Big-Endian Machine.");
    getchar();
    return 0;
}