Scapegoat tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a scapegoat tree is a <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing binary search tree</a>, invented by Arne Andersson in 1989 and again by Igal Galperin and <a href="/facts/Ronald_L._Rivest/nQsIcAKa">Ronald L. Rivest</a> in 1993. It provides worst-case <a href="/facts/Big_O_notation/weFFjSWg">
 
 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 
 
 {\displaystyle {\color {Blue}O(\log n)}}
 
</a> lookup time (with 
 
 
 
 n
 
 
 {\displaystyle n}
 
 as the number of entries) and 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
 <a href="/facts/Amortized_analysis/9fFYenJz">amortized</a> insertion and deletion time.
Unlike most other self-balancing binary search trees which also provide worst case 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
 lookup time, scapegoat trees have no additional per-node memory overhead compared to a regular <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a>: besides key and value, a node stores only two pointers to the child nodes. This makes scapegoat trees easier to implement and, due to <a href="/facts/Data_structure_alignment/Bqk6zMNS">data structure alignment</a>, can reduce node overhead by up to one-third.
Instead of the small incremental rebalancing operations used by most balanced tree algorithms, scapegoat trees rarely but expensively choose a "scapegoat" and completely rebuilds the subtree rooted at the scapegoat into a complete binary tree. Thus, scapegoat trees have 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 worst-case update performance.

Scapegoat tree open-in-new

Scapegoat tree