- Relaxed Balance through Standard Rotations.
- Kim S. Larsen, Eljas Soisalon-Soininen, and Peter Widmayer.
In 5th International Workshop on Algorithms and Data Structures (WADS), volume 1272 of Lecture Notes in Computer Science, pages 450-461. Springer, 1997.
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.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.