Editing Scapegoat tree (section)

===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 the root, remembering to set MaxNodeCount to NodeCount.

This gives deletion a worst-case performance of <math>O(n)</math> time, whereas the amortized time is <math>O(\log n)</math>.

====Sketch of proof for cost of deletion====
Suppose the scapegoat tree has <math>n</math> elements and has just been rebuilt (in other words, it is a complete binary tree).  At most <math>n/2 - 1</math> deletions can be performed before the tree must be rebuilt.  Each of these deletions take <math>O(\log n)</math> time (the amount of time to search for the element and flag it as deleted).  The <math>n/2</math> deletion causes the tree to be rebuilt and takes <math>O(\log n) + O(n)</math> (or just <math>O(n)</math>) time.  Using aggregate analysis it becomes clear that the amortized cost of a deletion is <math>O(\log n)</math>:

<math>
{\sum_{1}^{n/2} O(\log n) + O(n) \over n/2} = 
{{n \over 2}O(\log n) + O(n) \over n/2} = 
O(\log n) \ 
</math>