Editing Splay tree (section)

== Analysis ==
A simple [[amortized analysis]] of static splay trees can be carried out using the [[potential method]]. Define:
* size(''r'') = the number of nodes in the sub-tree rooted at node ''r'' (including ''r'').
* rank(''r'') = log<sub>2</sub>(size(''r'')).
* Φ = the sum of the ranks of all the nodes in the tree.

Φ will tend to be high for poorly balanced trees and low for well-balanced trees.

To apply the [[potential method]], we first calculate ΔΦ: the change in the potential caused by a splay operation. We check each case separately. Denote by rank' the rank function after the operation. x, p and g are the nodes affected by the rotation operation (see figures above).

===Zig step===
:{|
|-
| ΔΦ || = rank'(''p'') − rank(''p'') + rank'(''x'') − rank(''x'')&nbsp;&nbsp;
| [since only p and x change ranks]
|-
|    || = rank'(''p'') − rank(''x'')
| [since rank'(''x'')=rank(''p'')]
|-
|    || ≤ rank'(''x'') − rank(''x'')
| [since rank'(''p'')<rank'(''x'')]
|}

===Zig-zig step===
:{|
| ΔΦ ||colspan=2| = rank'(''g'') − rank(''g'') + rank'(''p'') − rank(''p'') + rank'(''x'') − rank(''x'')
|-
|    || =  rank'(''g'') + rank'(''p'') − rank(''p'') − rank(''x'')&nbsp;&nbsp;
| [since rank'(x)=rank(g)]
|-
|    || ≤  rank'(''g'') + rank'(''x'') − 2 rank(''x'')
| [since rank(''x'')<rank(''p'') and rank'(''x'')>rank'(''p'')]
|-
|    || ≤  3(rank'(''x'')−rank(''x'')) − 2
| [due to the concavity of the log function]
|}

===Zig-zag step===
:{|
| ΔΦ ||colspan=2| = rank'(''g'') − rank(''g'') + rank'(''p'') − rank(''p'') + rank'(''x'') − rank(''x'')
|-
|    || ≤ rank'(''g'') + rank'(''p'') − 2 rank(''x'')&nbsp;&nbsp;
| [since rank'(''x'')=rank(''g'') and rank(''x'')<rank(''p'')]
|-
|    || ≤ 3(rank'(''x'')−rank(''x'')) − 2
| [due to the concavity of the log function]
|}
The amortized cost of any operation is ΔΦ plus the actual cost. The actual cost of any zig-zig or zig-zag operation is 2 since there are two rotations to make. Hence:

:{|
| amortized-cost || = cost + ΔΦ
|-
|                || ≤ 3(rank'(''x'')−rank(''x''))
|}

When summed over the entire splay operation, this [[telescoping series|telescopes]] to 1 + 3(rank(root)−rank(''x'')) which is O(log ''n''), since we use The Zig operation at most once and the amortized cost of zig is at most 1+3(rank'(''x'')−rank(''x'')).

So now we know that the total ''amortized'' time for a sequence of ''m'' operations is:
:<math>T_\mathrm{amortized}(m) = O(m \log n)</math>

To go from the amortized time to the actual time, we must add the decrease in potential from the initial state before any operation is done (Φ<sub>''i''</sub>) to the final state after all operations are completed (Φ<sub>''f''</sub>).

:<math>\Phi_i - \Phi_f = \sum_x{\mathrm{rank}_i(x) - \mathrm{rank}_f(x)} = O(n \log n)</math>

where the [[big O notation]] can be justified by the fact that for every node ''x'', the minimum rank is 0 and the maximum rank is log(''n'').

Now we can finally bound the actual time:

:<math>T_\mathrm{actual}(m) = O(m \log n + n \log n)</math>

=== Weighted analysis ===
The above analysis can be generalized in the following way.
* Assign to each node ''r'' a weight ''w''(''r'').
* Define size(''r'') = the sum of weights of nodes in the sub-tree rooted at node ''r'' (including ''r'').
* Define rank(''r'') and Φ exactly as above.

The same analysis applies and the amortized cost of a splaying operation is again:
:<math>1 + 3(\mathrm{rank}(root)-\mathrm{rank}(x))</math>
where ''W'' is the sum of all weights.

The decrease from the initial to the final potential is bounded by:
:<math>\Phi_i - \Phi_f \leq \sum_{x\in tree}{\log{\frac{W}{w(x)}}}</math>
since the maximum size of any single node is ''W'' and the minimum is ''w(x)''.

Hence the actual time is bounded by:
:<math>O\left(\sum_{x \in sequence}{\left(1 + 3\log{\frac{W}{w(x)}}\right)} + \sum_{x \in tree}{\log{\frac{W}{w(x)}}}\right) = O\left(m + \sum_{x \in sequence}{\log{\frac{W}{w(x)}}} + \sum_{x \in tree}{\log{\frac{W}{w(x)}}}\right)</math>