Створення бінарного дерева пошуку

Мета роботи

Навчитися працювати з розгалуженими динамічними структурами, реалізовувати за допомогою мови програмування високого рівня бінарне дерево пошуку.

Обладнання

Персональний комп’ютер, IDE Microsoft Visual Studio або інша середа розробки для мови C++

Теоретичні відомості

Бінарне дерево

Бінарне дерево — це ієрархічна динамічна структура даних, у якій кожен вузол має не більше двох нащадків (лівий і правий). Кожен вузол містить дані та два покажчики на дочірні вузли.

Основні поняття:

Корінь дерева — перший (верхній) вузол дерева.
Лист — вузол, який не має нащадків.
Висота дерева — максимальна кількість вузлів на шляху від кореня до листа.
Піддерево — будь-яке дерево, що є частиною більшого дерева.

Властивості:

Кількість вузлів на рівні k не перевищує 2^k.
Максимальна кількість вузлів у дереві висоти h — 2^(h+1) - 1.

Представлення вузла бінарного дерева на C++:

struct Node {
    int data;
    Node* left;
    Node* right;
};

Бінарне дерево пошуку (БДП, BST)

Бінарне дерево пошуку — це бінарне дерево, яке задовольняє додаткову умову:

Для кожного вузла всі елементи в лівому піддереві менші за значення вузла, а всі елементи в правому піддереві — більші або рівні.

Основні операції:

Додавання (insert): вставка нового елемента з дотриманням властивості БДП.
Пошук (search): знаходження елемента за значенням.
Видалення (remove): видалення вузла з перебудовою дерева.
Обхід дерева: прямий (preorder), симетричний (inorder), зворотний (postorder).

Приклад вставки у БДП:

void Add(int value, Node*& root) {
    if (!root) {
        root = new Node{value, nullptr, nullptr};
        return;
    }
    if (value < root->data)
        Add(value, root->left);
    else
        Add(value, root->right);
}

Переваги:

Швидкий пошук, вставка та видалення (O(log n) у збалансованому дереві).
Динамічна структура, не потребує попереднього визначення розміру.

Недоліки:

При невдалому порядку вставки дерево може виродитися у список (O(n) операції).
Потрібно слідкувати за балансуванням (AVL, Red-Black Tree тощо).

Застосування:

Реалізація асоціативних масивів, множин, словників.
Організація швидкого пошуку та сортування.

Візуалізація:

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13

Хід роботи

Завантажити Visual Studio. Знайдіть на робочому столі ярлик з Visual Studio або Пуск → Всі програми→ Microsoft → Microsoft Visual Studio.
Створити новий проект «Visual C++ (консольное приложение Win32)». Файл → Cтворити → Проект, тип проекту «Консольное приложение Win32».
Перевірити роботу програми та намалювати блок-схему алгоритму

#include <iostream>
using namespace std;

// Структура ветки
struct Branch {
    int Data; // Поле даних
    Branch* LeftBranch; // Вказівники на ліву та праву гілку
    Branch* RightBranch;
};

// Функція внесення даних
void Add(char aData, Branch*& aBranch) {
    if (!aBranch) { // Якщо гілки не існує, створюємо її та додаємо дані
        aBranch = new Branch;
        aBranch->Data = aData;
        aBranch->LeftBranch = nullptr;
        aBranch->RightBranch = nullptr;
        return;
    } else { // В іншому випадку порівнюємо дані
        if (aData < aBranch->Data) {
            Add(aData, aBranch->LeftBranch);
        } else {
            Add(aData, aBranch->RightBranch);
        }
    }
}

// Функція виведення дерева
void Print(Branch* aBranch, int level = 0) {
    if (!aBranch) return; // Якщо гілки не існує, виходимо
    Print(aBranch->RightBranch, level + 1); // Виводимо праву гілку
    for (int i = 0; i < level; i++) cout << "  "; // Відступи для красивого відображення
    cout << aBranch->Data << endl; // Виводимо дані
    Print(aBranch->LeftBranch, level + 1); // Виводимо ліву гілку
}

// Функція для звільнення пам'яті, включаючи всі гілки
void FreeTree(Branch* aBranch) {
    if (!aBranch) return;
    FreeTree(aBranch->LeftBranch);
    FreeTree(aBranch->RightBranch);
    delete aBranch;
}

int main() {
    Branch* Root = nullptr;
    int s[] = {10, 6, 8, 14, 5, 2, 11, 13, 7, 15, 4, 3, 0, 16, 1, 17, 18, 12, 19};

    for (int i = 0; i < 20; i++) {
        Add(s[i], Root);
    }

    Print(Root);
    FreeTree(Root);

    cin.get();
    return 0;
}

Перевірте роботу прикладів за посиланнями нижче.
Виконайте самостійні завдання:
1. Переосмисліть дану програму згідно із загальними правилами ООП
2. Додайте до програми класс TreeNode який буде містити дані про вузли дерева
3. Реалізуйте через методи класу функції додавання, видалення, пошуку
4. Модифікуйте функцію пошуку так, щоб вона надавала інформацію про кількість переходів під час пошуку
5. Додайте в програму можливість заповнення випадковими числами.
6. Відповідно свого варіанту оберіть діапазон випадкових чисел: (номер_варіанта)*100 - (номер_варіанта)*100 + 200
Використовуючи попередні лабораторні роботи, створіть програму, яка буде додавати випадкові числа одночасно у зв’язниц список та бінарне дерево пошуку.
1. Згенеруйте та додайте 1000, 10000, 100000 випадкових чисел одночасно в дерево та список
2. Використовуючи функції пошуку для списку та дерева оцініть середню кількість переходів по дереву та по списку.
3. Пошук для різних чисел повторіть 10 разів
4. Подайте результати пошуку у звіті в табличному вигляді. Зробіть висновок
Для кожного етапу роботи зробити знімки екрану та додати їх у звіт з описом кожного скіншота
Додати програмний код завдання для самомтійного виконання
Дати відповіді на контрольні запитання
Зберегти звіт у форматі PDF

Контрольні запитання

Що таке бінарне дерево? Які його основні властивості?
Що таке бінарне дерево пошуку? Яка його головна відмінність від звичайного бінарного дерева?
Як реалізується вузол бінарного дерева у C++?
Які основні операції підтримує бінарне дерево пошуку? Опишіть їх коротко.
Як відбувається пошук елемента у бінарному дереві пошуку?
Які види обходу бінарного дерева існують? Для чого вони використовуються?
Які переваги та недоліки бінарних дерев порівняно з масивами та списками?
Що таке балансування бінарного дерева? Навіщо воно потрібне?
Як звільнити пам’ять, зайняту бінарним деревом?
Наведіть приклади застосування бінарних дерев у програмуванні.

350 Алгоритми та структури даних