6

While reading about splay trees I found some expression about the rank of the splay node 'X' and the amortized cost in wikipedia. It is given as, { We can bound the amortized cost of any zig-zig or zig-zag operation by:

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

where x is the node being moved towards the root, and the subscripts "f" and "i" indicate after and before the operation, respectively. When summed over the entire splay operation, this telescopes to 3(rank(root)) which is O(log n). Since there's at most one zig operation, this only adds a constant.}

I am not able to interpret this. Can some one explain the above in-detail please. If possible with some examples.

Please provide some links for the explanations on others theorems of splay trees

Thanks

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
poddroid
  • 845
  • 1
  • 14
  • 26

1 Answers1

1

You want to carry out a simple amortized analysis of static splay trees. If you take one basic zig zag like the example on wikipedia. it's the worst case senario. And you have :

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

Proof: with the notation used on wikipedia,since x is at the root of the tree at after the transformation, 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 reasonning with x before the transformation you get :

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

you can generalise that to the whole operation to calculate the amortized cost.

I guess it proove your result, but I am not sure it's what you were looking for .

Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63