Різниця між бінарним деревом і двійковим деревом пошуку

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

Бінарне дерево - це ієрархічна структура даних, в якій кожен вузол має нуль, одного або максимум двох дітей. Кожен вузол містить «лівий» вказівник, «правий» вказівник та елемент даних. Вказівник "root" представляє верхній вузол дерева. Кожен вузол у структурі даних безпосередньо пов'язаний з довільною кількістю вузлів з обох сторін, що називаються дочірніми. Нульовий покажчик представляє двійкове дерево. Не існує конкретного порядку, як організувати вузли у бінарному дереві. Вузли, у яких немає дочірніх вузлів, називаються листовими вузлами, або зовнішніми вузлами.

Простіше кажучи, він визначає організовану функцію маркування на вузлах, яка в свою чергу присвоює деяке випадкове значення кожному вузлу. Все, що має двох дітей та один батьківський вузол, - це двійкове дерево. Бінарні дерева використовуються для зберігання інформації, яка формує ієрархію, як файлова система на вашому персональному комп’ютері. На відміну від масивів, у дерев немає верхньої межі кількості вузлів, оскільки вони пов'язані за допомогою покажчиків, як пов'язані списки. Основні функції Binary Tree включають в себе представлення ієрархічних даних, сортування списків даних, забезпечення ефективних операцій вставки / видалення тощо. Вузли дерева представлені за допомогою структур у C.

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

Бінарне дерево пошуку - це тип даних даних бінарного дерева, в якому вузли розташовані в порядку, отже, також називаються "упорядкованим бінарним деревом". Це структура даних на основі вузла, яка забезпечує ефективний та швидкий спосіб сортування, пошуку, пошуку даних. Для кожного вузла елементи лівого піддерева повинні бути меншими або рівними ключовим у його батьківському вузлі (LP). Не повинно бути дублікатів ключів. Простіше кажучи, це особливий вид структури даних бінарних дерев, який ефективно зберігає та керує елементами в пам'яті.

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

Різниця між бінарним деревом та двійковим деревом пошуку

1. Визначення бінарного дерева та бінарного дерева пошуку - Бінарне дерево - це ієрархічна структура даних, в якій дитина може мати нуль, один або максимум два дочірні вузли; кожен вузол містить лівий покажчик, правий вказівник та елемент даних. Немає конкретного порядку, як слід організувати вузли на дереві. Бінарне дерево пошуку, з іншого боку, є упорядкованим двійковим деревом, в якому існує відносний порядок того, як слід організувати вузли.
2. Будова з Бінарне дерево та двійкове дерево пошуку- Найбільш верхній вузол дерева являє собою кореневий вказівник у двійковому дереві, а лівий і правий вказівники представляють менші дерева з обох боків. Це спеціалізована форма дерева, яка представляє дані в структурі дерева. Бінарне дерево пошуку, з іншого боку, - це тип двійкового дерева, в якому всі вузли в лівому піддереві менше або дорівнюють значенню кореневого вузла, а правого піддерева більше або дорівнює значенню кореневого вузла.
3. Операція з Бінарне дерево та двійкове дерево пошуку- Бінарним деревом може бути все, що має двох дітей та одного батька. Поширені операції, які можна виконати на двійковому дереві, - це вставлення, видалення та обхід. Двійкові дерева пошуку - це більше сортовані двійкові дерева, що дозволяє швидко та ефективно шукати, вставляти та видаляти елементи. На відміну від бінарних дерев, дерева двійкових пошуків сортують свої ключі, тому пошук зазвичай здійснює двійковий пошук операцій.
4. Типи з Бінарне дерево та двійкове дерево пошуку- Існують різні типи бінарних дерев, поширеними є «Повне бінарне дерево», «Повне бінарне дерево», «Ідеальне бінарне дерево» та «Розширене бінарне дерево». Деякі поширені типи дерев бінарного пошуку включають дерева TL, дерева AVL, дерева Splay, дерева танго, червоно-чорні дерева тощо.

Бінарне дерево порівняно з бінарним деревом пошуку: порівняльна діаграма

Підсумок двійкового дерева та двійкового дерева пошуку

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