- Relaxed Balance using Standard Rotations.
- Kim S. Larsen, Eljas Soisalon-Soininen, and Peter Widmayer.
Algorithmica, 31(4): 501-512, 2001.
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))
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.
open access (151 KB)
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
Other publications by the author.