Search trees with relaxed balance and near-optimal height

We introduce the relaxed k-tree, a search tree with relaxed balance and a height bound, when in balance, of (1 + epsilon)log(2) 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(2) n for a fixed constant c. In all previous proposals, the constant is at least 1/ log(2) 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.