Design and Analysis of Algorithms

430 Design and Analysis of Algorithms

The following lemma is useful in deriving the amortized time complexity. In the lemma,

r(v) = the rank of a node before rotation

r′(v) = the rank of a node after rotation

Lemma The amortized cost of a single rotation at v is at most 1 + 3r′(v) – 3r(v) and the amortized cost of

a double rotation at v is at most 3r′(v) – 3r(v).

We shall assume this lemma, the details of which can be seen in the original paper by Sleator and Tarjan,

[ST 85].

By adding up all the amortized costs of all the rotations, the amortized cost of splaying is 1 + 3r′(v)

– 3r(v), where r′(v) is the rank after splaying. We get this sum as ...