Editing Scapegoat tree (section)

====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>