Двійкове дерево пошуку (BST) із прикладом

Що таке бінарне дерево пошуку?

Бінарне дерево пошуку (BST) – це вдосконалений алгоритм, який використовується для аналізу вузла, його лівої та правої гілок, що моделюються у деревоподібній структурі, та повернення значення. BST розроблено на основі архітектури базового алгоритму бінарного пошуку; отже, воно дозволяє швидше виконувати пошук, вставку та видалення вузлів. Це робить програму дуже швидкою та точною.

Атрибути бінарного дерева пошуку

BST складається з кількох вузлів і складається з таких атрибутів:

• Вузли дерева представлені у зв'язку "батьківський елемент-дитина".
• Кожен батьківський вузол може мати нуль дочірніх вузлів або максимум два підвузли чи піддерева зліва та справа.
• Кожне піддерево, також відоме як бінарне дерево пошуку, має підгілки справа та зліва від себе.
• Усі вузли пов’язані парами ключ-значення.
• Ключі вузлів, присутніх у лівому піддереві, менші за ключі їхнього батьківського вузла.
• Аналогічно, ключі вузлів, присутніх у правому піддереві, більші за ключі їхнього батьківського вузла.

1. Існує головний вузол або батьківський рівень 11. Під ним розташовані ліві та праві вузли/гілки з власними значеннями ключів.
2. Праве піддерево має ключові значення, більші за батьківський вузол.
3. Ліве піддерево має менше ключових значень, ніж батьківський вузол.

Навіщо нам двійкове дерево пошуку?

• Два основні фактори, які роблять бінарне дерево пошуку оптимальним рішенням будь-якої реальної проблеми, це швидкість і точність.
• Завдяки тому, що бінарний пошук виконується у форматі, подібному до гілки, із зв’язками «батько-нащадок», алгоритм знає, у якому місці дерева потрібно шукати елементи. Це зменшує кількість порівнянь ключ-значення, які програма повинна зробити, щоб знайти потрібний елемент.
• Крім того, якщо елемент, який потрібно знайти, більший або менший за батьківський вузол, вузол знає, на якій стороні дерева шукати. Причина полягає в тому, що ліве піддерево завжди менше за батьківський вузол, а праве піддерево має значення, які завжди дорівнюють або більші за батьківський вузол.
• BST зазвичай використовується для реалізації складних пошуків, надійної логіки гри, автозавершення дій і графіки.
• Алгоритм ефективно підтримує такі операції, як пошук, вставка та видалення.

Типи бінарних дерев

Є три види бінарних дерев:

• Повне бінарне дерево: Усі рівні дерева заповнені, за можливим винятком останнього рівня. Аналогічно, всі вузли заповнені, спрямовуючи їх до крайнього лівого краю.
• Повне бінарне дерево: Усі вузли мають 2 дочірні вузли, окрім листка.
• Збалансоване або ідеальне бінарне дерево: У дереві всі вузли мають двох дочірніх вузлів. Крім того, для кожного підвузла існує однаковий рівень.

Дізнайтеся більше про Бінарне дерево в структурі даних якщо ви зацікавлені.

Як працює бінарне дерево пошуку?

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

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

BST насамперед пропонує такі три типи операцій для вашого використання:

• Пошук: шукає елемент у бінарному дереві.
• Вставити: додає елемент до бінарного дерева.
• Видалити: видаляє елемент з бінарного дерева.

Кожна операція має власну структуру та метод виконання/аналізу, але найскладнішою з усіх є операція Delete.

Пошук Operaції

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

1. Елемент, який потрібно знайти, дорівнює 10.
2. Порівняйте елемент з кореневим вузлом 12, 10 < 12, отже, ви переходите до лівого піддерева. Немає потреби аналізувати праве піддерево.
3. Тепер порівняйте 10 з вузлом 7, 10 > 7, тож перейдіть до правого піддерева.
4. Потім порівняйте 10 з наступним вузлом, який дорівнює 9, 10 > 9, і перегляньте правий дочірній елемент піддерева.
5. 10 збігається зі значенням у вузлі, 10 = 10, повертає значення користувачеві.

Псевдо Code для пошуку за британським літнім часом

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

Insert Operaції

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

1. Існує список із 6 елементів, які потрібно вставити в BST по порядку зліва направо.
2. Вставте 12 як кореневий вузол та порівняйте наступні значення 7 та 9 для відповідної вставки у праве та ліве піддерево.
3. Порівняйте значення 19, 5 та 10, що залишилися, з кореневим вузлом 12 та розмістіть їх відповідно. 19 > 12, розмістіть його як правого дочірнього елемента 12; 5 < 12 та 5 < 7, отже, розмістіть його як лівого дочірнього елемента 7. Тепер порівняйте 10, 10 < 12 та 10 > 7 та 10 > 9, розмістіть 10 як праве піддерево 9.

Псевдокод для вставки вузла в BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

видаляти Operaвих

Для видалення вузла з BST є кілька випадків, тобто видалення кореневого вузла або видалення кінцевого вузла. Також, після видалення кореневого вузла, нам потрібно подумати про кореневий вузол.

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

• Випадок 1 – Вузол без дочірніх елементів: Це найпростіша ситуація, вам просто потрібно видалити вузол, який не має більше дітей праворуч чи ліворуч.
• Випадок 2 – Вузол з одним дочірнім елементом: Після видалення вузла просто з'єднайте його дочірній вузол з батьківським вузлом видаленого значення.
• Випадок 3 – Вузол з двома дочірніми елементами: це найскладніша ситуація, і вона працює за такими двома правилами:
  • 3a – Попередник за порядком: вам потрібно видалити вузол з двома дочірніми елементами та замінити його найбільшим значенням у лівому піддереві видаленого вузла.
  • 3b – Наступник за порядком: вам потрібно видалити вузол з двома дочірніми елементами та замінити його найменшим значенням у правому піддереві видаленого вузла.

1. Це перший випадок видалення, коли ви видаляєте вузол, який не має дочірніх елементів. Як видно на діаграмі, 19, 10 та 5 не мають дочірніх елементів. Але ми видалимо 19.
2. Видаліть значення 19 і видаліть посилання з вузла.
3. Перегляньте нову структуру BST без 19.

1. Це другий випадок видалення, коли ви видаляєте вузол, який має 1 дочірній елемент. Як видно на діаграмі, 9 має одного дочірнього елемента.
2. Видаліть вузол 9 та замініть його дочірнім вузлом 10, а також додайте посилання з 7 на 10.
3. Перегляньте нову структуру BST без 9.

1. Тут ви видалите вузол 12, який має двох дочірніх елементів.
2. Видалення вузла відбуватиметься на основі правила попередника в порядку, що означає, що найбільший елемент у лівому піддереві з 12 замінить його.
3. Видаліть вузол 12 та замініть його на 10, оскільки це найбільше значення в лівому піддереві.
4. Перегляньте нову структуру BST після видалення 12.

1. Видалити вузол 12, який має двох дочірніх елементів.
2. Видалення вузла відбуватиметься на основі правила наступника в порядку порядку, що означає, що найменший елемент у правому піддереві з 12 замінить його.
3. Видаліть вузол 12 та замініть його на 19, оскільки це найменше значення у правому піддереві.
4. Перегляньте нову структуру BST після видалення 12.

Псевдо Code для видалення вузла

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Важливі терміни

• Вставити: Вставляє елемент у дерево / створює дерево.
• Пошук: Шукає елемент у дереві.
• Проходження попереднього замовлення: Обходить дерево у попередньому порядку.
• Обхід у порядку: Обходить дерево по порядку.
• Проходження поштової скриньки: Обходить дерево після порядку.

Поширені запитання