Преди да разберете Червено-черно дърво и AVL дърво разлики, трябва да знаем за червено-черното дърво и AVL дървото поотделно.
Какво е червено-черно дърво?
Червено-черното дърво е самоуравновесено двоично дърво за търсене в който всеки възел съдържа един допълнителен бит информация, който обозначава цвета на възела. Цветът на възела може да бъде червен или черен, в зависимост от битовата информация, съхранявана от възела.
Имоти
Следните са свойствата, свързани с червено-черно дърво:
- Коренният възел на дървото трябва да е черен.
- Червен възел може да има само черни деца. Или можем да кажем, че два съседни възела не могат да бъдат червени на цвят.
- Ако възелът няма ляво или дясно дете, тогава този възел се нарича листов възел. И така, поставяме лявото и дясното дете под листовия възел, известен като нула
Черната дълбочина или черна височина на листен възел може да се дефинира като броя черни, които срещаме, когато се придвижваме от листовия възел към основния възел. Едно от ключовите свойства на Червено-черното дърво е, че всеки листов възел трябва да има еднаква черна дълбочина.
Нека разберем това свойство чрез пример.
В горното дърво има пет възела, в които един е червен, а останалите четири възела са черни. Има три листови възела в горното дърво. Сега изчисляваме черната дълбочина на всеки листов възел. Както можем да забележим, че черната дълбочина на всичките три листа е 2; следователно, това е червено-черно дърво.
Ако дървото не се подчинява на нито едно от горните три свойства, тогава то не е червено-черно дърво.
Височина на червено-черно дърво
Разгледайте h като височината на дървото с n възли. Каква би била най-малката стойност на n?. Стойността на n е най-малката, когато всички възли са черни. Ако дървото съдържа всички черни възли, тогава дървото ще бъде пълно двоично дърво. Ако височината на пълно двоично дърво е h, тогава броят на възлите в дървото е:
n = 2h -1
Каква би била най-голямата стойност на n?
подниз в java
Стойността на n е най-голяма, когато всеки черен възел има две червени деца, но червеният възел не може да има червени деца, така че ще има черни деца. По този начин има редуващи се слоеве от черни и червени деца. Така че, ако броят на черните слоеве е h, тогава броят на червените слоеве също е h; следователно общата височина на дървото става 2h. Общият брой възли е:
n = 2*2h-1
avl дървета
Какво представлява 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 също е дърво за двоично търсене.
Следните правила се прилагат в червено-черно дърво:
- Възелът в червено-черно дърво е червен или черен на цвят.
- Цветът на кореновия възел трябва да е черен.
- Съседните възли не трябва да са червени. С други думи, можем да кажем, че червеният възел не може да има червени деца, но черният възел може да има черни деца.
- Трябва да има еднакъв брой черни възли във всеки път; тогава само дърво може да се счита за червено-черно дърво.
- Външните възли са нулевите възли, които винаги са черни на цвят.
Правило на AVL дървото:
Всеки възел трябва да има коефициент на баланс -1, 0 или 1.
В горната фигура трябва да проверим дали дървото е червено-черно дърво или не. За да проверим това, първо трябва да проверим дали дървото е двоично дърво за търсене или не. Както можем да видим на горната фигура, тя удовлетворява всички свойства на двоичното дърво за търсене; следователно, това е двоично дърво за търсене. Второ, трябва да проверим дали отговаря на горепосочените правила или не. Горното дърво отговаря на всички горни пет правила; следователно се заключава, че горното дърво е червено-черно дърво.
В горната фигура трябва да проверим дали дървото е AVL дърво или не. Тъй като всеки възел има стойност на коефициента на баланс или като -1, 0 или 1, така че това е AVL дърво.
В случай на червено-черно дърво, ако всички горни правила са изпълнени, при условие че едно дърво е двоично дърво за търсене, тогава се казва, че дървото е червено-черно дърво.
В случая на дървото AVL, ако коефициентът на баланс е -1, 0 или 1, тогава се казва, че горното дърво е дърво на AVL.
Ако дървото не е балансирано, тогава се използват два инструмента за балансиране на дървото в червено-черно дърво:
Ако дървото не е балансирано, тогава се използва един инструмент за балансиране на дървото в AVL дървото:
В случая на червено-черното дърво операциите по вмъкване и изтриване са ефективни. Ако дървото се балансира чрез повторното оцветяване, тогава операциите за вмъкване и изтриване са ефективни в червено-черното дърво.
np подложка
В случая на дървото AVL операцията по търсене е ефективна, тъй като изисква само един инструмент за балансиране на дървото.
В случая на червено-черно дърво времевата сложност за всички операции, т.е. вмъкване, изтриване и търсене е O(logn).
В случая на AVL дърво времевата сложност за всички операции, т.е. вмъкване, изтриване и търсене е O(logn).
Нека разберем разликите в табличната форма.
| Параметър | Червено черно дърво | AVL дърво |
|---|---|---|
| Търсене | Red Black Trees не осигурява ефективно търсене, тъй като Red Black Trees са приблизително балансирани. | AVL дървета осигуряват ефективно търсене, тъй като това е строго балансирано дърво. |
| Вмъкване и изтриване | Вмъкването и изтриването са по-лесни в червено черно дърво, тъй като изисква по-малко ротации за балансиране на дървото. | Вмъкването и изтриването са сложни в дървото на AVL, тъй като изисква множество завъртания за балансиране на дървото. |
| Цвят на възела | В червено-черното дърво цветът на възела е червен или черен. | В случай на AVL дървета, няма цвят на възела. |
| Фактор на баланса | Не съдържа балансиращ фактор. Той съхранява само един бит информация, който обозначава червения или черния цвят на възела. | Всеки възел има коефициент на баланс в AVL дървото, чиято стойност може да бъде 1, 0 или -1. Изисква допълнително пространство за съхраняване на фактора на баланс на възел. |
| Строго балансиран | Червено-черните дървета не са строго балансирани. | AVL дърветата са строго балансирани, т.е. височината на лявото поддърво и височината на дясното поддърво се различават най-много с 1. |