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

Ключова різниця - Бінарне дерево проти Двійкове дерево пошуку
 

Структура даних - це систематизований спосіб організації даних для їх ефективного використання. Впорядкування даних за допомогою структури даних повинно скоротити час виконання або час виконання. Також структура даних повинна вимагати мінімального обсягу пам'яті. Іноді дані можуть бути розташовані у структурі дерева. Дерево являє собою вузол, з'єднаний ребрами. Найвищий вузол - це корінь. Кожен вузол може мати максимум два вузли. Вони відомі як дочірні вузли. Вузол зліва від батьківського вузла - лівий дочірній вузол, а вузол праворуч від батьківського вузла - правий вузол. Бінарне дерево та двійкове дерево пошуку - це дві структури даних дерева. Бінарне дерево - це тип структури даних, де кожен батьківський вузол може мати щонайменше два дочірні вузли. Двійкове дерево пошуку - це двійкове дерево, де ліва дочірка містить лише вузли зі значеннями, меншими або рівними батьківському вузлу, і де права дитина містить лише вузли зі значеннями, що перевищують батьківський вузол. Це те саме ключова різниця. На відміну від структур даних, таких як масиви, бінарне дерево та двійкове дерево пошуку не мають верхньої межі для зберігання даних.

ЗМІСТ

1. Огляд та ключові відмінності
2. Що таке бінарне дерево
3. Що таке двійкове дерево пошуку
4. Подібність між бінарним деревом та двійковим деревом пошуку
5. Бічне порівняння - Бінарне дерево та Двійкове дерево пошуку в табличній формі
6. Підсумок

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

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

Малюнок 01: Приклад бінарного дерева

Вище - приклад двійкового дерева. Елемент 2 у верхній частині дерева - корінь. Кожен вузол має максимум два вузли. Якщо дерево містить певні цикли або якщо один вузол містить більше двох вузлів, його не можна класифікувати як двійкове дерево. Щоб перейти від одного вузла до іншого, завжди є одна стежка. Дочірніми вузлами кореневого вузла 2 є 7 та 5. Можливо також, що у вузла немає вузлів. Але будь-який вузол не може мати більше двох вузлів. Правий елемент кореня дорівнює 5. Цей елемент 5 є батьківським вузлом для дочірнього вузла 9. У вузлах 4 і 11 немає дочірніх елементів. Тому вони є листовими вузлами.

Бінарне дерево використовується для зберігання даних в ієрархічному порядку. Це схоже на файлову структуру комп’ютера. Структура даних, як масив, може зберігати певний обсяг даних. Але у двійкового дерева немає верхньої межі кількості вузлів.

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

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

Малюнок 02: Приклад дерева двійкового пошуку

Елемент 8 є найвищим елементом. Тому це кореневий вузол. Якщо 3 є батьківським вузлом, то 1 і 6 є дочірніми вузлами. 1 - лівий дочірній вузол, а 6 - правий дочірній вузол. Ліва дитина містить значення, менші або рівні батьківського вузла. Коли 3 є батьківським вузлом, ліва сторона повинна мати елемент, менший або рівний 3. У цьому прикладі він дорівнює 1. Правий дочір містить лише вузли зі значеннями, що перевищують батьківський вузол. Коли 3 - це батьківський вузол, правий дочірній вузол повинен мати більш високе значення, ніж 3. У цьому прикладі це 6. Так само є певний порядок упорядкування кожного елемента даних бінарним деревом пошуку. Саме структура даних забезпечує ефективний спосіб сортування, отримання та пошуку даних.

Які подібності між бінарним деревом та двійковим деревом пошуку?

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

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

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

Підсумок - Бінарне дерево проти Двійкове дерево пошуку 

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

Завантажте PDF-файл Binary Tree vs Binary Search Tree

Ви можете завантажити PDF-версію цієї статті та використовувати її в офлайн-цілях відповідно до посилань. Завантажте PDF-версію тут: Різниця між бінарним деревом та двійковим деревом пошуку

Довідка:

1.Будинка, Підручники. “Структури даних та дерево алгоритмів.”, Підручник, 8 січня 2018 р. Доступний тут
2. Різниця між бінарним деревом та деревом бінарного пошуку. | javapedia.Net, Javapedia.net, 15 лютого 2017. Доступно тут

Надано зображення:

1. 'Бінарне дерево' від Derrick Coetzee - власна робота, (загальнодоступне надбання) через Вікісховище
2. 'Двійкове дерево пошуку'. Немає автора, який читається машиною. (на основі претензій щодо авторських прав)., (Public Domain) через Вікісховище Commons