Before we jump into TreeMap, let us first look into Tree Data Structure.
The basic building block for the tree is the node. Tree is nothing but hierarchial ordering of nodes. Some of the basic definitions are defined below:
Root:The top node in a tree. In the above tree structure “A” is the root.
Parent:The node which is predecessor of any node.In other words the node which has child node(s).In the above tree structure “D” is the parent for “E”,”F” and “G”.
Child:The node which is descendant of any node. In a tree, all the nodes except root are child nodes.In the above tree structure “E”,”F” and “G” are the children of “D”.
Siblings:A group of nodes with the same parent.In the above tree structure “E”,”F” and “G” are the siblings.
Leaf:A node with no children.In the above tree structure “C”,”E”,”F”, “G”,”H” and “I” are the leaf nodes.
Now let us know what is a Binary Tree?
The above is an example of binary tree.Binary tree is a special tree where each node can have no more than two children.
Now let us know what is a Binary Search Tree(BST)?
The above is an example of Binary Search Tree. In this case, a node’s left child must have a value less than its parent’s value and the node’s right child must have a value greater than or equal to its parent value.
Balanced Binary Search Tree(Balanced BST)
Balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically.
Advantages of Balanced BST:
Most operations on a BST take time proportional to the height of the tree, so it is desirable to keep the height small. For normal BST, the worst case for search, add and remove operations is O(n), whereas in case of Binary BST it is O(log n).
Self-balancing binary trees solve this problem by performing transformations on the tree at key times, in order to reduce the height. Although a certain overhead is involved, it is justified in the long run by ensuring fast execution of later operations.
Implementations of Balanced BST
Following are popular Balanced Binary Search tree implementations.
- 2-3 tree
- AA tree
- AVL tree
- Red-black tree
- Scapegoat tree
- Splay tree
Now let us come to our main topic i.e., TreeMap.TreeMap is a Red-Black tree based implementation of Map.
Following are the properties of Red-black tree.
- Every node is either red or black.
- Every leaf is a NIL node, and is colored black.
- If a node is red, then both its children are black. That is a red node can’t have a red child node.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
- The root node is always black
We will not go in deep into Red-Black Tree as it is based on some complex algorithms and in any case these internal details are not needed for us.
In TreeMap the entries(key-value pairs) are sorted based on the keys.
The objects to be used as key in the TreeMap should implement Comparable interface.Otherwise a Comparator which can compare the keys needs to be passed an argument while creating the TreeMap.
Let us take the example of Employee. In this case, the natural ordering of the Employee is by Id. We have also created two Comparators SalaryComparator and NameComparator to sort Employees by Salary and Name respectively.