Splay Trees

By the end, you can

• Explain what makes a splay tree different from a plain BST.
• Identify which of the three splay cases (zig, zig-zig, zig-zag) applies given the local shape of a node, its parent, and its grandparent.
• Trace the rotation order within a zig-zig step and explain why the grandparent edge rotates first.
• Describe the full sequence of phases in a splay operation from search to root.
• Explain the amortized O(log n) bound and why a single operation can still be Θ(n).
• Define the rank function used in the potential-function analysis and explain how the cost telescopes.
• Explain the locality payoff and the working-set theorem.
• Compare splay trees to AVL and red-black trees on metadata overhead, worst-case guarantees, and suitability for cache-like workloads.
• State what static optimality means and identify the dynamic optimality conjecture as still open.