A binary tree can be made into different self-balancing trees with different sets of additional conditions, such as the AVL tree and the Red-Black Tree.
The TreeMap in Java is a red-black tree. However, each node consists of a key and corresponding value (key/value pair) instead of just a key. Each key/value pair would be one element in an array-like structure. This article explains how to use a TreeMap in Java, beginning with a binary search tree, followed by the red-black tree, and then the Java TreeMap.
Article Content
- Binary Search Tree
- Red-Black Tree
- Key/Value Pairs for Java TreeMap
- Java TreeMap Construction
- Java TreeMap Methods
- Conclusion
Binary Search Tree
The following is an example of a binary search tree:
Each node has a key. The key (value) for the root node is 8. The left child is 3 and the right child is 10 (10 >= 3). It can be seen that for any node that has two children, the right child is greater than or equal to the left child. Also, the right half of the tree has values that are greater than those of the left half of the tree for each level.
All the values of the above tree can be placed in an array, as follows:
Notice that the array (tree) begins at 8; descends to 3, then rises to beyond 8 at 10; descends to 1, rises to 6, then has NILs, until 14; descends to 4; rises to 7; NILs again; then 13 and the last NIL.
8 is the first value at index 0. It is the root node (root parent). It is not necessarily the biggest value among all the values. Its first child (3) is at index 1, the index of which is equal to 2(0) + 1, where 0 is the index of the parent. Its second child (10) is at index 2, which is equal to 2(0) + 2, where 0 is the index of the parent.
3 is at index 1. It is a parent. Its first child (1) is at index 3, which is equal to 2(1) + 1, where 1 is the index of the parent. Its second child (6) is at index 4, which is equal to 2(1) + 2, where 1 is the index of the parent.
6 is at index 4. It is a parent. Its first child (4) is at index 9, which is equal to 2(4) + 1, where 4 is the index of the parent. Its second child (7) is at index 10, which is equal to 2(4) + 2, where 4 is the index of the parent.
10 is at index 3. It is a parent. It has no first (left) child, which was supposed to be at index 7, which is equal to 2(3) + 1, where 3 is the index of the parent. Its second child (14) is at index 8, which is equal to 2(3) + 2, where 3 is the index of the parent.
14 is at index 8. It is a parent. Its first child (13) is at index 17, which is equal to 2(8) + 1, where 8 is the index of the parent. It has no right (second) child, which was supposed to be at index 18, which is equal to 2(8) + 2, where 8 is the index of the parent.
In general, as index counting begins from 0. Let i represent the index of a parent of the array; and so, the left (first) child of a parent at index i, is at index 2i + 1; and its right (second) child, is at index 2i + 2. Some cells in the array may be empty; they must not have values.
Red-Black Tree
A red-black tree is a binary search tree, that is balanced. The following is an already balanced red-black tree:
A balanced tree is a tree with a short height. The node positions are changed and marked with red and blue colors to have the shortest tree height possible in its development.
Using the formulas, 2i + 1 and 2i + 2, the values can be put in an array-like structure as follows:
Notice that the array starts at 13, descends to 8 and then rises to 17. It then descends beyond 8 to 1 and then rises to 11, then 15, then 25; from which there is a NIL, and then it descends to 6. NILs follow before 22 and 27.
The array of a balanced tree, like the red-black tree above, has fewer NILs than its corresponding binary search tree that is not balanced. The array length of a balanced tree is shorter than the corresponding tree that is not balanced.
A red-black tree is a partially ordered tree.
Key/Value Pairs for Java TreeMap
The previous red-black tree has only keys as node values. Each integer key can be given a corresponding string value. The following list has the same keys with corresponding values:
These are key/value pairs suitable for a Java TreeMap. Each key will be mapped to its corresponding value. A key/value pair is called a map-entry in Java. For the Java TreeMap, the arrangement of the nodes is made by keys (not values of the key/value pairs). Each key is mapped to its value.
Java TreeMap Construction
In Java, TreeMap is a class in the java.util.* package, which should be imported. This class has four constructors, and two constructors are illustrated in this article.
Public TreeMap()
This constructs an empty TreeMap. The following code segment illustrates this:
The put() method includes key/value pairs to the TreeMap. After all this, the TreeMap becomes balanced internally.
Public TreeMap(Map<? extends K,? extends V> m)
This constructor method creates a map from another already created map, as in the following code segment:
tm.put(13, "thirteen"); tm.put(8, "eight"); tm.put(17, "seventeen"); tm.put(1, "one");
tm.put(11, "eleven"); tm.put(15, "fifteen"); tm.put(25, "twenty-five"); tm.put(6, "six");
tm.put(22, "twenty-two"); tm.put(27, "twenty-seven");
TreeMap<Integer,String> tm1 = new TreeMap<Integer,String>(tm);
tm1 is created from tm. After all this, both TreeMaps balanced internally; with the first one balanced first. Balancing takes place as keys include pairs.
Java TreeMap Methods
Public V put(K key, V value)
Strictly speaking, the put() method does not add a key/value pair. It associates a particular value to a particular key. If the key already existed in the TreeMap with a different value, the value is replaced with the new one. This method returns the old value or null if there was no old value. The use of this method has been demonstrated above.
Public int size()
This method returns the number of key/value mappings (pairs) in the TreeMap. The following code segment shows how to use it:
The output is 10, indicating that there are 10 key/value pairs in this TreeMap object.
Public V get(Object key)
This method returns the value corresponding to the argument, which is the key. It returns null if the key does not exist. The following code illustrates this for the key/value pair: 11/”eleven”, and for the key, 40, which does not exist:
The output is:
Public Set<K> keySet()
This method returns a set-view of the keys that are in the TreeMap. To display the keys, the iterator has to be used. The following code segment for the previous TreeMap illustrates this:
The output is:
The return list is completely sorted (ascending), though the TreeMap has partial internal sorting.
Public Collection<V> values()
This returns the collection-view (list) of all the values in the TreeMap, without the keys. To display the values, the iterator has to be used. The following code segment for the previous TreeMap illustrates this:
The output is:
The values have been displayed based on their complete sorted keys (ascending), though the TreeMap has partial sorting internally.
Public Set<Map.Entry<K,V>> entrySet()
This returns a set of key/value pairs. To display the keys and their corresponding values, the iterator has to be used. The following code segment for the above TreeMap illustrates this:
The output is:
6 => six
8 => eight
11 => eleven
13 => thirteen
15 => fifteen
17 => seventeen
22 => twenty-two
25 => twenty-five
27 => twenty-seven
The pairs have been displayed based on their complete sorted keys (ascending), though the TreeMap has partial sorting internally.
Conclusion
In Java, a TreeMap is a red-black tree, which is a self-balancing binary search tree. The commonly used methods and the Java TreeMap construction have been discussed in this article. We hope you found this information helpful. Check out the other Linux Hint articles for more tips and tutorials.
