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

3.1 Визначення бінарного дерева пошуку (BST)

Бінарне дерево пошуку (BST) — це бінарне дерево, що має наступні властивості:

• Для будь-якого вузла його ліве піддерево містить тільки вузли з ключами меншими, ніж ключ даного вузла.
• Для будь-якого вузла його праве піддерево містить тільки вузли з ключами більшими, ніж ключ даного вузла.
• Обидва піддерева кожного вузла також є бінарними деревами пошуку.

Приклад BST:

BST – це скорочення від Binary Search Tree – буквально «Бінарне дерево пошуку». Фактично це організація даних у вигляді «дерева», по якому можна дуже швидко шукати. Структура дерева – це фактично приховане/хитре сортування елементів.

Обхід центрований (in-order traversal)

Завдання обходу — визначеним чином сформувати список вузлів (або даних з вузлів, питання термінології і має значення на практиці). Центрований (симетричний) обхід — обхід, при якому корінь дерева займає місце між результатами відповідних обходів лівого і правого піддерев.

Разом зі властивістю бінарного дерева пошуку (яка про нерівності, див. теорію) це говорить про те, що центрований обхід бінарного дерева пошуку сформує нам відсортований список вузлів — круто! Ось як буде виглядати обхід визначеного раніше дерева:

3.2 Принципи роботи і властивості BST

Принципи роботи:

• Організація даних: BST організовує дані так, щоб забезпечувати ефективний пошук, вставку і видалення елементів.
• Рекурсивна структура: Кожен вузол у BST підпорядковується тим самим правилам, що і корінь дерева, що робить структуру рекурсивною.
• Балансованість: Для забезпечення оптимальної продуктивності BST має бути збалансованим, тобто висота лівого і правого піддерев має бути приблизно однаковою.

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

• Впорядкованість: В будь-який момент можна обійти дерево в порядку "in-order" (ліве піддерево → поточний вузол → праве піддерево), щоб отримати всі елементи в відсортованому порядку.
• Час операцій:
  • В середньому час виконання операцій пошуку, вставки і видалення становить O(log n), де n — кількість вузлів.
  • В гіршому випадку (якщо дерево не збалансоване) час виконання операцій може досягати O(n).
• Унікальні ключі: Всі ключі в BST мають бути унікальними, щоб зберегти впорядкованість.

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

1. Вставка (Insertion):

Принцип роботи:

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

Алгоритм:

1. Якщо дерево порожнє, новий вузол стає кореневим вузлом.
2. Інакше рекурсивно знаходимо правильне місце і додаємо новий вузол.

2. Видалення (Deletion):

Принцип роботи:

• Знайти вузол для видалення.
• Розглянути три випадки:
• Вузол є листом (не має дітей): просто видаляємо вузол.
• Вузол має одного нащадка: замінюємо вузол його нащадком.
• Вузол має двох нащадків: знаходимо найменший вузол у правому піддереві (або найбільший у лівому), копіюємо його значення у вузол, що видаляється, і рекурсивно видаляємо найменший вузол у правому піддереві.

Алгоритм:

1. Знайти вузол із заданим ключем.
2. Залежно від випадку виконати відповідне видалення і перерозподіл вузлів.

3. Пошук (Search):

Принцип роботи:

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

Алгоритм:

1. Якщо дерево порожнє або ключ вузла співпадає з шуканим, повертаємо вузол.
2. Якщо ключ шуканого вузла менший, рекурсивно шукаємо в лівому піддереві.
3. Якщо ключ шуканого вузла більший, рекурсивно шукаємо в правому піддереві.

3.4 Приклади задач, які розв'язуються за допомогою BST

1. Пошук елемента в динамічному множині

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

Розв'язання з використанням BST:

• Вставка нових елементів у дерево.
• Видалення існуючих елементів.
• Пошук елементів у дереві.

Приклад використання:

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

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

Необхідно швидко знаходити мінімальне та максимальне значення у наборі даних.

Розв'язання з використанням BST:

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

Приклад використання:

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

3. Перевірка балансу виразу

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

Розв'язання з використанням BST:

Використовуємо BST для зберігання проміжних станів перевірки балансу дужок.

Приклад використання:

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

4. Побудова словника

Необхідно створити структуру даних для зберігання словника, в якому слова можуть бути додані, видалені і швидко знайдені.

Розв'язання з використанням BST:

• Слова додаються в дерево в алфавітному порядку.
• Пошук слів здійснюється за ключами.

Приклад використання:

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