Red-Black Tree

Red-Black Tree is a height balanced tree. In this tree, extra color information ( apart from Node value,left and right pointer ) is stored to distinguish whether node is red or black.So RB tree has following properties.

1. Every Node has either color Red or Black.
2. Root is always Black.
3. Two adjacent nodes can not be Red.
4. Number of Black Node from Root to any leaf node must be same

By default, NULL leaf node color is BLACK.

So above 4 properties must be followed in case of  RB tree. NULL nodes are generally
Main purpose of a height-balanced RB tree is to ensure any search/insert/delete operation on this tree is O(logn) of time complexity.Thus, disadvantage of skew tree is avoided.

  

Now we will see, how above 4 properties ensure that the tree is height balanced.

As per property 1 , Root node of tree must be black .

Tree cannot be skewed as Property 4 will be violated as no. of black node in different path may differ.

But we can make most of nodes as red to obey property 4 in a  skewed tree but if we do so, property 3 will be violated as two node may be placed adjacent to each other

So we have to distribute red and black node such a way that all the proprieties would be satisfied.and tree will remain as balanced.

So if tree remains balanced, then search will take O(logn) of time as per BST search operation .Now we will see how insertion and deletion takes place in RB tree.In RB tree, when we do any insertion/deletion, we have to perform below two operation to make tree balanced again.

• Rotation
• Recoloring

In insertion , by default color of new node is RED and problem arises when newly inserted node's parent is also RED. So after insertion/deletion

Insertion Logic

1.  Mark the new node as RED and perform insertion as we are doing in a binary search tree.
2.  If parent of new node is BLACK , then no need to do anything.
3. If parent node is RED, then check color of the sibling of parent node i.e uncle node.
1. If color of uncle node is RED, then color of parent of parent i.e. grandparent node must be BLACK to satisfy property 4. Then perform recoloring where change the color of parent and uncle node to BLACK and color of grandparent to RED.Now consider grandparent node as new inserted node and perform step 3 and 4 iteratively.
2. If  color of uncle node is black then we have to perform below rotation and recoloring operation.
1. LL Operation
2. RR Operation
3. LR Operation
4. RL Operation
3.  After LL and RR rotation we perform and below recoloring step and for LR and RL rotation we perform recoloring after first rotation(left/right) and before second rotation(right/left) respectively
1. set color of parent as BLACK
2. set color of grand parent as RED.
4. If new node is root, the change the color to BLACK

In java, TreeMap is implemented using RB tree . Below code is extracted from TreeMap.java where balancing has been performed after BST insertion of new node.

 private void fixAfterInsertion(Entry x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Entry y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

    private static  boolean colorOf(Entry p) {
        return (p == null ? BLACK : p.color);
    }

    private static  Entry parentOf(Entry p) {
        return (p == null ? null: p.parent);
    }

    private static  void setColor(Entry p, boolean c) {
        if (p != null)
            p.color = c;
    }

    private static  Entry leftOf(Entry p) {
        return (p == null) ? null: p.left;
    }

    private static  Entry rightOf(Entry p) {
        return (p == null) ? null: p.right;
    }

    /** From CLR */
    private void rotateLeft(Entry p) {
        if (p != null) {
            Entry r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

    /** From CLR */
    private void rotateRight(Entry p) {
        if (p != null) {
            Entry l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }