На этом шаге мы приведем задачи для самостоятельного решения.
Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.
1. Красно-чёрные деревья
1. (По [1, с. 256]) Нарисуйте "вручную" полное бинарное дерево поиска высоты 3 с ключами {1, 2, ..., 15}. Добавьте NIL-листья и "раскрасьте" вершины тремя способами так, чтобы получившиеся красно-чёрные деревья имели чёрную высоту 2, 3 и 4. Нарисуйте полученные деревья и найдите их чёрную высоту.
2. Напишите функцию, возвращающую чёрную высоту указанной вершины.
3. Напишите функцию, возвращающую самую короткую ветвь красно-чёрного дерева, ведущую от корня к листьям.
4. Напишите функцию, возвращающую чёрную высоту красно-чёрного дерева.
5. Напишите функцию, возвращающую последовательность чёрных вершин для каждой ветви красно-чёрного дерева.
6. Напишите функцию, возвращающую количество красных и чёрных вершин красно-чёрного дерева (учтите существование NIL-листьев).
7. Напишите функцию, которая среди красных вершин, имеющих заданную чёрную высоту, определяет вершину с наибольшим ключом.
8. Напишите функцию, возвращающую результат объединения двух красно-чёрных деревьев.
2. AA-деревья
1. Напишите функцию для добавления узла в AA-дерево.
2. Напишите функцию для построения AA-дерева.
3. Напишите функцию удаления узлов из AA-дерева.
4. Напишите функцию, возвращающую результат объединения двух AA-деревьев.
(1)Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 1999. - 960 с.
Со следующего шага мы начнем рассматривать реализацию красно-черных деревьев на языках программирования LISP и Haskell.
