Relaxed Balance using Standard Rotations

Kim Skak Larsen, Eljas Soisalon-Soininen, Peter Widmayer

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review


In search trees with relaxed balance, rebalancing transformations need not be connected with updates, but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing operations are uncoupled from updates, their total number is bounded by O(M log (M+N)) , where M is the number of updates to an AVL tree of initial size N . Hence, relaxed balancing of AVL trees comes at no extra cost asymptotically. Furthermore, our scheme differs from most other relaxed balancing schemes in an important aspect: No rebalancing transformation can be done in the wrong direction, i.e., no performed rotation can make the tree less balanced. Moreover, each performed rotation indeed corresponds to a real imbalance situation in the tree. Finally, and perhaps most importantly, our structure is capable of forgetting registered imbalance if later updates happen to improve the situation. Our results are of theoretical interest and have possible sequential and parallel applications.
Udgave nummer4
Sider (fra-til)501-512
Antal sider12
StatusUdgivet - 2001


Dyk ned i forskningsemnerne om 'Relaxed Balance using Standard Rotations'. Sammen danner de et unikt fingeraftryk.