The Scapegoat Tree

A scapegoat tree stores keys in ordinary binary-search-tree order. Search, predecessor, successor, minimum, and maximum use the usual comparisons and do not modify the tree.

The structure differs during updates. It allows local imbalance to accumulate, then rebuilds an entire offending subtree into a nearly complete tree. Search takes O(log n) worst-case time; insertion and deletion take O(log n) amortized time, although one update can take linear time.

An AVL tree stores height or balance information, and a red-black tree stores a color. A scapegoat-tree node needs only its key, value, and child links. No height, subtree size, color, or priority is maintained at every node.

The tree object instead stores two counters: n, the current number of keys, and q, an upper bound on n since the last full rebuild. Implementations may add parent pointers or temporary path storage, but those are navigation choices rather than balance metadata.

A parameter α, with 1/2 < α < 1, controls the permitted imbalance. The tree keeps its height within a constant of log₁/α q. The common choice α = 2/3 therefore gives a bound of about log₃/₂ q.

Because deletion rebuilds when n < αq, the counters otherwise satisfy αq ≤ n ≤ q. The height is therefore O(log n). The tree need not be weight-balanced at every node; the global height bound is the property that guarantees worst-case logarithmic search.

Insert the key as an ordinary binary-search-tree leaf, increment n, and set q = max(q, n). If the new leaf’s depth does not exceed ⌊log₁/α q⌋, the operation stops without restructuring.

A deeper leaf proves that too much imbalance has accumulated somewhere on its root path. The algorithm then walks upward from the inserted node to locate an ancestor whose child on that path contains more than an α fraction of the ancestor’s subtree.

For each ancestor w, compute the size of the child subtree that contains the new leaf. Node w is a scapegoat when size(child) > α · size(w). With α = 2/3, more than two thirds of w’s nodes lie on one side.

The search may use parent pointers, a retained insertion path, or recursion. Subtree sizes do not have to remain stored between updates: they can be computed while examining candidates. A geometric-size argument bounds the total size-computation work by the size of the subtree ultimately rebuilt.

Traverse the scapegoat subtree in order to obtain its nodes in sorted order. Choose the median as the new root, recursively choose medians for the two halves, and reconnect the rebuilt subtree to its former parent.

Rebuilding a subtree of s nodes takes O(s) time. The original nodes can be reused; the algorithm changes links rather than allocating replacement records. A simple implementation uses an O(s) temporary array, while the original paper gives rebuilding methods using logarithmic auxiliary space.

Assume every edge on a root-to-leaf path entered a child containing at most an α fraction of its parent’s nodes. After depth d, that subtree would contain at most αᵈ q nodes.

If d > log₁/α q, then αᵈ q < 1, which is impossible for a subtree containing the inserted leaf. Therefore every insertion that violates the depth bound has at least one weight-unbalanced ancestor available to rebuild.

A rebuild can cost linear time in the selected subtree, so one insertion has an O(n) worst case. The rebuild is delayed until enough updates have created substantial imbalance in that subtree.

A credit or potential argument charges a small amount to each ancestor touched by an update. By the time a subtree of size s becomes a scapegoat, it has accumulated Ω(s) relevant changes, enough to pay for its O(s) rebuild. Across a sequence, insertion costs O(log n) amortized.

Delete a key with the ordinary binary-search-tree splice and decrement n; do not decrement q. Deletion cannot increase the tree’s height, so no local subtree repair is needed.

After enough removals, q becomes too loose an upper bound. Rebuild the whole tree when n < αq, then set q = n. A linear number of deletions separate full rebuilds for fixed α, giving O(log n) amortized deletion with an O(n) worst case for one deletion.

Smaller α permits less imbalance and produces shorter search paths, but insertions trigger rebuilding sooner. Larger α tolerates deeper trees and performs fewer rebuilds.

The parameter therefore trades lookup depth against update work. It does not change the asymptotic guarantees while α remains a fixed constant strictly between 1/2 and 1, but it changes constants and latency distributions.

Scapegoat trees avoid per-node balance fields and never restructure during lookup. Rebuilding also produces a compact local shape and can refresh augmented summaries for a whole subtree in one ordered pass.

The cost is bursty updates: a single insertion or deletion may rebuild many nodes. Computing subtree sizes and retaining an update path add temporary work or storage. Systems that require strict per-update latency usually prefer AVL or red-black trees; splay trees share amortized updates but also mutate on access.

The sources reviewed for this chapter do not identify a prominent production system that documents using a scapegoat tree. Usable library containers exist, but those are implementations rather than evidence of downstream deployment. The structure remains a plausible fit for search-heavy ordered maps when lookup must not mutate the index and bursty update latency is acceptable.

Documented uses are mainly research systems. A hybrid aerial-underwater vehicle path-planning study used a scapegoat tree to find collision-free positions around dynamic obstacles. A cloud-storage integrity design used a scapegoat-based Merkle hash tree, or SGMHT, to support simultaneous authenticated updates to multiple data blocks. Galperin and Rivest also extended partial rebuilding theoretically to k-d trees, orthogonal range-query structures, and quadtrees.

A scapegoat tree is a binary search tree that enforces a global logarithmic height bound without storing balance metadata in each node. A too-deep insertion identifies a weight-unbalanced ancestor and rebuilds that subtree from its sorted nodes.

Search is O(log n) worst-case and does not change the tree. Insertions and deletions are O(log n) amortized, but an individual update can cost O(n). The design exchanges small incremental rotations for occasional linear rebuilds.