Scapegoat tree

Invented by Andersson (GB-trees, 1989), Galperin, Rivest (1993) 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 relatively easy implementation (no rotations) parameter $\alpha$ enables a trade-off between time spent for rebuilding and maximum height guarantees the $O(\log n)$ time for insert and delete is only amortized, individual operations may take $\Omega(n)$ time sg_set, sg_multiset, and sgtree classes in Boost.Intrusive library