# 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]