Методические указания для выполнения лабораторных работ по дисциплине "Структуры и алгоритмы обработки данных"

1. Дополнительная операция - определение критерия сбалансированности для узлов дерева (нерекурсивная форма).
2. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - определение К –го по порядку значения ключа в дереве (рекурсивная форма).
3. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - вставка элемента в корень дерева.
4. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - объединение двух поддеревьев (рекурсивная форма).
5. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - горизонтальное инвертирование дерева (нерекурсивная форма).
6. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - вывод данных всех узлов, расположенных на заданном уровне дерева (рекурсивная форма).
7. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «снизу - вверх.» (нерекурсивная форма).
8. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «снизу - вверх.» (рекурсивная форма).
9. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «сверху - вниз.» (нерекурсивная форма).
10. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «сверху - вниз.» (рекурсивная форма).
    Лабораторная работа № 4.

"Нелинейные коллекции данных - сбалансированные деревья поиска".

Задание: На базе двоичного дерева поиска спроектировать,  реализовать и провести тестовые испытания АТД для нелинейной коллекции - "Сбалансированное дерево поиска".

Операции АТД "Сбалансированное дерево поиска":

·  опрос количества узлов в дереве Size,

·  проверка пустого дерева Еmpty,

·  поиск элемента в дереве Find,

·  опрос высоты дерева,

·  очистка дерева Clear

·  включение нового элемента по ключу в дерево Insert,

·  удаление элемента по ключу из дерева Delete,

Методические указания к лабораторной работе:

1. Рандомизированное дерево, АВЛ - дерево и Красно - Черное дерево (RB - дерево) реализовать как модификацию АТД "Дерево двоичного поиска" с помощью технологии наследования классов.
2. АТД "2-3 дерево" реализовать, как самостоятельный класс.
3. Получить оценки эффективности операций Find, Insert, Delete относительно количества узлов в дереве, выраженные в средней на операцию глубине пути в дереве.

4. Трудоемкость операций измеряется в средней на операцию длине пути в дереве.
5. При тестировании рассмотреть варианты худшего и среднего случаев работы операций.

Варианты заданий:

1.  АТД "АВЛ - дерево" - модификация АТД "Рекурсивное дерево двоичного поиска.

2.  АТД "АВЛ - дерево" - модификация АТД "Нерекурсивное дерево двоичного поиска.

3.  , АТД " RB - дерево" - модификация АТД "Рекурсивное дерево двоичного поиска.

4.  , АТД " RB - дерево" - модификация АТД "Нерекурсивное дерево двоичного поиска.

5.  АТД "Рекурсивное 2-3 дерево".

6.  АТД "Нерекурсивное 2-3 дерево".

7.  АТД " Рандомизированное дерево" - модификация АТД "Рекурсивное дерево двоичного поиска.

8.  АТД "Рандомизированное дерево" - модификация АТД "Нерекурсивное