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
- How is the potential defined for a splay tree?
- What is the amortized cost of a rotation (either single or double)?
- What is the amortized cost of the whole splay operation?
- What is the real cost of the whole splay operation?
From the lecture we know the potential is between 0 and \( n\log n\).
- What is the potential of a perfectly balanced tree? For simplicity assume \(n =
2^k - 1\)
- What is the potential of a path?
- 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.
- Analyze the change of potential in the insert. What happens to the potential when
we add new child to a node?
- Do the same for delete.
Insert and delete can be also implemented by splaying the node (or its parent)
first and then splitting and merging the tree.
- 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?
- Look into the analysis of proper splay operation. What is the amortized cost of
naive splay, using the same analysis?
- 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
- 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?