ALCOMFT-TR-01-128

Rolf Fagerberg, Rune E. Jensen and Kim S. Larsen
Search Trees with Relaxed Balance and Near-Optimal Height
Århus. Work package 4. May 2001.

Abstract: We introduce the relaxed k-tree, a search tree with relaxed balance and a height bound, when in balance, of (1+epsilon)log₂ n + 1, for any epsilon > 0. The rebalancing work is amortized O(1/epsilon) per update. This is the first binary search tree with relaxed balance having a height bound better than c · log₂ n for a fixed constant c. In all previous proposals, the constant is at least 1/log₂\phi>1.44, where \phi 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.

Postscript file: ALCOMFT-TR-01-128.ps.gz (84 kb).