TreeSet and TreeMap in Java are implemented by Red-Black Trees. See my CS 61B notes.

Some solutions use TreeSet/TreeMap to keep elements sorting in subarrays or sliding windows. Since their APIs are not common, I write this post to summarize some usage. Also, I will mention a bit about binarySearch() although most of the time we need to implement different binary search versions by ourselves.

TreeSet / TreeMap

When we want to keep entries sorted in a map, we use TreeMap. Major operations on a TreeMap takes $O(\log{N})$ time.

1
2
Map<Integer, String> map = new TreeMap<>();
TreeMap<Integer, String> map = new TreeMap<>();
  • If we use get(K) and put(K, V) only, we can use Map as the static type.
  • If we want to use something not in the Map interface (e.g. ceilingKey() and floorKey()), we should use TreeMap as the static type.

Sorted by Keys

Entries in TreeMap are sorted by keys. It is not natural to make them sorted by values, although it is possible (the code is more complex than we think).

Imagine someone might write this code:

1
2
3
TreeMap<Integer, String> map = new TreeMap((k1, k2) -> {
  return map.get(k1) - map.get(k2);
});

It turns out that there is a compiling error. You can try this out by yourself. It is actually a design problem. If you want to use the property in a map that we can access a key quickly and that keys are unique, we can’t sort items by values. It is because values are not unique, two keys might be corresponding with the same value. It is a tie case.

Definition: A Map that further provides a total ordering on its keys.

Further Reading: TreeMap sort by value

Alternative: Use a hash map. Put keys in a list, and pass in a comparator based on map.get(k1) - map.get(k2).

Usage

1
2
3
4
5
6
TreeMap<Integer, String> map = new TreeMap<>();
map.put(2, "A");
map.put(5, "B");
map.put(6, "C");
map.put(8, "D");
// print: [2: "A", 5: "B", 6: "C", 8: "D"] (sorted)

Lower Bound:

It is a lower-bound method since we specify a lower-bound value K.

  • higherKey(K) / higherEntry(K)
  • ceilingKey(K) / ceilingEntry(K)

We use them when we want to find the least key greater than K (or equal for ceiling). 

1
2
3
4
5
6
7
8
9
10
11
map.higherKey(1);  // 2
map.ceilingKey(1); // 2

map.higherKey(2);  // 5
map.ceilingKey(2); // 2

map.higherKey(8);  // null
map.ceilingKey(8); // 8

map.higherKey(9);  // null
map.ceilingKey(9); // null

higherKey(K) is more like >, while ceilingKey is more like >=.

Upper Bound:

It is an upper-bound method since we specify an upper-bound value K.

  • lowerKey(K) / lowerEntry(K)
  • floorKey(K) / floorEntry(K)

We use them when we want to find the greatest key less than K (or equal for floor).

1
2
3
4
5
6
7
8
9
10
11
map.lowerKey(9);  // 8
map.floorKey(9);  // 8

map.lowerKey(8);  // 6
map.floorKey(8);  // 8

map.lowerKey(2);  // null
map.floorKey(2);  // 2

map.lowerKey(1);  // null
map.floorKey(1);  // null

lowerKey(K) is more like <, while floorKey is more like <=.

Others:

1
2
3
4
5
TreeMap<Integer, String> map = new TreeMap<>();
map.put(2, "A");
map.put(5, "B");
map.put(6, "C");
map.put(8, "D");

keySet() / descendingKeySet():

1
2
map.keySet();           // [2, 5, 6, 8] (ascending)
map.descendingKeySet(); // [8, 6, 5, 2]

firstKey() (firstEntry()) / lastKey() (lastEntry()):

1
2
map.firstKey(); // 2
map.lastKey();  // 8

pollFirstEntry() / pollLastEntry():

1
2
map.pollFirstEntry(); // <2, "A">
map.pollLastEntry();  // <8, "D">

TreeSet

Its method names are similar to TreeMap‘s.

  • ceiling(K) / higher(K)
  • floor(K) / lower(K)
  • first() / last()
  • pollFirst() / pollLast()
  • headSet(), subSet(), … skip:)

binarySearch()

In Java, Arrays and Collections provide this method for binary search. It is trivial because it is a standard binary search method. It returns a negative number res where -(res + 1) is the position that the element would be inserted at; otherwise, it returns the index where the item is.

1
2
3
4
5
int[] arr = new int[] { 1, 3, 5, 7 }; // cannot specify the size
Arrays.binarySearch(arr, 0); // -1
Arrays.binarySearch(arr, 2); // -2
Arrays.binarySearch(arr, 1); // 0
Arrays.binarySearch(arr, 5); // 2

When there are duplicates, it returns the one it first meets. It is not meant to be leftmost or rightmost.

1
2
3
int[] arr = new int[] { 1, 3, 3, 5, 7, 7, 7 };
Arrays.binarySearch(arr, 3); // 1
Arrays.binarySearch(arr, 7); // 5

Note: If the list is not sorted, the binary search here is not meaningful at all.

At last, Collections.binarySearch(list, K) has the same behavior as Arrays.binarySearch(arr, K) does.