netch80 | (no subject)

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?

Flat | Top-Level Comments Only

Можливо це буквальний переклад алгоритму, написаного для зовсім інших машин. Він економить на записі в додаткову змінну bestsofar. При пошуку в великому дереві bestsofar записується в середньому depth/2 раз, а ось в бектрекінгу ми прокручуємо в середньому O(1) циклів (і найгірший випадок може бути взагалі виключений).

Можливо орігінальний алгоритм був рекурсивний, і при розкручуванні і заміні явного стека на бектрекінг отримали ось таке.

А можливо автор просто не додумався, що можна просто запам'ятати місце, коли ми восстаннє звертали наліво.

> а ось в бектрекінгу ми прокручуємо в середньому O(1) циклів (і найгірший випадок може бути взагалі виключений).

Хм. В середньому, мабуть, так. Але це дає значні витрати на підтримку посилань на батьківські вузли. Без бектрекінгу вони не потрібні.

Можливо вони використовуються ще десь. Ось ітерація з ними має бути значно простішою.