Exercises 25. 3. 2021: (a,b)-trees and bit of splay trees

Ex. 1: Insert and delete


Perform following operations on the (2,3)-tree from the picture (perform each operation separately):
  1. Insert 7
  2. Insert 48
  3. Delete 44
  4. Delete 40
  5. Delete 32
  6. Delete 30
  7. Delete 16
You can check you solution in a visualisation, tree from the picture can be created by inserting following keys (in that order):
(the original sequence was wrong, this one should be correct)
28, 24, 26, 18, 0, 36, 16, 34, 22, 10, 2, 30, 4, 6, 20, 12, 32, 38, 14, 8, 40, 42, 44, 46
Note that visualisation only allows \((\lceil b/2 \rceil,b)\)-trees.

Ex. 2: Height of (a,b)-tree

Prove the bounds on the height of a (a,b)-tree from the lecture. That is, prove that (a,b)-tree with \(n\) keys has height between \(\log_b (n+1)\) and \(1+\log_a ((n+1)/2)\). Note that height is measured in the number of edges, that is, a tree with only a root and external nodes has height 1. Hint: Go the other way around and calculate what is the maximum and minimum number of keys a tree of height \( h\) can contain. This should give you the desired bounds on height.

Ex. 3: Naive splay (from previous practicals)

Proper splay trees use double rotations if possible. What happens if we implement splay naively, using single rotations?
  1. 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.
  2. 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?