AVL Trees with Relaxed Balance.

Kim S. Larsen.
In 8th International Parallel Processing Symposium (IPPS), pages 888-893. IEEE Computer Society Press, 1994.

AVL trees with relaxed balance were introduced with the aim of improving runtime performance by allowing a greater degree of concurrency. This is obtained by uncoupling updating from rebalancing. An additional benefit is that rebalancing can be controlled separately. In particular, it can be postponed completely or partially until after peak working hours.

We define a new collection of rebalancing operations which allows for a significantly greater degree of concurrency than the original proposal. Additionally, in contrast to the original proposal, we prove the complexity of our algorithm. If N is the maximum size the tree could ever have, we prove that each insertion gives rise to at most floor(log_phi(N + 3/2) + log_phi(sqrt(5)) - 3) rebalancing operations and that each deletion gives rise to at most floor(log_phi(N + 3/2) + log_phi(sqrt(5)) - 4) rebalancing operations, where phi is the golden ratio.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): none.

full version

Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.

other publications

Other publications by the author.