TY - GEN

T1 - Search Trees with Relaxed Balance and Near-Optimal Height

AU - Fagerberg, Rolf

AU - Jensen, Rune E.

AU - Larsen, Kim Skak

PY - 2001

Y1 - 2001

N2 - We introduce the relaxed k-tree, a search tree with relaxed balance and a height bound, when in balance, of (1 + ε)log2n + 1, for any g > 0. The rebalancing work is amortized O(1/ε) per update. This is the first binary search tree with relaxed balance having a height bound better than c · log2 n for a fixed constant c. In all previous proposals, the constant is at least 1/log2 φ τ; 1.44, where φ is the golden ratio.
As a consequence, we can also define a standard (non-relaxed) k-tree with amortized constant rebalancing per update, which is an improvement over the original definition.
Search engines based on main-memory databases with strongly fluctuating workloads are possible applications for this line of work.

AB - We introduce the relaxed k-tree, a search tree with relaxed balance and a height bound, when in balance, of (1 + ε)log2n + 1, for any g > 0. The rebalancing work is amortized O(1/ε) per update. This is the first binary search tree with relaxed balance having a height bound better than c · log2 n for a fixed constant c. In all previous proposals, the constant is at least 1/log2 φ τ; 1.44, where φ is the golden ratio.
As a consequence, we can also define a standard (non-relaxed) k-tree with amortized constant rebalancing per update, which is an improvement over the original definition.
Search engines based on main-memory databases with strongly fluctuating workloads are possible applications for this line of work.

U2 - 10.1007/3-540-44634-6_38

DO - 10.1007/3-540-44634-6_38

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 414

EP - 425

BT - Algorithms and Data Structures, 7th International Workshop, WADS 2001

T2 - Seventh International Workshop on Algorithms and Data Structures

Y2 - 8 August 2001 through 10 August 2001

ER -