- 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)
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.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
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 by the author.