Solution: Descending Toward the Key
The iterator version reads all keys to answer a question about one path. The ordering property lets us follow just that one path. We go down from the root, and at each node one comparison tells us which way to go and whether the node is worth remembering.
floorKey
The floor is the largest stored key that is not above the given key. As we go down, we keep the best candidate we have seen so far in best:
@Override
public K floorKey(K key) {
if (key == null) {
throw new IllegalArgumentException();
}
Node<K, V> node = root;
K best = null;
while (node != null) {
int cmp = key.compareTo(node.key);
if (cmp == 0) {
return node.key;
} else if (cmp < 0) {
node = node.left;
} else {
best = node.key; // at or below key, so a candidate
node = node.right;
}
}
return best;
}
When the node’s key equals the given key, that key is its own floor, and we are done. When the node’s key is larger, the node and its right subtree are too big, so we step left and remember nothing. When the node’s key is smaller, it is a candidate, so we record it. Then we step right, because a larger key that is still not above the given key would be a better floor, and any such key is in the right subtree. When we fall off the tree, best holds the largest candidate we passed, or null if we never passed one.
The loop works like a search. It only goes down, so it does not need recursion.
ceilingKey
The ceiling is the smallest stored key that is not below the given key. The code is the same loop with every comparison going the other way:
@Override
public K ceilingKey(K key) {
if (key == null) {
throw new IllegalArgumentException();
}
Node<K, V> node = root;
K best = null;
while (node != null) {
int cmp = key.compareTo(node.key);
if (cmp == 0) {
return node.key;
} else if (cmp > 0) {
node = node.right;
} else {
best = node.key; // at or above key, so a candidate
node = node.left;
}
}
return best;
}
Tracing both on the key 55
Run floorKey(55). At the root 50: since , it is a candidate, so best = 50, and we step right to 70. The left subtree of 50 holds only smaller keys, so it can never hold a better floor:
╭────╮
best │█50█│
╰──┬─╯
┌──────────────┴──────────────┐
╭──┴─╮ ╭──┴─╮
│░30░│ │ 70 │
╰──┬─╯ ╰──┬─╯
┌──────┴──────┐ ┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│░20░│ │░40░│ │ 60 │ │ 80 │
╰────╯ ╰────╯ ╰────╯ ╰──┬─╯
┌──────┴──────┐
╭──┴─╮ ╭──┴─╮
│ 75 │ │ 90 │
╰────╯ ╰────╯
At 70: since , it is too big, so we step left to 60 and remember nothing:
╭────╮
best │ 50 │
╰──┬─╯
┌──────────────┴──────────────┐
╭──┴─╮ ╭──┴─╮
│░30░│ │█70█│
╰──┬─╯ ╰──┬─╯
┌──────┴──────┐ ┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│░20░│ │░40░│ │ 60 │ │░80░│
╰────╯ ╰────╯ ╰────╯ ╰──┬─╯
┌──────┴──────┐
╭──┴─╮ ╭──┴─╮
│░75░│ │░90░│
╰────╯ ╰────╯
At 60: since , too big again, so we step left and fall off the tree:
╭────╮
best │ 50 │
╰──┬─╯
┌──────────────┴──────────────┐
╭──┴─╮ ╭──┴─╮
│░30░│ │ 70 │
╰──┬─╯ ╰──┬─╯
┌──────┴──────┐ ┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│░20░│ │░40░│ │█60█│ │░80░│
╰────╯ ╰────╯ ╰────╯ ╰──┬─╯
┌──────┴──────┐
╭──┴─╮ ╭──┴─╮
│░75░│ │░90░│
╰────╯ ╰────╯
The loop ends and we return best, which is 50.
Now ceilingKey(55). At the root 50: since , it is too small for a ceiling, so we step right to 70:
╭────╮
│█50█│
╰──┬─╯
┌──────────────┴──────────────┐
╭──┴─╮ ╭──┴─╮
│░30░│ │ 70 │
╰──┬─╯ ╰──┬─╯
┌──────┴──────┐ ┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│░20░│ │░40░│ │ 60 │ │ 80 │
╰────╯ ╰────╯ ╰────╯ ╰──┬─╯
┌──────┴──────┐
╭──┴─╮ ╭──┴─╮
│ 75 │ │ 90 │
╰────╯ ╰────╯
At 70: since , it is a candidate, so best = 70, and we step left to 60:
╭────╮
│ 50 │
╰──┬─╯
┌──────────────┴──────────────┐
╭──┴─╮ ╭──┴─╮
│░30░│ best │█70█│
╰──┬─╯ ╰──┬─╯
┌──────┴──────┐ ┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│░20░│ │░40░│ │ 60 │ │░80░│
╰────╯ ╰────╯ ╰────╯ ╰──┬─╯
┌──────┴──────┐
╭──┴─╮ ╭──┴─╮
│░75░│ │░90░│
╰────╯ ╰────╯
At 60: since , a better candidate, so best = 60, and we step left and fall off the tree:
╭────╮
│ 50 │
╰──┬─╯
┌──────────────┴──────────────┐
╭──┴─╮ ╭──┴─╮
│░30░│ │ 70 │
╰──┬─╯ ╰──┬─╯
┌──────┴──────┐ ┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│░20░│ │░40░│ best │█60█│ │░80░│
╰────╯ ╰────╯ ╰────╯ ╰──┬─╯
┌──────┴──────┐
╭──┴─╮ ╭──┴─╮
│░75░│ │░90░│
╰────╯ ╰────╯
The loop ends and we return 60. Each query visited three of the nine nodes.
Cost
Each query follows one path from the root toward a leaf, one step per level, with no backtracking. That is , and on an AVL tree . The iterator version was .
A map that does not keep its keys in order can say whether 55 is stored, but it cannot find 50 and 60 as its nearest neighbors without looking at every key.