Search Trees with Relaxed Balance and Near-Optimal Height.

Rolf Fagerberg, Rune E. Jensen, and Kim S. Larsen.
In 7th International Workshop on Algorithms and Data Structures (WADS), volume 2125 of Lecture Notes in Computer Science, pages 414-425. Springer, 2001.

We introduce a 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 number of nodes involved in rebalancing is O(1/epsilon) per update in the amortized sense, and O(log n/epsilon) in the worst case sense. 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, which is an improvement over the current definition.

World Wide Web search engines are possible applications for this line of work.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): The final publication is available at link.springer.com.

open access (146 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.