TreeMap and TreeSet are two important members of the Java Collection Framework. TreeMap is a common implementation class for the Map interface, and TreeSet is a common implementation class for the Set interface. Although the interface specifications implemented by TreeMap and TreeSet are different, the TreeSet underlying layer is implemented through TreeMap (just as the HashSet underlying layer is implemented through HashMap), so the implementation methods of the two are exactly the same. The implementation of TreeMap is the red and black tree algorithm
The relationship between TreeSet and TreeMap
It is exactly similar to HashSet, most of the methods in TreeSet are implemented by directly calling the TreeMap method.
Similarities:
- TreeMap and TreeSet are both asynchronous collections, so they cannot be shared between multiple threads, but the synchronization can be achieved using method().
- The running speed is slower than the Hash collection. The internal operation time complexity of the elements is O(logN), while the HashMap/HashSet is O(1).
- TreeMap and TreeSet are both ordered sets, which means that the values they store are all well-ordered.
Differences:
- The main difference is that TreeSet and TreeMap implement Set and Map interfaces respectively
- TreeSet only stores one object, while TreeMap stores two objects Key and Value (only key objects are ordered)
- There cannot be duplicate objects in TreeSet, but it can exist in TreeMap
- The underlying layer of TreeMap adopts the implementation of red and black trees to complete the orderly insertion and sorting of data.
Characteristics of red and black trees:
- Properties 1: Each node is either red or black.
- Property 2: The root node is always black.
- Property 3: All leaf nodes are empty nodes (i.e. null) and are black.
- Property 4: The two child nodes of each red node are black. (There will not be two consecutive red nodes on the path from each leaf to root)
- Property 5: The path from either node to each leaf node in its subtree contains the same number of black nodes.