Перш ніж зрозуміти Червоно-чорне дерево та дерево AVL відмінності, ми повинні знати про червоно-чорне дерево та дерево AVL окремо.

Що таке червоно-чорне дерево?

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

Властивості

Нижче наведено властивості, пов’язані з червоно-чорним деревом:

• Кореневий вузол дерева має бути чорним.
• Червоний вузол може мати лише чорних дітей. Або ми можемо сказати, що два сусідні вузли не можуть бути червоного кольору.
• Якщо вузол не має лівого чи правого дочірнього елемента, тоді цей вузол називається листовим вузлом. Отже, ми розмістили ліву та праву дочірні елементи під листовим вузлом, відомим як нуль

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

Розберемо цю властивість на прикладі.

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

Якщо дерево не підкоряється жодній із трьох наведених вище властивостей, то воно не є червоно-чорним деревом.

Висота червоно-чорного дерева

Розглянемо h як висоту дерева, що має n вузлів. Яким буде найменше значення n?. Значення n є найменшим, коли всі вузли чорні. Якщо дерево містить усі чорні вузли, то воно буде повним бінарним деревом. Якщо висота повного бінарного дерева дорівнює h, то кількість вузлів у дереві дорівнює:

n = 2 год -1

Яке буде найбільше значення n?

примірник java

Значення n є найбільшим, коли кожен чорний вузол має двох червоних дітей, але червоний вузол не може мати червоних дітей, тому він матиме чорних дітей. Таким чином, чергуються шари чорних і червоних дітей. Отже, якщо кількість чорних шарів дорівнює h, то кількість червоних шарів також дорівнює h; тому загальна висота дерева стає 2h. Загальна кількість вузлів:

n = 2*2h-1

Що таке дерево AVL?

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

У наведеному вище дереві найгірша часова складність для пошуку елемента становить O(h), тобто висота дерева. У наведеному вище випадку кількість порівнянь, зроблених для пошуку елемента 17, дорівнює 4, а висота дерева також дорівнює 4.

Якщо ми розглянемо перекошене бінарне дерево, як показано нижче:

У наведеному вище правому скошеному дереві кількість порівнянь, зроблених для пошуку елемента 17, дорівнює 5, і кількість елементів, присутніх у дереві, також дорівнює 5. Тому можна сказати, що якщо дерево є скошеним бінарним деревом, то часова складність буде O(n).

Тепер ми повинні збалансувати ці перекошені дерева так, щоб вони мали часову складність O(h). Існує термін, відомий як a фактор балансу , який використовується для самозбалансування бінарного дерева пошуку. Коефіцієнт балансу можна обчислити як:

Значення коефіцієнта балансу може бути 1, 0 або -1. Якщо кожен вузол у бінарному дереві має значення 1, 0 або -1, то це дерево вважається збалансованим бінарне дерево або дерево AVL.

Дерево вважається ідеально збалансованим, якщо коефіцієнт балансу кожного вузла дорівнює 0. Дерево AVL є майже збалансованим деревом, оскільки кожен вузол у дереві має значення коефіцієнта балансу 1, 0 або -1.

Відмінності між червоно-чорним деревом і деревом AVL.

Нижче наведено відмінності між червоно-чорним деревом і деревом AVL:

Двійкове дерево пошуку

Червоно-чорне дерево є бінарним деревом пошуку, а дерево AVL також є бінарним деревом пошуку.

правила

У червоно-чорному дереві застосовуються такі правила:

підрядок у java

1. Вузол у червоно-чорному дереві червоного або чорного кольору.
2. Колір кореневого вузла повинен бути чорним.
3. Прилеглі вузли не повинні бути червоними. Іншими словами, ми можемо сказати, що червоний вузол не може мати червоних дітей, але чорний вузол може мати чорних дітей.
4. На кожному шляху має бути однакова кількість чорних вузлів; тоді червоно-чорним деревом можна вважати лише дерево.
5. Зовнішні вузли - це нульові вузли, які завжди чорного кольору.

Правило дерева AVL:

Кожен вузол повинен мати коефіцієнт балансу як -1, 0 або 1.

приклад

На наведеному вище малюнку нам потрібно перевірити, чи є дерево червоно-чорним чи ні. Щоб перевірити це, спочатку нам потрібно перевірити, чи є дерево бінарним деревом пошуку чи ні. Як ми бачимо на наведеному вище малюнку, воно задовольняє всі властивості бінарного дерева пошуку; отже, це бінарне дерево пошуку. По-друге, ми повинні перевірити, чи задовольняє він вищезазначеним правилам чи ні. Наведене вище дерево задовольняє всім наведеним п'яти правилам; отже, він робить висновок, що вищевказане дерево є червоно-чорним деревом.

На наведеному вище малюнку нам потрібно перевірити, чи є дерево деревом AVL чи ні. Оскільки кожен вузол має значення коефіцієнта балансу як -1, 0 або 1, тож це дерево AVL.

Як можна вважати дерево збалансованим чи ні?

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

У випадку дерева AVL, якщо коефіцієнт балансу дорівнює -1, 0 або 1, то вищезгадане дерево вважається деревом AVL.

Інструменти, що використовуються для балансування

Якщо дерево не збалансоване, то для збалансування дерева в червоно-чорному дереві використовуються два інструменти:

Перефарбування Обертання

Якщо дерево не збалансоване, то для збалансування дерева в дереві AVL використовується один інструмент:

Обертання

Ефективно для якої операції

У випадку червоно-чорного дерева операції вставки та видалення є ефективними. Якщо дерево врівноважено через перефарбування, то операції вставки та видалення ефективні в червоно-чорному дереві.

діаграма класів java

У випадку дерева AVL операція пошуку ефективна, оскільки вимагає лише одного інструменту для балансування дерева.

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

У випадку червоно-чорного дерева складність часу для всіх операцій, тобто вставки, видалення та пошуку, становить O(logn).

У випадку дерева AVL часова складність для всіх операцій, тобто вставки, видалення та пошуку, становить O(logn).

Розберемося в відмінностях табличної форми.