Семинар 3. Дерево поиска

Разбор прошлого домашнего задания

Задача 1. Эмиль Рахимов

Задача 2. Денис Рахманкин

Задача 3. Роман Чулков

Задача 4. Денис Рахманкин

Задача 5. Алексей Бабушкин

Задача 6. Валерий Миронов

Задачи с практики

1. Покажите, как добавить в дерево поиска по неявному ключу операцию reverse(), которая меняет порядок элементов на обратный.

   Бонус: как сделать операцию reverse(n), которая \(n\) раз меняет порядок элементов на обратный? \(0 \leqslant n \leqslant 10^{18}\).

2. а) Напомним инвариант АВЛ-дерева: у любой вершины высота двух поддеревьев её детей отличается не более чем на единицу. Докажите, что высота АВЛ-дерева из \(n\) вершин не превосходит \(\mathcal O(\log n)\).

   б) Верно ли то же самое, если в дереве у любой вершины высота поддеревьев её детей отличается не более чем на пять?