Editing Scapegoat tree (section)

==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 [[Binary tree#Types of binary trees|almost complete binary trees]].

A binary search tree that is α-weight-balanced must also be '''α-height-balanced''', that is 
 height(tree) ≤ floor(log<sub>1/α</sub>(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(log<sub>1/α</sub>(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 tree]]s 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 tree]]s, in that the actual rotations depend on 'balances' of nodes, but the means of determining the balance differs greatly. Since AVL trees check the balance value on every insertion/deletion, it is typically stored in each node; scapegoat trees are able to calculate it only as needed, which is only when a scapegoat needs to be found.

Unlike most other self-balancing search trees, scapegoat trees are entirely flexible as to their balancing. They support any α such that 0.5 < α < 1. A high α value results in fewer balances, making insertion quicker but lookups and deletions slower, and vice versa for a low α. Therefore in practical applications, an α can be chosen depending on how frequently these actions should be performed.