Working of TreeMap

The following two tabs change content below.
Prasad Kharkar is a java enthusiast and always keen to explore and learn java technologies. He is SCJP,OCPWCD, OCEJPAD and aspires to be java architect.

Latest posts by Prasad Kharkar (see all)

Continuing with our articles on understanding of internal data structures, in java, along with previous LinkedHashMap and HashMap, we will further see working of TreeMap in java.

Working of TreeMap:

Unlike LinkedHashMap and HashMap, TreeMap does not use hashing for storing keys. It uses a data structure called Red-Black tree. Understanding of red black trees is beyond the scope of this article. We are just interested in knowing working of TreeMap when each element is added into it.Here, we will simply study the state of TreeMap after each insertion of element. TreeMap will always have all its elements sorted whenever some operation is performed on it.

An Object In TreeMap.

As the name itself suggests, working of TreeMap is based on tree data structure. Each node in tree will have three references i.e. its parent, right and left element. It is depicted as below

Structure of a Node in TreeMap

Structure of a Node in TreeMap

  • The left element will always be logically less than parent element.
  • The right element will always be logically greater than OR equal to parent element

The logical comparison of Objects is done by natural order i.e. those object who implement Comparable interface and override compareTo(Object obj) method. Based on the return value,

  • If obj1.compareTo(obj2) returns negative number, then obj1 is logically less than obj2.
  • If obj1.compareTo(obj2) returns positive number then obj1 is logically greater than obj2
  • If obj1.compareTo(obj2) returns zero, then obj1 is equal to obj2.

 

Example for Working of TreeMap:

We are simply creating a TreeMap with Integer keys and Object as values, we will put all values as null as they are irrelevant.

Now let us understand what happens line by line.

1. treeMap.put(1,null);

Before executing treeMap.put(1, null); there are no elements in it. So 1 is the first object being inserted as key. This is treated as root node for tree and structure for treeMap becomes as below.

First Object Inserted

First Object Inserted

2. treeMap.put(5, null);

Now, 5 is logically greater than 1 and hence according to our rules,

  • will be placed to the right of 1.
  • 1 will be parent of 5.
SecondIntegerInserted

Second Object Inserted

3. treeMap.put(3, null);

As mentioned above, we are only interested in final structure of TreeMap after each object insertion because internally because right now algorithm and implementation of Red black tree is irrelevant to us (We will see it in detail in a few articles). Red Black tree implementation will give us sorted order from left to right. So diagram becomes as below.

Third Object Inserted

Third Object Inserted

  • 1 will be to the left of 3
  • 5 will be to the right of 3

4. treeMap.put(2, null);

Fourth Object Inserted

Fourth Object Inserted

  • 1 will be to left of 3
  • 5 will be to right of 3
  • 2 will be to right of 1

5. treeMap.put(4, null);

Fifth Object Inserted

Fifth Object Inserted

  • 1 will be to left of 3
  • 5 will be to right of 3
  • 2 will be to right of 1
  • 4 will be to left of 5

The article doesn’t explain working of TreeMap with implementation details of red black tree and how it arranged the tree such that it sorts all elements each time they are inserted, but gives a vague idea about how it is structured. I hope the article helped understand the working of TreeMap.

Share Button

9 comments for “Working of TreeMap

  1. Neeraja
    June 16, 2016 at 12:55 am

    do you have any plans on starting blogging on data structures….?

    • June 16, 2016 at 9:23 am

      Hi Neeraja, I am planning to write on Design patterns for a couple of months and then will focus on algorithms and data structures.

  2. Abhishek RC
    January 20, 2017 at 2:49 pm

    could you please let me know why “treeMap.put(3, null);” was considered to be a parent node rather than considered to be a left node of “5” ?

    • Pulkit Chitkara
      January 25, 2017 at 12:12 pm

      Because of Red Black Tree Data Structure. Below are the properties of red-black tree. On these properties “treeMap.put(3, null);” is chosen as a parent node.
      1) Every node has a color either red or black.
      2) Root of tree is always black.
      3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).
      4) Every path from root to a NULL node has same number of black nodes.
      You can go to geeksforgeeks website for more reference.

  3. June 13, 2017 at 5:20 pm

    This is really very useful example of TreeMap.
    thank you for this post

  4. paka
    June 23, 2017 at 12:48 pm

    nice job! helpful ! is the analysis based on JDK7? or JDK8?

  5. Pra
    July 4, 2017 at 4:06 pm

    Typo at :: As mentioned above, we are only interested in final structure of TreeMap after each object insertion *because* internally *because* right now

  6. Asad
    November 2, 2017 at 11:36 am

    nicely explained…thanks

Leave a Reply

Your email address will not be published. Required fields are marked *