In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson in 1989 and again by Igal Galperin and Ronald L. Rivest in 1993. It provides worst-case lookup time (with as the number of entries) and amortized insertion and deletion time. Unlike most other self-balancing binary search trees which also provide worst case lookup time, scapegoat trees have no additional per-node memory overhead compared to a regular binary search tree: besides key and value, a node stores only two pointers to the child nodes. This makes scapegoat trees easier to implement and, due to data structure alignment, 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 rebuild the subtree rooted at the scapegoat into a complete binary tree. Thus, scapegoat trees have worst-case update performance. Theory A binary search tree is said to be weight-balanced if half the nodes are on the left of the root, and half on the right. An α-weight-balanced node is defined as meeting a relaxed weight balance criterion: size(left) ≤ α*size(node) size(right) ≤ α*size(node) Where size can be defined recursively as: function size(node) is if node = nil then return 0 else return size(node->left) + size(node->right) + 1 end if end function Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-balanced must also be α-height-balanced, that is height(tree) ≤ floor(log1/α(size(tree))) By contraposition, a tree that is not α-height-balanced is not α-weight-balanced. Scapegoat trees are not guaranteed to keep α-weight-balance at all times, but are always loosely α-height-balanced in that height(scapegoat tree) ≤ floor(log1/α(size(tree))) + 1. Violations of this height balance condition can be detected at insertion time, and imply that a violation of the weight balance condition must exist. This makes scapegoat trees similar to red–black trees in that they both have restrictions on their height. They differ greatly though in their implementations of determining where the rotations (or in the case of scapegoat trees, rebalances) take place. Whereas red–black trees store additional 'color' information in each node to determine the location, scapegoat trees find a scapegoat which isn't α-weight-balanced to perform the rebalance operation on. This is loosely similar to AVL trees, in that the actual rotations depend