Exercises 11. 3. 2021
Ex. 1: Binary counter
We saw a binary counter that supports increment operation in constant amortized time.
What would go wrong if we also allowed decrement operation? Is it possible to desing a
counter that would support both increment and decrement in constant amortized time?
Ex. 2: BB-\(\alpha\) trees
We saw a binary search trees balanced by local rebuilding. Try to analyze details of
the rebuilding and implement delete oparation on such trees (see exercises in section
1.4 of the lecture notes (last page), 3* is extra hard).
Ex. 3: Successor in BST
In your assignment you were supposed to implement a successor function on a general
unbalanced binary search tree. What is the worst case complexity of such operation?
Show that traversing the tree from min element to max element via repeated calls of
successor takes only \( \mathcal{O}(n) \) time. Can we formulate some sort of
amortization argument?