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.