Amortized cost of splay tree: cost + P (tf) - P (ti) ≤ 3 (rankf (x) - ranki (x)) explanation

Question

While reading about splay trees, I found some expression about the splay node 'X' rank and amortized cost on wikipedia. It is given as, {We can relate the amortized cost of any zigzag or zigzag operation:

amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)), 

where x is the node moved to the root, and the indices "f" and "i" indicate after and before the operation, respectively. When summing over the entire splay operation, this telescope is 3 (rank (root)), which is O (log n). Since there is no more than one operation with zig, this adds a constant.}

I can not interpret it. Can someone explain the above in detail in detail. If possible, with some examples.

Please provide some links for explanations in other pause tree theorems.

thanks

Answer 1

You want a simple depreciation analysis of static trees. If you take one basic zigzag, as an example on Wikipedia. this is the worst case of senario. And you have:

P (tf) - P (ti) ≤ 3 (rankf (x) - ranki (x))

Proof: with the notation used in wikipedia, since x is in the root of the tree after the conversion, you easily get:

rankf (x)> = rankf (g) and rankf (x)> = rankf (f)

Thus,

Ptf = rankf (x) + rankf (g) + rankf (p) <= 3 * rankf (x)

With the opposite consideration with x before conversion you get:

Pti = ranki (x) + ranki (g) + ranki (p)> = 3 * ranki (x)

You can generalize this to the entire transaction to calculate the amortized cost.

I assume this is the result of your result, but I'm not sure what you were looking for.