Sunday, June 1, 2014

TreeMap Implementation in Java

As the name suggest; TreeMap ( i.e. TreeMap<K,V>) is a map implementation of Java which is based on 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 sorted way. This allows you to use queries like find all keys lesser than a given value, find smallest, largest etc. It sorts the keys in natural order i.e. considers them instance of 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 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 Red-Black tree based NavigableMap implementation. 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 tree remains balanced. Although AVL trees are more balanced compared to Red-Black tree, but Red-Black tree performs better if there are many frequent insertions and deletions.

Tree uses these two techniques for balancing :
  • Recoloring
  • Rotation 
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 node of the tree. Along with key and value pairs it stores references to left and 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!!!

2 comments:

  1. Really Helped a lot, Its because of contributors like you, Complex Fundas are easier to grasp .

    ReplyDelete
  2. Nice explanation

    ReplyDelete