На этом шаге мы приведем задачи для самостоятельного решения.
Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.
1. Операция "ротация"
1*. Напишите функцию, реализующую операцию "ротация вправо" в бинарном дереве поиска.
2*. Напишите функцию, реализующую операцию "ротация влево" в бинарном дереве поиска.
3. Покажите, что выполнение (n-1)-ой операции "ротация вправо" достаточно для преобразования любого бинарного дерева поиска, содержащего n вершин, в линейный список.
2. Операция "поворот"
1. Напишите функцию, реализующую операцию "спаренный двусторонний поворот вправо" (LR-поворот) в бинарном дереве поиска.
2. Напишите функцию, реализующую операцию "спаренный двусторонний поворот влево" (RL-поворот) в бинарном дереве поиска.
3. Напишите функцию, реализующую операцию "спаренный односторонний поворот вправо" (RR-поворот) в бинарном дереве поиска.
4. Напишите функцию, реализующую операцию "спаренный односторонний поворот влево" (LL-поворот) в бинарном дереве поиска.
5*. Напишите функцию, реализующую тройной RRR-поворот в бинарном дереве поиска.
6*. Напишите функцию, реализующую тройной LRR-поворот в бинарном дереве поиска.
3. Перемещение элемента в корень бинарного дерева поиска
1*. Напишите функцию, которая преобразует бинарное дерево поиска, перемещая заданный элемент в корень дерева.
2. Напишите функцию, которая преобразует бинарное дерево поиска, перемещая k-й (по номеру) наименьший элемент в корень дерева.
3. Напишите функцию для сравнения работы операций "ротация" и "спаренный поворот" по быстродействию при перемещении указанной вершины A дерева Tree в его корень.
4*. Напишите функцию для реализации операции "объединение двух бинарных деревьев поиска", все ключи второго из которых заведомо больше ключей первого.
Указание. Ко второму дереву примените операцию перемещения в корень наименьшего элемента в этом дереве; решение задачи завершается установкой связи с первым деревом.
4. Скошенные деревья
1. Напишите функцию, реализующую операцию "удаление элемента из скошенного дерева" посредством операции спаренного поворота (и, возможно, операции ротации).
Со следующего шага мы начнем рассматривать красно-чёрные деревья, AA-деревья.
