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 -