Page 171 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Simple Rotation

The only two nodes that change rank are x and y. So the cost is 1 + r’(x) − r(x) + r’(y) − r(y). Since
y decreases in rank, this is at most 1 + r’(x) − r(x). Since x increases in rank, r’(x) − r(x) is positive
and this is bounded by 1 + 3(r’(x) − r(x)).

Zig-Zig Rotation

Only the nodes x, y, and z change in rank. Since this is a double rotation, we assume it has actual
cost 2 and the amortized time is
2 + r’(x) − r(x) + r’(y) − r(y) + r’(z) − r(z)
Since the new rank of x is the same as the old rank of z, this is equal to
2 − r(x) + r’(y) − r(y) + r’(z)

The new rank of x is greater than the new rank of y, and the old rank of x is less than the old rank
y, so this is at most
2 − r(x) + r’(x) − r(x) + r’(z) = 2 + r’(x) − 2r(x) + r’(z)

Now, let s(x) be the old size of x and let s’(x) be the new size of x. Consider the term 2r’(x) − r(x) −
r’(z). This must be at least 2 because it is equal to lg(s’(x)/s(x)) + lg(s’(x)/s’(z)). Notice that this is
the sum of two ratios where s’(x) is on top. Now, because s’(x) ≥ s(x) + s’(z), the way to make the
sum of the two logarithms as small as possible is to choose s(x) = s(z) = s’(x)/2. But in this case the
sum of the logs is 1 + 1 = 2. Therefore the term 2r’(x) − r(x) − r’(z) must be at least 2. Substituting
it for the red 2 above, we see that the amortized time is at most
(2r’(x) − r(x) − r’(z)) + r’(x) − 2r(x) + r’(z) = 3(r’(x) − r(x)) as required.

Zig-Zag Rotation

Again, the amortized time is
2 + r’(x) − r(x) + r’(y) − r(y) + r’(z) − r(z)

Because the new rank of x is the same as the old rank of z, and the old rank of x is less than the
old rank of y, this is
2 − r(x) + r’(y) − r(y) + r’(z)

≤ 2 − 2 r(x) + r’(y) + r’(z)
Now consider the term 2r’(x) − r’(y) − r’(z). By the same argument as before, this must be at least
2, so we can replace the constant 2 above while maintaining a bound on amortized time:
≤ (2r’(x) − r’(y) − r’(z)) − 2 r(x) + r’(y) + r’(z) = 2(r’(x) − r(x))

Therefore amortized run time in this case too is bounded by 3(r’(x) − r(x)), and this completes the
proof of the amortized complexity of splay tree operations.

7.6 Summary

Splay trees are self-adjusting binary search trees in which every access for insertion or
retrieval of a node, lifts that node all the way up to become the root, pushing the other
nodes out of the way to make room for this new root of the modified tree. Hence, the

frequently accessed nodes will frequently be lifted up and remain around the root position;
while the most infrequently accessed nodes would move farther and farther away from the
root.

166 LOVELY PROFESSIONAL UNIVERSITY