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?