Consider a binary search tree (AVL, red-black, whatever). The goal "find the least key strictly greater than the specified one" ("upper_bound" in C++ STL, higherEntry//higherKey in Java, etc.) can be implemented in manner (Java-like pseudocode):
current = root;
bestsofar = null;
while (current != null) {
if (example_key < current.key) {
bestsofar = current;
current = current.left;
} else {
current = current.right;
}
}
// return for KV extracting
return bestsofar;
This can be improved with optimizations (e.g.
C5 adds special processing case without comparings if found exact match), but the main principle remains that we use single pass from the root to a leaf.
But Java TreeMap implementation uses strange variant (the same at least in versions 8...13):
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
so, in some cases it backtracks using "parent" link to find the place it started passing only left-side links before final right-side dead end. (Really, all 4 key-based inexact searches utilizes this way, with minor differences and mirrored conditions.)
What case is being optimized with this approach?
This entry was originally posted at https://netch80.dreamwidth.org/49623.html. Please comment there using OpenID.
netch по тематике IT. Все вопросы - к оригиналу.
amused