AVL Trees With Relaxed Balance
DOI:
https://doi.org/10.7146/dpb.v21i428.6742Abstract
AVL trees with relaxed balance were introduced with the aim of improving runtime per formance 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 of the tree, we prove that each insertion gives rise to at most I_ log_Phi(N + 3/2) + log_Phi(squareroot{5}) - 3 _I rebalancing operations and that each deletion gives rise to at most I_ log_Phi(N + 3/2) + log_Phi(squareroot{5}) - 4 _I rebalancing operations, where Phi is the golden ratio.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.