Зелений = знайдено / Жовтий = шлях пошуку / Червоний = не знайдено
Двійкове дерево пошуку (ДДП) — фундаментальна структура даних у комп'ютерних науках, де кожен вузол зберігає значення та має щонайбільше двох дітей: усі значення лівого піддерева менші за вузол, усі значення правого — більші. Ця властивість упорядкованості означає, що пошук, вставка та видалення елементів займають O(log n) часу в середньому — та сама асимптотична ефективність, що й бінарний пошук у відсортованому масиві, але з гнучкістю динамічної структури. ДДП лежить в основі індексів баз даних, таблиць символів у компіляторах та контейнера std::map у C++.
Симулятор дозволяє вставляти, шукати та видаляти значення, переглядати обходи дерева (в порядку, прямий, зворотний) з покроковою анімацією та застосовувати AVL-балансування для перетворення виродженого (у вигляді списку) дерева на збалансоване. Панель статистики показує кількість вузлів, висоту дерева та чи задовольняє воно критерій AVL (|h_L − h_R| ≤ 1 у кожному вузлі).
Яка часова складність пошуку в ДДП?
У збалансованому ДДП пошук займає O(log n) часу, бо кожне порівняння вдвічі зменшує кількість кандидатів. У найгіршому випадку — коли елементи вставлено у відсортованому порядку, утворюючи лінійний ланцюжок — дерево виродиться і пошук стає O(n). Саме тому були винайдені самобалансувальні варіанти: AVL-дерева та червоно-чорні дерева.
Що таке AVL-дерево і як відбувається балансування?
AVL-дерево (названо на честь Адельсона-Вельського та Ландіса, 1962) — це самобалансувальне ДДП, яке підтримує інваріант: різниця висот лівого та правого піддерев (коефіцієнт балансу) у кожному вузлі не перевищує 1. Коли вставка або видалення порушує цю умову, виконується ротація — проста (ліво або право) чи подвійна (ліво-право або право-ліво) — що відновлює баланс за O(log n) без зміни властивості ДДП.
Що дає обхід дерева в порядку (inorder)?
Обхід у порядку (ліво → корінь → право) відвідує кожен вузол у зростаючому порядку значень. Це одна з найкорисніших властивостей ДДП: один O(n)-прохід дає відсортований список. Прямий обхід (корінь → ліво → право) зручний для серіалізації дерева, а зворотний (ліво → право → корінь) — коли треба обробити дітей до батьків, наприклад при видаленні цілого дерева.
Коефіцієнт балансу (bf) вузла — це висота лівого піддерева мінус висота правого. В AVL-дереві bf має бути −1, 0 або +1 для кожного вузла. Симулятор відображає «bf:x» під кожним вузлом. Вузол із bf = +2 має лівий надлишок і потребує правої ротації (або лівоправої подвійної ротації, якщо дочірній вузол правоважкий).
Якщо елементи вставляти у строго зростаючому або спадному порядку — наприклад, 1, 2, 3, 4, 5 — ДДП перетворюється на правий (або лівий) ланцюжок висотою n−1, ідентичний за структурою зв'язному списку. Кожен пошук тоді вимагає перегляду всіх n вузлів, що дає O(n). Спробуйте вставити відсортовані значення в цей симулятор і порівняйте висоту з випадковим порядком вставки тих самих значень.
Видалення вузла в ДДП має три випадки: (1) вузол є листом — просто видаляємо; (2) вузол має одного нащадка — замінюємо вузол нащадком; (3) вузол має двох нащадків — замінюємо значення вузла найменшим значенням правого піддерева (наступником в порядку обходу), потім видаляємо цей вузол-наступник, який гарантовано потрапляє у випадок 1 або 2.
Системи управління базами даних використовують B-дерева (узагальнення ДДП з кількома ключами у вузлі) для дискових індексів, забезпечуючи O(log n) пошук серед мільйонів записів. Ядро Linux використовує червоно-чорні дерева для планування задач та управління областями віртуальної пам'яті. Контейнери std::map і std::set у C++ зазвичай реалізовані через червоно-чорні дерева, гарантуючи O(log n) у найгіршому випадку.
Обидві структури деревоподібні, але мають різні властивості впорядкування. ДДП забезпечує ліво-менший-за-батька порядок по всьому дереву, що робить пошук ефективним. Купа підтримує лише відношення між батьком та його безпосередніми нащадками (max-heap: батько ≥ нащадки), що дає O(1) для знаходження максимуму, але O(n) для довільного пошуку. Купи оптимальні для черг пріоритетів; ДДП — для впорядкованих словників.
Стандартне визначення ДДП виключає дублікати, але реальні реалізації обробляють їх одним з трьох способів: (1) ігнорувати (як у цьому симуляторі); (2) дозволяти дублікати у правому піддереві; (3) зберігати лічильник поряд зі значенням. Вибір впливає на логіку видалення та семантику обходу і зазвичай фіксується на етапі проектування.
Ця симуляція будує двійкове дерево пошуку прямо у вашому браузері, дозволяючи вставляти, шукати та видаляти цілі значення, спостерігаючи за кожним порівнянням крок за кроком. Звичайне ДДП набуває форми виключно від порядку вставки, тому може вироджуватися у повільний ланцюжок; кнопка AVL Баланс перебудовує ті самі значення у збалансоване за висотою дерево за допомогою поворотів, щоб можна було порівняти пошук до і після. Три кнопки обходу показують класичні порядки відвідування — симетричний, прямий і зворотний, а панель статистики повідомляє кількість вузлів, висоту дерева та чи виконується умова AVL-балансу.
Кожне вставлене значення стає вузлом, розміщеним ліворуч або праворуч від батька за правилом ДДП: менші значення — ліворуч, більші — праворуч. Пошук підсвічує шлях порівнянь жовтим, стаючи зеленим, якщо значення знайдено, або червоним, якщо його немає, тож видно, скільки порівнянь насправді потрібно — O(log n) у середньому для збалансованого дерева, але O(n) для сильно перекошеного.
Введіть значення і натисніть «Вставити», «Пошук» чи «Видалити»; скористайтеся «Випадк. 10», щоб швидко заповнити дерево, або «Очистити», щоб почати заново. Натисніть «AVL Баланс», щоб перебудувати поточні значення у збалансоване дерево через повороти, і порівняйте висоту до і після. Кнопки «Симетр.», «Прямий» і «Зворотн.» анімують кожен порядок обходу в полі результату, а панель статистики відстежує кількість вузлів, висоту, статус балансу та останню операцію.
Симетричний (inorder) обхід будь-якого двійкового дерева пошуку завжди відвідує значення у строго зростаючому порядку — саме ця властивість робить ДДП зручним для зберігання відсортованих даних, які можна ефективно шукати, вставляти й видаляти без окремого сортування. Практичні нащадки змодельованого тут AVL-дерева, як-от червоно-чорні дерева, лежать в основі std::map у C++ та TreeMap у Java.
Симулятор порівнює нове значення з коренем: менше йде ліворуч, більше — праворуч, і так рекурсивно, доки не знайдеться порожнє місце, куди створюється новий вузол. Це зберігає властивість упорядкованості ДДП — кожен лівий нащадок менший, а кожен правий більший за свого предка — без жодного балансування.
Вона зчитує всі значення симетричним обходом, спорожняє дерево, а потім вставляє ті самі значення заново у стилі AVL, застосовуючи ліві та праві повороти щоразу, коли висоти лівого й правого піддерев вузла різняться більш ніж на один. Значення не змінюються, але отримана форма стає збалансованою за висотою, зазвичай значно зменшуючи висоту дерева.
Симетричний обхід відвідує ліве піддерево, потім вузол, потім праве, даючи значення у відсортованому зростаючому порядку. Прямий обхід відвідує спершу вузол, потім ліве, потім праве піддерево, що зручно для копіювання чи серіалізації дерева. Зворотний обхід відвідує обидва піддерева перед самим вузлом — порядок, потрібний для безпечного видалення цілого дерева.
Якщо значення вставляти у вже відсортованому порядку, звичайне ДДП перетворюється на односторонній ланцюжок, не відмінний від зв'язного списку, тож пошук може вимагати перевірки кожного вузла. Спробуйте вставити числа за зростанням, зауважте висоту, а потім натисніть «AVL Баланс», щоб побачити, як висота і найгірший час пошуку різко зменшуються.
Це коефіцієнт балансу вузла: висота його лівого піддерева мінус висота правого. AVL-дерево тримає це значення в межах −1, 0 або +1 для кожного вузла; більша за модулем величина сигналізує про дисбаланс, який потребує повороту для виправлення.