Шаг 154.
Основы языка Haskell.
Рекурсивные типы данных. BST-деревья. Задачи для самостоятельного решения

    На этом шаге мы приведем задачи для самостоятельного решения.


   Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.

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-деревья.




Предыдущий шаг Содержание Следующий шаг