6. Бінарні дерева пошуку

Мета роботи. Ознайомитись з принципами побудування бінарних дерев пошуку і найпростішими методами їх балансування.

Завдання.

1. Створити шаблон класу бінарного дерева пошуку з наступними операціями.

   1. Додавання елемента в дерево.

   2. Видалення елемента з дерева.

   3. Пошук елемента в дереві. Створити два варіанти функції: перша функція повертає значення true, якщо елемент є в дереві, false – якщо його немає; друга функція повертає вказівник на елемент, якщо він є в дереві, і nullptr якщо його там немає.

   4. Пошук мінімального і максимального елементів дерева.

   5. Знаходження кількості елементів в дереві.

   6. Знаходження висоти дерева.

   7. Пошук батька елемента.

   8. Прямий, зворотний, центрований обхід дерева.

   9. Обхід дерева в ширину.

   10. Формування лінійного дужкового запису дерева.

   11. Видалення дерева.

2. На основі класу бінарного дерева реалізовувати клас «множина», аналогічний класу setстандартної бібліотеки шаблонів С++. Операції класу «множина».

   1. Конструктор, що створює пусту множину.

   2. Конструктор, що створює множину з заданим критерієм сортування.

   3. Конструктор копіювання.

   4. Конструктор, що створює множину, ініціалізовану елементами інтервалу [begin,end).

   5. Конструктор, що створює множину, ініціалізовану елементами інтервалу [begin,end)з заданим критерієм сортування.

   6. Знаходження кількості елементів множини.

   7. Перевірка, чи є множина порожньою.

   8. Перевірка, чи входить елемент в множину.

3. На основі класу бінарного дерева реалізувати клас збалансованого дерева. Для балансування використовувати додатковий відсортований масив і бінарний пошук.

4. На основі класу бінарного дерева реалізувати клас збалансованого дерева. Для балансування використовувати алгоритм DSW.

7. Червоно-чорні дерева

Мета роботи. Ознайомитись з властивостями червоно-чорних дерев і методами підтримки балансу в них.

Завдання.

1. Створити шаблон класу червоно-чорного дерева з наступними операціями.

   1. Додавання елемента в дерево.

   2. Видалення елемента з дерева.

   3. Пошук елемента в дереві.

2. Передбачити можливість підрахування кількості наступних операцій.

   1. Повороту дерева при додаванні і видаленні елементів.

   2. Зміни кольору вузлів дерева при додаванні і видаленні елементів.

   3. Переходу між елементами дерева при пошуку.

8. Авл дерева

Мета роботи. Ознайомитись з властивостями АВЛ дерев і методами підтримки балансу в них.

Завдання.

1. Створити шаблон класу АВЛ дерева з наступними операціями.

   1. Додавання елемента в дерево.

   2. Видалення елемента з дерева.

   3. Пошук елемента в дереві.

2. Передбачити можливість підрахування кількості наступних операцій.

   1. Операцій повороту дерева при додаванні і видаленні елементів.

   2. Операцій переходу між елементами дерева при пошуку.

9. Порівняння методів балансування бінарних дерев

Мета роботи. Порівняти ефективність червоно-чорних, АВЛ і splay дерев і алгоритму балансування DSW.

Завдання.

1. Створити шаблон класу splay дерева з наступними операціями.

   1. Додавання елемента в дерево.

   2. Видалення елемента з дерева.

   3. Пошук елемента в дереві.

2. Для splay дерева передбачити можливість підрахування кількості наступних операцій.

   1. Операцій повороту дерева при додаванні і видаленні елементів.

   2. Операцій переходу між елементами дерева при пошуку.

3. Порівняти кількість операцій з підтримки балансу (поворотів для АВЛ дерева, поворотів й зміни кольору вузлів для Червоно-Чорних дерев) і операцій переходу між елементами дерева для наступних випадків.

   1. Послідовність додавання, видалення і звертання до елементів дерева випадкова, але кількість операцій додавання і видалення значно менша кількості операцій пошуку елементів дерева.

   2. Послідовність додавання, видалення і звертання до елементів дерева випадкова, але кількість операцій додавання і видалення значно більша кількості операцій пошуку елементів дерева.