Relaxed Balance Using Standard Rotations

Relaxed Balance Using Standard Rotations

0.00 Avg rating0 Votes
Article ID: iaor20121075
Volume: 31
Issue: 4
Start Page Number: 501
End Page Number: 512
Publication Date: Dec 2001
Journal: Algorithmica
Authors: , ,
Keywords: graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.