TreeMap
TreeMap
It is available since Java 1.2
It extends the AbstractMap class.
It implements the Colneable, Serializable, NavigableMap interfaces.
Through AbstractMap it also implements the Map interface.
TreeMap has four constructors
TreeMap();
TreeMap(Comparator comp);
TreeMap(Map map);
TreeMap(SortedMap smap);
Characteristics
Red-Black tree is a self balancing Binary Search Tree where each node has Red or Black color and each node has to following some specific rules.
Rules to follow by each nodes:
1) Each node must have either red or black color.
2) Root Node cannot have any parent node.
3) Each node can have max two child nodes (Left and Right)
4) Two red nodes cannot be adjacent. ( a red node cannot have red parent or red child)
5) All the right nodes of particular node will be greater than or equal to that node.
6) All the left node will be less than or equal to thatn node.
7) Every path from the root node to the last null node must have same number of black nodes.
The time taken by all operations (search, insert, delete etc) in BST(binary search tree) is O(h) time. Here 'h' is the height of the tree.
The height of the RedBlack Tree is always O(log n) here 'n' is the number of nodes in the tree.
Example:
import java.util.Comparator;
import java.util.TreeMap;
public class TreeMapFlight {
public static void main(String[] bag){
TreeMap<Integer,String> tm = new TreeMap<Integer,String>(new MyComp());
tm.put(1, "one");
tm.put(null, "null1");
tm.put(null, "null2");
tm.put(null, "null3");
System.out.println(tm);
}
}
class MyComp implements Comparator{
@Override
public int compare(Object o1, Object o2) {
return 1;
}
}
Output:
{1=one, null=null1, null=null2, null=null3}
It is available since Java 1.2
It extends the AbstractMap class.
It implements the Colneable, Serializable, NavigableMap interfaces.
Through AbstractMap it also implements the Map interface.
TreeMap has four constructors
TreeMap();
TreeMap(Comparator comp);
TreeMap(Map map);
TreeMap(SortedMap smap);
Characteristics
- The implementation of TreeMap is based on the Red-Black tree structure.
- The data in the TreeMap is sorted according to the comparable natural ordering.
- The default ordering can be changed by providing required comparator at the creation time of TreeMap.
- All the key elements which are being inserted into the TreeMap must be comparable. Means key elements class must implement the comprable or comparator.
- If key elements violates this rule will throw a ClassCastException.
- TreeMap does not permit the null key with natural ordering.
- TreeMap can have multiple null values.
- Storing duplicate key in the TreeMap will replace the previous value with the new value for that key.
- Note: user can store multiple null keys in TreeMap using user defined comparator in certain tricky way.
Red-Black tree is a self balancing Binary Search Tree where each node has Red or Black color and each node has to following some specific rules.
Rules to follow by each nodes:
1) Each node must have either red or black color.
2) Root Node cannot have any parent node.
3) Each node can have max two child nodes (Left and Right)
4) Two red nodes cannot be adjacent. ( a red node cannot have red parent or red child)
5) All the right nodes of particular node will be greater than or equal to that node.
6) All the left node will be less than or equal to thatn node.
7) Every path from the root node to the last null node must have same number of black nodes.
The time taken by all operations (search, insert, delete etc) in BST(binary search tree) is O(h) time. Here 'h' is the height of the tree.
The height of the RedBlack Tree is always O(log n) here 'n' is the number of nodes in the tree.
import java.util.Comparator;
import java.util.TreeMap;
public class TreeMapFlight {
public static void main(String[] bag){
TreeMap<Integer,String> tm = new TreeMap<Integer,String>(new MyComp());
tm.put(1, "one");
tm.put(null, "null1");
tm.put(null, "null2");
tm.put(null, "null3");
System.out.println(tm);
}
}
class MyComp implements Comparator{
@Override
public int compare(Object o1, Object o2) {
return 1;
}
}
Output:
{1=one, null=null1, null=null2, null=null3}