| 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\) trades time spent on rebuilding for a stronger guarantee on the height
- the technique of keeping a tree balanced by rebuilding subtrees can be used in other data structures, such as the k-d tree or the range tree, where nodes cannot be rotated efficiently
|
| 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 |