Editing Splay tree (section)

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