TreeMap Implementation in Java

As the name suggests; TreeMap (i.e. TreeMap<K, V>) is a map implementation which is based on a binary search tree. It's an ordered map implementation where keys are comparable.  HashMap doesn't guarantee any order for keys, but TreeMap stores key in a sorted way. This allows you to use queries like find all keys lesser than a given value, find the smallest, largest etc. It sorts the keys in natural order i.e. considers them an instance of a Comparable interface (if Comparable is implemented). During creation, we can also provide an optional Comparator instance(discussed in detail, here). 

This post, I will be focusing mostly on the implementation aspect of TreeMap. It might be helpful to go through earlier post where I have talked about implementation of HashMap and LinkedHashMap.

Building Blocks

Let's cover major components of  TreeMap.

Red-Black Tree: TreeMap uses a Red-Black tree based NavigableMap implementation. A red-black tree is a self-balancing binary search tree; so most of the operations like search, get, put, remove take O(log n) time. This gets guaranteed by ensuring that after every insertion/deletion the upper bound on height is O(log n) i.e. tree is balanced. Red-Black tree colors every node as either red or black and follows certain rules to ensure that the tree remains balanced. Although AVL trees are more balanced compared to the Red-Black tree, Red-Black tree performs better if there are many frequent insertions and deletions.

The tree uses these two techniques for balancing :

• Recoloring
• Rotation 

The red-black tree first tries to re-color the node/s to balance the tree; if it doesn't work then it goes for rotation technique.

More details of this tree can be found, wikipedia.

I have discussed generic binary search tree implementation in Java, here.

Entry: Just like HashMap and LinkedHashMap; TreeMap also uses Entry node to store key, values pairs of each entry.

static final class Entry<K,V> implements Map.Entry<K,V>{

        K key;

        V value;         

        Entry<K,V> left;

        Entry<K,V> right;

        Entry<K,V> parent;

        boolean color = BLACK;  

        

       //other methods

}

Entry class represents the node of the tree. Along with key and value pairs, it stores references to the left and the right subtree as well. Also, unlike a normal Binary search tree, every node stores reference to its parent. This is required for rotating nodes to balance the tree. And as discussed above; it colors all nodes either red or black. Root node gets colored as black.

Note, one important difference in Entry class of TreeMap compared with HashMap and LinkedHashMap. TreeMap doesn't use hashing to perform operations. (i.e. Entry class doesn't have hash attribute)

Root: Stores the root node of the tree for traversal.
  private transient Entry<K,V> root;

Put Method: Put method is used to inserting key, value pair in the map. Insertion is similar to inserting a new node in the binary search tree. It uses Comparable or Comparator interface to compare key with the key of root node. And based on the returned value (-1, 0 or +1 ) it takes appropriate action. To get an idea of how it works; please go through this post. 

Another important thing worth mentioning is; after every insertion, TreeMap ensures that the tree is balanced, here.

Get Method: Get also works similar to the get of a binary search tree. Recursively traverses the tree until it finds the node. It traverses by using the binary search tree property (i.e. root.data > root.left.data and root.data < root. right.data).

Related Posts: HashMap Implementation, LinkedHashMap Implementation

--- 

happy learning!!!