Problem: Ordered Queries on the TreeMap

The Map contract answers one kind of question about a key: is it here, and what value is stored under it? A TreeMap keeps its keys in order, and it can use that order to answer more questions. Even when a key is not stored, the tree can tell you the nearest stored keys on each side of it. And it can list every key that falls in a range.

The three queries are collected in an interface that extends Map:

public interface OrderedMap<K extends Comparable<K>, V> extends Map<K, V> {
  K floorKey(K key);                // largest key <= key, or null if there is none
  K ceilingKey(K key);              // smallest key >= key, or null if there is none
  List<K> keysBetween(K lo, K hi);  // keys from lo to hi, both included, ascending
}

Start from a copy of TreeMap, renamed, and add the three methods:

public class OrderedTreeMap<K extends Comparable<K>, V> implements OrderedMap<K, V> {
  // ... everything from TreeMap ...

  @Override
  public K floorKey(K key) { }

  @Override
  public K ceilingKey(K key) { }

  @Override
  public List<K> keysBetween(K lo, K hi) { }
}

All three throw IllegalArgumentException for a null key, and keysBetween also throws when lo is greater than hi.

Take this tree. The pictures show only the keys:

             ╭────╮
             │ 50 │
             ╰──┬─╯
       ┌────────┴────────┐
    ╭──┴─╮            ╭──┴─╮
    │ 30 │            │ 70 │
    ╰──┬─╯            ╰──┬─╯
   ┌───┴───┐       ┌─────┴─────┐
╭──┴─╮  ╭──┴─╮  ╭──┴─╮      ╭──┴─╮
│ 20 │  │ 40 │  │ 60 │      │ 80 │
╰────╯  ╰────╯  ╰────╯      ╰──┬─╯
                           ┌───┴───┐
                        ╭──┴─╮  ╭──┴─╮
                        │ 75 │  │ 90 │
                        ╰────╯  ╰────╯

For the key 55, the floor is 50 and the ceiling is 60. 55 is not stored, but those are the nearest keys on each side. For a key that is stored, say 40, the floor and the ceiling are both 40. For 10, the floor is null, because no stored key is that small. For 95, the ceiling is null, because no stored key is that large. And keysBetween(55, 78) returns [60, 70, 75], the only three of the nine keys in that range.

The obvious approach uses the map’s own iterator, which visits the keys in ascending order. For floorKey, iterate over the keys and keep the last one that is not above the key. For keysBetween, iterate over the keys and keep the ones in range. Both are correct, and both read all $n$ keys. Your versions should do better: floorKey and ceilingKey should run in $O (lo g n)$ , and keysBetween in $O (lo g n + k)$ , where $k$ is the number of keys it returns.

Try it before reading the solution.