 Search Trees with Relaxed Balance and NearOptimal 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 414425. Springer, 2001.
We introduce a relaxed
ktree, 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 (nonrelaxed)
ktree 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.