![[topimage]](IMADA_en.png)
Exercises
- For splay trees, compute the potential of a perfectly balanced tree as well as the potential of a tree which has deteriorated to a linked list.
-
For red-black trees, consider the following:
- Consider how to merge two red-black trees in time O(log n), provided that the keys in one tree are all smaller than the keys in the other.
- Given a key k, consider how to split two red-black trees in time O(log n) such that all keys smaller than k go into one tree and the rest go into the other.
- How can one split a red-black tree in two parts or equal size (±1) in time O(log n)? You may add fields.
- In the lecture, we claimed a time complexity of T(n) = 2 T(√n) + 1 was not good enough to get a result better than O(log n). Prove that.
- On the other hand, T(n) = T(√n) + 1 should give us O(log log n). Prove that.