Scapegoat tree

Invented by Andersson (GB-trees, 1989), Galperin, Rivest (1993)
Idea:
  • lazy insert: let the tree grow and from time to time, when a subtree gets too imbalanced, rebuild the whole subtree from scratch into a perfectly balanced tree
  • lazy delete: just mark the node for deletion; when \(n/2\) nodes are marked, rebuild the whole tree and throw away all deleted nodes
Advantages:
  • relatively easy implementation (no rotations)
  • parameter \(\alpha\) enables a trade-off between time spent for rebuilding and maximum height guarantees
Disadvantages:
  • the \(O(\log n)\) time for insert and delete is only amortized, individual operations may take \(\Omega(n)\) time
Implementation: sg_set, sg_multiset, and sgtree classes in Boost.Intrusive library
[You can download the application for offline viewing.]

References

  • A. Andersson. General balanced trees. Journal of Algorithms, 30(1):1-18, 1999. [bib] [pdf]
  • A. Andersson. Implementing general balanced trees. [bib] [pdf]
  • I. Galperin and R.L. Rivest. Scapegoat trees. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 165-174. Society for Industrial and Applied Mathematics, 1993. [bib] [pdf]