by realising that we already know two of the three sizes, leaving only the third to be calculated. Consider the following example to demonstrate this. Assuming that we're climbing back up to the root: size(parent) = size(node) + size(sibling) + 1 But as: size(inserted node) = 1. The case is trivialized down to: size[x+1] = size[x] + size(sibling) + 1 Where x = this node, x + 1 = parent and size(sibling) is the only function call actually required. Once the scapegoat is found, the subtree rooted at the scapegoat is completely rebuilt to be perfectly balanced. This can be done in time by traversing the nodes of the subtree to find their values in sorted order and recursively choosing the median as the root of the subtree. As rebalance operations take time (dependent on the number of nodes of the subtree), insertion has a worst-case performance of time. However, because these worst-case scenarios are spread out, insertion takes amortized time. Sketch of proof for cost of insertion Define the Imbalance of a node v to be the absolute value of the difference in size between its left node and right node minus 1, or 0, whichever is greater. In other words: Immediately after rebuilding a subtree rooted at v, I(v) = 0. Lemma: Immediately before rebuilding the subtree rooted at v, ( is Big Omega notation.) Proof of lemma: Let be the root of a subtree immediately after rebuilding. . If there are degenerate insertions (that is, where each inserted node increases the height by 1), then , and . Since before rebuilding, there were insertions into the subtree rooted at that did not result in rebuilding. Each of these insertions can be performed in time. The final insertion that causes rebuilding costs . Using aggregate analysis it becomes clear that the amortized cost of an insertion is : Deletion Scapegoat trees are unusual in that deletion is easier than insertion. To enable deletion, scapegoat trees need to store an additional value with the tree data structure. This property, which we will call MaxNodeCount simply represents the highest achieved NodeCount. It is set to NodeCount whenever the entire tree is rebalanced, and after insertion is set to max(MaxNodeCount, NodeCount). To perform a deletion, we simply remove the node as you would in a simple binary search tree, but if NodeCount ≤ α*MaxNodeCount then we rebalance the entire tree about