Exercises 18. 3. 2021: Splay trees

Ex. 1: Potential

Make sure you understant the potential of a splay tree and the main idea of potential analysis of a splay operation.
  1. How is the potential defined for a splay tree?
  2. What is the amortized cost of a rotation (either single or double)?
  3. What is the amortized cost of the whole splay operation?
  4. What is the real cost of the whole splay operation?

    5. From the lecture we know the potential is between 0 and \( n\log n\).
  5. What is the potential of a perfectly balanced tree? For simplicity assume \(n = 2^k - 1\)
  6. What is the potential of a path?
  7. What is the minimum attainable potential (depending on n)? Try to prove tightest bound as possible.

Ex. 2: Insert and delete

In the lecture we saw implementation of insert and delete based on ordinary BST operations with splaying of the deepest touched node.
  1. Analyze the change of potential in the insert. What happens to the potential when we add new child to a node?
  2. Do the same for delete.

    3. Insert and delete can be also implemented by splaying the node (or its parent) first and then splitting and merging the tree.
  3. Desing and analyze insert and delete operations using the split/join approach.

Ex. 3: Naive splay

Proper splay trees use double rotations if possible. What happens if we implement splay naively, using single rotations?
  1. Look into the analysis of proper splay operation. What is the amortized cost of naive splay, using the same analysis?
  2. Design a sequence of operations that creates a splay tree of linear depth, both for proper splay trees and for naive splay trees. Hint: Inserts are enough. With proper order, you can force even a proper splay tree to perform only single rotations.
  3. Using the tree from previous task, desing sequence of \(k\) operations that has total complexity \( \Omega(kn)\) in naive splay tree. What happens if we run the same operation in a proper splay tree?