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