AVL trees with relaxed balance
Kim Skak Larsen · 2002
AVL trees with relaxed balance (G.M. Adel'son-Vel'skii et al., 1962) were introduced with the aim of improving runtime performance by allowing a greater degree of concurrency. This is obtained by uncoupling updating from rebalancing. 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 the rebalancing. If N is the maximum size the tree could ever have, we prove that each insertion gives rise to at most /spl lsqb/log/sub /spl phi(N+3/2)+log/sub /spl phi(/spl radic/(5))/spl minus/3/spl rsqb/ rebalancing operations and that each deletion gives rise to at most /spl lsqb/log/sub /spl phi(N+3/2)+log/sub /spl phi(/spl radic/(5))/spl minus/4/spl rsqb/ rebalancing operations, where /spl phi/ is the golden ratio.>