Editing Scapegoat tree (section)

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

<math>I(v) = \operatorname{max}(|\operatorname{left}(v) - \operatorname{right}(v)| - 1, 0) </math>

Immediately after rebuilding a subtree rooted at ''v'', I(''v'') = 0.

'''Lemma:''' Immediately before rebuilding the subtree rooted at ''v'', <br />
<math>I(v) \in \Omega (|v|) </math><br />
(<math>\Omega </math> is [[Big Omega notation]].)

Proof of lemma:

Let <math>v_0</math> be the root of a subtree immediately after rebuilding.  <math>h(v_0) = \log(|v_0| + 1) </math>.  If there are <math>\Omega (|v_0|)</math> degenerate insertions (that is, where each inserted node increases the height by 1), then <br />
<math>I(v) \in  \Omega (|v_0|) </math>,<br />
<math>h(v) = h(v_0) + \Omega (|v_0|) </math> and<br />
<math>\log(|v|) \le \log(|v_0| + 1) + 1 </math>.

Since <math>I(v) \in \Omega (|v|)</math> before rebuilding, there were <math>\Omega (|v|)</math> insertions into the subtree rooted at <math>v</math> that did not result in rebuilding.  Each of these insertions can be performed in <math>O(\log n)</math> time.  The final insertion that causes rebuilding costs <math>O(|v|)</math>.  Using [[aggregate analysis]] it becomes clear that the amortized cost of an insertion is <math>O(\log n)</math>:

<math>{\Omega (|v|) O(\log n) + O(|v|) \over \Omega (|v|)} = O(\log n) </math>