How do TreeMap and TreeSet stay sorted in Java, and what data structure do they use?
Both of them keep their entries in order, and they do it by holding them in a tree.
The tree is a self balancing binary search tree, usually called a red-black tree. Each entry is a node, and every node keeps the entries on its left smaller than itself and the entries on its right larger than itself. The tree balances itself as entries are added and removed, so the height stays small.
That structure is what makes them fast. Finding an entry, adding one and removing one all take a number of steps that grows with the logarithm of the number of entries, rather than with the number of entries themselves. So a tree with a million entries is still found in about twenty steps.
Here is what the ordering looks like in practice.
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
TreeSet<String> names = new TreeSet<String>();
names.add("Grace");
names.add("Ada");
names.add("Alan");
System.out.println("the set is sorted : " + names);
TreeMap<String, Integer> ages = new TreeMap<String, Integer>();
ages.put("Grace", 45);
ages.put("Ada", 36);
ages.put("Alan", 41);
System.out.println("the map is sorted : " + ages);
System.out.println("the first key : " + ages.firstKey());
System.out.println("the last key : " + ages.lastKey());
}
}
So the answer to the question is this. They use a self balancing binary search tree, which keeps the entries in order and keeps every operation at a logarithmic cost.
The next question in this topic looks at how to change the order.