Бінарне дерево, його структура, типи та принципи роботи

Бінарне дерево – це структура даних, де кожен вузол може мати до двох нащадків: лівого і правого. Воно забезпечує ефективне зберігання та організацію даних, а також спрощує реалізацію алгоритмів і операцій. Історично, бінарні дерева були розроблені для ефективного пошуку та організації інформації, починаючи зі створення бінарного пошукового дерева в 1950-х роках. З плином часу вони стали широко застосовуватися в базах даних, компіляторах, алгоритмах сортування і пошуку, комп’ютерній графіці та інших галузях інформатики (дана тема вивчається на практиці на курсі Алгоритми і структури даних від компанії FoxmindED).

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

Структура

Бінарне дерево складається з вузлів, кожен з яких містить деякі дані та посилання на його нащадків:

Вузли:

комірки пам’яті, що зберігають дані (числа, рядки, об’єкти);
можуть мати посилання на інші вузли.

Корінь:

верхній вузол дерева, який не має “батька”;
від нього починається обхід дерева.

Нащадки:

“діти” вузла, на які він посилається;
лівий нащадок завжди менший або дорівнює своєму “батькові”;
правий нащадок завжди більший або дорівнює своєму “батькові”.

Для наочності представимо просте бінарне дерево:

/ \

3 10

/ \ \

1 6 14

/ \ /

4 7 13

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

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

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

Бінарні дерева застосовуються в різних галузях програмування та інформатики. Це і бази даних, і алгоритми сортування та пошуку, і структури даних.

Наш курс Алгоритми та структури даних дає змогу познайомитися з основними та найбільш використовуваними структурами даних.
Курс складається із серії відеолекцій і практичних завдань для закріплення матеріалу.

Деталі курсу

Типи

Існує кілька типів двійкових дерев:

Бінарні дерева пошуку (BST): дані впорядковано так, що елементи в лівому піддереві менші за значення вузла, а в правому – більші. Часто використовуються для швидкого пошуку елементів у базах даних.
АВЛ-дерева: це спеціальний тип BST, де висота піддерев кожного вузла відрізняється не більше ніж на одиницю. Запобігають деградації продуктивності при великих обсягах даних.
Червоно-чорні дерева: ще один тип самобалансуючих BST. Вузли додатково позначені червоним або чорним кольором. Широко використовуються в реалізації множин і словників.
Є й інші типи, як-от B-дерева, B+ дерева, Splay-дерева тощо, кожен зі своїми характеристиками та застосуванням в інформатиці.

Наведемо приклади створення бінарних дерев на Python, Java і C++:

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

int main() {

    TreeNode* root = new TreeNode(1);

    root->left = new TreeNode(2);

    root->right = new TreeNode(3);

    root->left->left = new TreeNode(4);

    root->left->right = new TreeNode(5);

    return 0;

}

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

public class Main {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(5);

    }

}

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

root = TreeNode(1)

root.left = TreeNode(2)

root.right = TreeNode(3)

root.left.left = TreeNode(4)

root.left.right = TreeNode(5)

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

Бінарні дерева знаходять широке застосування в реальних проєктах і завданнях;

Бази даних: використовуються для організації індексів і швидкого пошуку даних. Наприклад, B-дерева для реляційних баз даних і B+ дерева для кластерних індексів.

Алгоритми пошуку та сортування: застосовуються в алгоритмах бінарного пошуку та сортування, таких як сортування злиттям;

Реальні проєкти: використовуються в СУБД (MySQL, PostgreSQL), пошукових системах, файлових системах (NTFS), компіляторах та інтерпретаторах для аналізу та зберігання програмного коду.

Бінарні дерева забезпечують ефективну організацію та обробку даних, що робить їх важливим інструментом у різних галузях інформатики та програмування.

Алгоритми

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

Розглянемо порядок:

Пошук вузла: порівнюємо ключі та спускаємося деревом: ліворуч, якщо ключ менший за поточний вузол, праворуч, якщо більший. Процес повторюється до знаходження вузла або досягнення кінця дерева.
Вставка вузла: порівнюємо ключі та вставляємо вузол у дерево, враховуючи правила порядку.
Видалення вузла: складний процес, що включає різні випадки залежно від наявності нащадків у вузла, що видаляється.
Обхід бінарного дерева: дає змогу відвідати кожен вузол у визначеному порядку: прямий, pre-order traversal (відвідування кореня, потім піддерев), зворотний, post-order traversal (відвідування піддерев, потім кореня), симетричний, in-order traversal (відвідування лівого піддерева, потім кореня, потім правого піддерева). Використовується для виведення відсортованих даних або виконання операцій над деревом.

Балансування

Балансування двійкових дерев – це процес підтримки рівноваги в структурі дерева шляхом перерозподілу вузлів. Воно запобігає деградації продуктивності та збільшенню часу виконання операцій під час послідовних вставлянь і видалень вузлів.

Навіщо вона потрібна? Без неї дерева можуть стати незбалансованими, що призводить до погіршення продуктивності операцій через збільшення висоти дерева і лінійної залежності часу виконання від кількості вузлів.

Алгоритми балансування:

АВЛ-дерева: гарантують баланс, підтримуючи різницю висот піддерев кожного вузла не більше ніж на одиницю. Використовують повороти і перебалансування піддерев під час вставки і видалення.
Червоно-чорні дерева: дерева, що самобалансуються, де кожен вузол позначений червоним або чорним кольором. Гарантують рівну кількість чорних вузлів на шляху від кореня до листів.
Splay-дерева: переміщують часто використовувані вузли ближче до кореня, що забезпечує хорошу продуктивність у середньому випадку.

Наведемо приклади алгоритмів балансування бінарних дерев:

Балансування АВЛ

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

Балансування червоно-чорного дерева

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

FoxmindEd – це навчальний центр, що має велику різноманітність напрямків курсів для новачків та програмістів з досвідом!

Тільки починаєте свій шлях в ІТ? Спробуйте курси Start

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

Хочете поглибити свої знання в ІТ? Ми маємо курси Middle/Senior

Балансування 2-3 дерева

Засноване на злитті та поділі вузлів для підтримки оптимальної структури.
За необхідності вузли об’єднуються або розділяються для збереження балансу.

Складність операцій

Проведемо аналіз часової та просторової складності операцій у бінарних деревах:

Пошук вузла: у збалансованих деревах, таких як АВЛ-дерева або червоно-чорні дерева, час пошуку становить O(log n), де n – кількість вузлів у дереві. У незбалансованих деревах, таких як дерева пошуку в найгіршому випадку, час пошуку може становити O(n).
Вставка вузла: у збалансованих деревах час вставки становить O(log n), тоді як у незбалансованих – O(n).
Видалення вузла: у збалансованих – час становить O(log n), тоді як у незбалансованих – O(n).
Просторова складність: зазвичай становить O(n), де n – кількість вузлів у дереві, через необхідність зберігання даних і покажчиків на нащадків для кожного вузла.

Порівняємо ефективність різних типів бінарних дерев:

АВЛ-дерева: гарантують логарифмічний час виконання операцій вставки, пошуку і видалення, але вимагають більше операцій для балансування.
Червоно-чорні дерева: вимагають менше операцій для балансування і можуть бути ефективнішими в деяких сценаріях.
Splay-дерева: забезпечують хорошу продуктивність у середньому випадку, але можуть мати неоптимальний час виконання в гіршому випадку для деяких операцій.

Практичні приклади та завдання

Пропонуємо короткий розбір практичного завдання:

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

Визначте клас Node, що представляє вузол бінарного дерева. У вузла повинні бути поля для зберігання значення, покажчиків на лівого і правого нащадка.

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

Метод вставки вузла

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

Метод пошуку вузла

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

Тестування

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

Підпишіться на наш Ютуб-канал! Корисні відео для програмістів чекають на вас! YouTube

Оберіть свій курс програмування! Шлях до кар’єри програміста починається тут! Подивитись

Оптимізація (за бажанням)

Реалізуйте методи видалення вузла, обходу дерева та інші додаткові функції залежно від вимог завдання.

Щоб потренувати навички роботи з бінарними деревами, радимо звернути увагу на такі ресурси: онлайн-курси та освітні платформи (Coursera, edX, Udacity, Codecademy, LeetCode, HackerRank), підручники та книжки (“Introduction to Algorithms”, Кормен, Лейзерсон, Рівест, Штайн, “Algorithms”, Седжвік, Вейн), онлайн-ресурси та платформи (GitHub, Stack Overflow), інтерактивні пісочниці й середовища розробки (Jupyter Notebook, Google Colab, Visual Studio Code, PyCharm).

А почати можна з онлайн-курсів Java Start, C# Start, Python Start, C++ Start на платформі FoxmindED. Консультант допоможе вам обрати оптимальний курс, виходячи з ваших прагнень у цій галузі.

Висновок

Бінарні дерева в програмуванні відіграють важливу роль. Їхня важливість – в ефективній організації та зберіганні даних, а також у широкому спектрі застосування в різних галузях. Вивчення цієї теми відкриває перед розробниками виняткові перспективи для створення ефективних програмних рішень та алгоритмів.

У чому важливість бінарного дерева в програмуванні