One Splay Can Hurt

You splay a node in an nn-node splay tree that is currently one long left-leaning path. What does that single operation cost, and what is the tree afterwards?

A

O(log⁡n)O(\log n) rotations. The O(log⁡n)O(\log n) is worst case, no potential is needed to pay for it, and the tree comes out roughly balanced.

B

Θ(n)\Theta(n) rotations. The O(log⁡n)O(\log n) is amortized, the potential stored in the path pays for it, and the tree comes out roughly balanced.

C

Θ(n)\Theta(n) rotations. The O(log⁡n)O(\log n) is amortized, the potential stored in the path pays for it, and the tree comes out still one long path.

D

Θ(n)\Theta(n) rotations. The O(log⁡n)O(\log n) is worst case, no potential is banked along the path, and the tree comes out roughly balanced.