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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пошук Operaції

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

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

Псевдокод для пошуку в BST

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ції

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

Існує список із 6 елементів, які потрібно вставити в BST у порядку зліва направо
Вставте 12 як кореневий вузол і порівняйте наступні значення 7 і 9 для відповідного вставлення в праве і ліве піддерево
Порівняйте решту значень 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 – У порядку наступника: вам потрібно видалити вузол із двома дочірніми вузлами та замінити його найбільшим значенням у правому піддереві видаленого вузла

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

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

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

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

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

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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

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

Вставити: вставити елемент у дерево/створити дерево.
Пошук: пошук елемента в дереві.
Preorder Traversal: обхід дерева за попереднім замовленням.
Обхід у порядку: перетинає дерево в порядку.
Postorder Traversal: обходить дерево в порядку після замовлення.

Підсумки

BST — це алгоритм розширеного рівня, який виконує різні операції на основі порівняння значень вузла з кореневим вузлом.
Будь-яка точка в ієрархії «батько-нащадок» представляє вузол. Принаймні один батьківський або кореневий вузол залишається присутнім весь час.
Є ліве піддерево і праве піддерево. Ліве піддерево містить значення, менші за кореневий вузол. Однак праве піддерево містить значення, яке перевищує кореневий вузол.
Кожен вузол може мати нуль, один або два дочірніх вузла.
Двійкове дерево пошуку полегшує такі основні операції, як пошук, вставка та видалення.
Видалення є найскладнішим і має кілька випадків, наприклад, вузол без дочірнього елемента, вузол з одним дочірнім елементом і вузол з двома дочірніми елементами.
Алгоритм використовується в реальних рішеннях, таких як ігри, дані автозаповнення та графіка.