Перш ніж дізнатися про відмінності між двійковим деревом пошуку та деревом AVL, нам слід знати про двійкове дерево пошуку та дерево AVL окремо.
Що таке бінарне дерево пошуку?
The двійкове дерево пошуку це дерево двійкове дерево. Як ми знаємо, це дерево може мати 'n' кількість дітей, тоді як; двійкове дерево може містити щонайбільше двох дітей. Отже, за обмеженням бінарного дерева також слідує бінарне дерево пошуку. Кожен вузол у двійковому дереві пошуку повинен мати щонайбільше двох дітей; іншими словами, ми можемо сказати, що бінарне дерево пошуку є варіантом бінарного дерева.
Двійкове дерево пошуку також відповідає властивостям бінарного пошуку. У двійковому пошуку всі елементи в масиві мають бути відсортовані. Ми обчислюємо середній елемент у бінарному пошуку, у якому ліва частина середнього елемента містить значення, менше середнього значення, а права частина середнього елемента містить значення, більші за середнє значення.
У бінарному дереві пошуку середній елемент стає кореневим вузлом, права частина стає правим піддеревом, а ліва частина стає лівим піддеревом. Тому можна сказати, що бінарне дерево пошуку є комбінацією a бінарне дерево і двійковий пошук .
Примітка. Двійкове дерево пошуку можна визначити як двійкове дерево, у якому всі елементи лівого піддерева менші за кореневий вузол, а всі елементи правого піддерева більші за кореневий вузол.
Часова складність у бінарному дереві пошуку
Якщо бінарне дерево пошуку є майже збалансованим деревом, тоді всі операції матимуть часову складність O (вхід) тому що пошук розділений на ліве або праве піддерево.
комбінації клавіш linux
Якщо бінарне дерево пошуку зміщено вліво або вправо, тоді всі операції матимуть часову складність O(n) тому що нам потрібно пройти до n елементів.
Що таке дерево AVL?
Ан Дерево AVL це самобалансуюче бінарне дерево пошуку, де різниця між висотами лівого та правого піддерев не може бути більшою за одиницю. Ця різниця відома як фактор балансу. У дереві AVL значення коефіцієнта балансу можуть бути -1, 0 або 1.
Як відбувається самобалансування бінарного дерева пошуку?
Як ми знаємо, дерево AVL є самобалансуючим бінарним деревом пошуку. Якщо бінарне дерево пошуку не збалансоване, його можна самозбалансувати за допомогою деяких змін. Ці зміни можна здійснити за допомогою певних обертань.
Давайте розберемося в самобалансуванні на прикладі.
Припустимо, ми хочемо вставити 10, 20, 30 у дереві AVL.
Нижче наведено способи вставлення 10, 20, 30 у дерево AVL:
стек в java
Крок 1: Спочатку ми створюємо бінарне дерево пошуку, як показано нижче:
Крок 2: На наведеному вище малюнку ми можемо спостерігати, що дерево незбалансоване, оскільки коефіцієнт балансу вузла 30 дорівнює 2. Щоб зробити його деревом AVL, нам потрібно виконати деякі обертання. Якщо ми виконаємо правильний поворот на вузлі 20, то вузол 30 рухатиметься вниз, тоді як вузол 20 рухатиметься вгору, як показано нижче:
Як ми бачимо, кінцеве дерево відповідає властивостям дерева бінарного пошуку та збалансованого дерева; отже, це дерево AVL.
У справі дерево було ліве незбалансоване дерево, тому виконуємо правильний поворот на вузлі.
Крок 1: Спочатку ми створюємо бінарне дерево пошуку, як показано нижче:
Крок 2: На наведеному вище малюнку ми бачимо, що дерево незбалансоване, оскільки коефіцієнт балансу вузла 10 дорівнює -2. Щоб зробити його деревом AVL, нам потрібно виконати кілька обертань. Це праве незбалансоване дерево, тому ми будемо виконувати обертання вліво. Якщо ми виконуємо обертання вліво на вузлі 20, то вузол 20 рухатиметься вгору, а вузол 10 рухатиметься вниз, як показано нижче:
java передає int до рядка
Як ми можемо помітити, остаточне дерево відповідає властивості Двійкове дерево пошуку і а збалансоване дерево ; отже, це дерево AVL.
Крок 1: Спочатку ми створюємо двійкове дерево пошуку, як показано нижче:
Крок 2: На наведеному вище малюнку ми можемо спостерігати, що дерево незбалансоване, оскільки коефіцієнт балансу кореневого вузла дорівнює 2. Щоб зробити його деревом AVL, нам потрібно виконати деякі обертання. Наведений вище сценарій є незбалансованим ліворуч і праворуч, оскільки один вузол знаходиться ліворуч від батьківського вузла, а інший – праворуч від батьківського вузла. Спочатку ми виконаємо поворот ліворуч, і обертання відбувається між вузлами 10 і 20. Після обертання ліворуч 20 рухатиметься вгору, а 10 рухатиметься вниз, як показано нижче:
Все одно дерево незбалансоване, тому ми виконуємо правильне обертання на дереві. Після того, як на дереві буде виконано правильне обертання, дерево матиме наступне:
Як ми можемо спостерігати у наведеному вище дереві, дерево відповідає властивості дерева бінарного пошуку та збалансованого дерева; отже, це дерево AVL.
Крок 1: Спочатку ми створюємо двійкове дерево пошуку, як показано нижче:
Крок 2: На наведеному вище малюнку ми можемо помітити, що дерево незбалансоване, оскільки коефіцієнт балансу кореневого вузла дорівнює 2. Щоб зробити його деревом AVL, нам потрібно виконати деякі обертання. Наведений вище сценарій є незбалансованим право-ліворуч, оскільки один вузол знаходиться праворуч від батьківського вузла, а інший вузол – ліворуч від батьківського вузла. Спочатку ми виконаємо правильний поворот, який відбувається між вузлами 30 і 20. Після правого обертання 20 рухатиметься вгору, а 30 рухатиметься вниз, як показано нижче:
Тим не менш, наведене вище дерево незбалансоване, тому нам потрібно виконати поворот ліворуч на вузлі. Після виконання повороту вліво вузол 20 переміститься вгору, а вузол 10 переміститься вниз, як показано нижче:
Як ми можемо спостерігати у наведеному вище дереві, дерево відповідає властивості дерева бінарного пошуку та збалансованого дерева; отже, це дерево AVL.
Відмінності між бінарним деревом пошуку та деревом AVL
| Двійкове дерево пошуку | Дерево AVL |
|---|---|
| Кожне бінарне дерево пошуку є двійковим деревом, оскільки обидва дерева містять щонайбільше два дочірніх дерева. | Кожне дерево AVL також є двійковим деревом, оскільки дерево AVL також має найбільше двох дітей. |
| У BST не існує такого терміну, як фактор балансу. | У дереві AVL кожен вузол містить коефіцієнт балансу, а значення коефіцієнта балансу має бути -1, 0 або 1. |
| Будь-яке бінарне дерево пошуку не є деревом AVL, оскільки BST може бути як збалансованим, так і незбалансованим деревом. | Кожне дерево AVL є бінарним деревом пошуку, оскільки дерево AVL слідує властивостям BST. |
| Кожен вузол у дереві бінарного пошуку складається з трьох полів, тобто лівого піддерева, значення вузла та правого піддерева. | Кожен вузол у дереві AVL складається з чотирьох полів, тобто лівого піддерева, значення вузла, правого піддерева та коефіцієнта балансу. |
| У випадку дерева бінарного пошуку, якщо ми хочемо вставити будь-який вузол у дерево, ми порівнюємо значення вузла з кореневим значенням; якщо значення вузла більше значення кореневого вузла, тоді вузол вставляється в праве піддерево, інакше вузол вставляється в ліве піддерево. Після того, як вузол вставлено, немає потреби перевіряти коефіцієнт балансу висоти для завершення вставки. | У випадку дерева AVL спочатку ми знайдемо відповідне місце для вставки вузла. Коли вузол буде вставлено, ми обчислимо коефіцієнт балансу кожного вузла. Якщо коефіцієнт балансу кожного вузла задовольняється, вставлення завершено. Якщо коефіцієнт балансу більше 1, то нам потрібно виконати кілька обертів, щоб збалансувати дерево. |
| У дереві бінарного пошуку висота або глибина дерева дорівнює O(n), де n — кількість вузлів у дереві бінарного пошуку. | У дереві AVL висота або глибина дерева дорівнює O(logn). |
| Його легко реалізувати, оскільки ми повинні дотримуватися властивостей бінарного пошуку, щоб вставити вузол. | Це складно реалізувати, тому що в дереві AVL ми повинні спочатку побудувати дерево AVL, а потім перевірити баланс висоти. Якщо висота є дисбалансом, нам потрібно виконати кілька обертів, щоб збалансувати дерево. |
| BST не є збалансованим деревом, оскільки воно не дотримується концепції фактора балансу. | Дерево AVL є деревом із збалансованою висотою, оскільки воно дотримується концепції фактора балансу. |
| Пошук неефективний у BST, коли в дереві доступна велика кількість вузлів, оскільки висота не збалансована. | Пошук є ефективним у дереві AVL, навіть якщо в дереві є велика кількість вузлів, оскільки висота збалансована. |