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

Зміст:

Anonim

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

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

У цьому посібнику зі структури даних ви дізнаєтесь:

  • Що таке бінарне дерево пошуку?
  • Атрибути бінарного дерева пошуку
  • Навіщо нам бінарне дерево пошуку?
  • Типи бінарних дерев
  • Як працює бінарне дерево пошуку?
  • Важливі терміни

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пошукова операція

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

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

Операція вставки

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

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

Видалити операції

Видалення - найдосконаліша і найскладніша серед усіх інших операцій. У 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. 1 Видаліть вузол 12 із двома дочірніми структурами
  2. 2 Видалення вузла відбуватиметься на основі правила In Order Successor, що означає, що найбільший елемент у правому піддереві з 12 замінить його
  3. 3 Видаліть вузол 12 і замініть його на 19, оскільки це найбільше значення в правому піддереві
  4. 4 Перегляньте нову структуру BST після видалення 12

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

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

Резюме

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