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

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

А Бінарне дерево цеПокажчик на ліву дитину:Він зберігає посилання лівого дочірнього вузла.Покажчик на праву дитину:Він зберігає посилання правого дочірнього вузла.Елемент даних:Елемент даних — це значення даних, які зберігаються вузлом.

Двійкове дерево можна представити у вигляді:

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

Основні терміни, які використовуються в бінарному дереві:

перетворити int на рядок

Кореневий вузол:Кореневий вузол — це перший або найвищий вузол у бінарному дереві.Батьківський вузол:Коли вузол з’єднаний з іншим вузлом через ребра, цей вузол називається батьківським. У бінарному дереві батьківський вузол може мати максимум 2 дочірніх вузла.Дочірній вузол:Якщо вузол має свого попередника, то цей вузол називається a дочірній вузол .Листовий вузол:Вузол, який не містить жодного дочірнього елемента, відомий як a листовий вузол .Внутрішній вузол:Вузол, який має принаймні 2 дочірніх вузла, відомий як an внутрішній вузол .Глибина вузла:Відстань від кореневого вузла до даного вузла відома як a глибина вузла . Ми надаємо мітки всім вузлам, наприклад, кореневий вузол позначено 0, оскільки він не має глибини, дочірні елементи кореневих вузлів позначено 1, дочірні елементи кореневого дочірнього вузла позначено 2.Висота:Найдовша відстань від кореневого вузла до листового вузла - це висота вузла .

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

n = 2^m+1-1

алгоритм rr

де n – кількість вузлів, m – глибина вузла.

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

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

Розберемо концепцію бінарного дерева пошуку на прикладах.

На наведеному вище малюнку ми бачимо, що значення кореневого вузла дорівнює 15, що більше, ніж значення всіх вузлів у лівому піддереві. Значення кореневого вузла менше, ніж значення всіх вузлів правого піддерева. Тепер ми переходимо до лівого дочірнього елемента кореневого вузла. 10 більше за 8 і менше за 12; він також задовольняє властивості бінарного дерева пошуку. Тепер ми переходимо до правого дочірнього елемента кореневого вузла; значення 20 більше за 17 і менше за 25; він також задовольняє властивості бінарного дерева пошуку. Таким чином, ми можемо сказати, що показано вище дерево є бінарним деревом пошуку.

Тепер, якщо ми змінимо значення 12 на 16 у наведеному вище двійковому дереві, ми маємо з’ясувати, чи є воно все ще бінарним деревом пошуку чи ні.

Значення кореневого вузла становить 15, що більше за 10, але менше за 16, тому воно не задовольняє властивості бінарного дерева пошуку. Тому це не бінарне дерево пошуку.

алгоритм к-нн

Операції над бінарним деревом пошуку

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

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

Спочатку ми обчислимо середній елемент і порівняємо середній елемент з елементом, який потрібно шукати. Середній елемент обчислюється за допомогою n/2. Значення n дорівнює 7; отже, середній елемент дорівнює 15. Середній елемент не дорівнює шуканому елементу, тобто 10.

Примітка. Якщо шуканий елемент менший за середній елемент, то пошук виконуватиметься в лівій половині; інакше пошук здійснюватиметься на правій половині. У випадку рівності елемент знайдений.

Оскільки елемент, який потрібно шукати, менший за середній елемент, тому пошук виконуватиметься в лівому масиві. Тепер пошук зменшено наполовину, як показано нижче:

Середній елемент у лівому масиві дорівнює 10, що дорівнює шуканому елементу.

Часова складність

У двійковому пошуку є n елементів. Якщо середній елемент не дорівнює шуканому елементу, тоді простір пошуку скорочується до n/2, і ми будемо продовжувати скорочувати простір пошуку на n/2, поки не знайдемо елемент. У цілому скорочення, якщо ми переходимо від n до n/2 до n/4 і так далі, тоді це займе log₂n кроків.

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

char + int у java