AVL trees with relaxed balance

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 [log_φ(N+3/2)+log_φ(√(5))-3] rebalancing operations and that each deletion gives rise to at most [log _φ(N+3/2)+log_φ(√(5))-4] rebalancing operations, where φ is the golden ratio