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;
        }
    }

In-depth Analysis of TreeMap in Java

Treemap is first introduced in java 1.2 .

We have already used Map (Hashmap/concurrentHashMap)and doing any operation on this map data structure takes  time complexity of O(1). So in general we prefer Hash map to store and retrieve key value pair. But if we want a little modification such as storing key-value pair in sorted order i.e key in order then, underlying data structure of hashmap doesnot  support that.For this TreeMap is introduced .Though it supports all the functionality s of a Map , but its time complexity differs from hashmap as its underlying data structure is a Tree (Red-Black tree).All operation like put/get/containsKey takes O(logn) time.Below, some features of treemap are mentioned.

• By Default tree map sorts its key in natural order.
• Sorting can be customized by passing comparator during creation of treemap.
• It uses a Red-Black Tree.
• It is not synchronized i.e 2 or more thread can operate on same data simultaneously.As it is not synchronized, it operates faster compared to any synchronized or concurrent counter-party.In Multithreaded environment it can be synchronized .SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
• Iterators returned by this collection class is fail-fast.So any structural modification in tree map during iteration  will throw Concurrent Modification Exception.So in this cases, it fails quickly instead of giving  non-deterministic behaviour.
• present in Java.util package
• This class Extends AbstactMap and implements NavigableMap, Cloneable and Serializable.

• Treemap extends abstract class AbstractMap which implemets Map Interface.AbstactMap gives skeletal implementaion of Map Interface where entryset() is  the abstarct method .AbstactMap gives an unmodifiable map as put() throws UnsupportedOpertionException in it .So To design an unmodifiable map class, extend this class and does not override put(). But to create an Modifiable map class extend AbstractMap and override put().
• Besides Treemap implements NavigableMap interface which extends SortedMap interface which extends Map Interface.Class which implements SortedMap interface should implement functions like comparator(),submap(),headmap(),tailmap().firstkey(),lastkey() etc.And class which has implemeted NavigableMap (which implicitly extends sortedMap) contains implementations of all navigation methods like lowerEntry(), floorEntry(), ceilingEntry(), higherEntry(),lowerKey, floorKey, ceilingKey, and higherKey() etc.

Internally TreeMap uses RB tree, but underlying data structure can be array and can perform binary search operation to achieve the same goal , but problem will be array  takes contiguous memory and dynamic memory allocation is cumbersome for huge amount of data .Also insertion and deletion operation takes O(n) of time as for each insertion or deletion , other array elements has to shift one index down/up. Linked list can be preferred as all operation takes O(n) time. So linear data structure is not a good option .In among non-linear data structure, tree is the best option.So, we need a binary search tree but problem is it may be skewed and worst case time complexity will be O(n). So, an balanced binary search tree is preferred . In balanced BST, lots of options are available like AVL tree , RB tree. But RB tree is preferred as it uses less no. of rotation during insertion and deletion compared to AVL tree.For more Details on Red-Black tree and AVL tree click respective links.

In AVL tree, it stores balance factor in each node, So when any insertion and deletion happen on this tree, it may do rotation and calculation of balance factor of every node present in tree hierarchy upto root node .So , in worst case O(logn) of operation can happen in AVL tree. But in RB tree, recoloring and rotation happen less compared to AVL tree.

Below is the code snippet (extracted from TreeMap.java) for balancing the RB tree after insertion of any node is done (BST insertion) .
  

  
  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;
    }

Below is the code snippet (extracted from TreeMap.java) for balancing the RB tree after deletion of any node is done (BST deletion)

private void fixAfterDeletion(Entry x) {
        while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {
                Entry sib = rightOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                Entry sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }

        setColor(x, BLACK);
    }