Преди да научим за разликите в двоичното дърво за търсене и AVL дървото, трябва да знаем за двоичното дърво за търсене и AVL дървото поотделно.
Какво е двоично дърво за търсене?
The двоично дърво за търсене е дърво двоично дърво. Както знаем, това дърво може да има 'n' брой деца, докато; двоичното дърво може да съдържа най-много две деца. И така, ограничението на двоично дърво също е последвано от дървото за двоично търсене. Всеки възел в дървото за двоично търсене трябва да има най-много две деца; с други думи, можем да кажем, че двоичното дърво за търсене е вариант на двоичното дърво.
Дървото за двоично търсене също следва свойствата на двоичното търсене. При двоично търсене всички елементи в масива трябва да са в сортиран ред. Изчисляваме средния елемент в двоичното търсене, при което лявата част на средния елемент съдържа стойността, по-малка от средната стойност, а дясната част на средния елемент съдържа стойностите, по-големи от средната стойност.
В дървото за двоично търсене средният елемент става кореновият възел, дясната част става дясното поддърво, а лявата част става лявото поддърво. Следователно можем да кажем, че дървото за двоично търсене е комбинация от a двоично дърво и двоично търсене .
Забележка: Двоичното дърво за търсене може да се дефинира като двоично дърво, в което всички елементи на лявото поддърво са по-малки от коренния възел, а всички елементи на дясното поддърво са по-големи от коренния възел.
Времева сложност в двоично дърво за търсене
Ако дървото за двоично търсене е почти балансирано дърво, тогава всички операции ще имат времева сложност от O(вход) защото търсенето е разделено или на ляво, или на дясно поддърво.
файл отворен в java
Ако дървото за двоично търсене е изкривено наляво или надясно, тогава всички операции ще имат времевата сложност на На) защото трябва да преминем до n елемента.
Какво представлява AVL дървото?
Ан AVL дърво е самобалансиращо се двоично дърво за търсене, където разликата между височините на левите и десните поддървета не може да бъде повече от едно. Тази разлика е известна като балансиран фактор. В AVL дървото стойностите на коефициента на баланс могат да бъдат -1, 0 или 1.
Как се случва самобалансирането на двоичното дърво за търсене?
Както знаем, че AVL дървото е самобалансиращо се двоично дърво за търсене. Ако двоичното дърво за търсене не е балансирано, то може да се самобалансира с някои пренареждания. Тези пренареждания могат да бъдат направени с помощта на някои ротации.
Нека разберем самобалансирането чрез пример.
Да предположим, че искаме да вмъкнем 10, 20, 30 в AVL дърво.
Следват начините за вмъкване на 10, 20, 30 в AVL дърво:
Етап 1: Първо създаваме двоично дърво за търсене, както е показано по-долу:
Стъпка 2: На фигурата по-горе можем да видим, че дървото е небалансирано, тъй като факторът на баланс на възел 30 е 2. За да го направим AVL дърво, трябва да извършим някои ротации. Ако извършим правилното завъртане на възел 20, тогава възел 30 ще се движи надолу, докато възел 20 ще се движи нагоре, както е показано по-долу:
Както можем да видим, крайното дърво следва свойството на дървото за двоично търсене и балансирано дърво; следователно, това е AVL дърво.
как да разкриете скрити приложения
В случая дървото беше ляво небалансирано дърво, така че извършваме правилното завъртане на възела.
Етап 1: Първо създаваме двоично дърво за търсене, както е показано по-долу:
Стъпка 2: На горната фигура можем да видим, че дървото е небалансирано, тъй като коефициентът на баланс на възел 10 е -2. За да го направим AVL дърво, трябва да извършим някои ротации. Това е дясно небалансирано дърво, така че ще извършим ляво завъртане. Ако извършим ляво завъртане на възел 20, тогава възел 20 ще се премести нагоре, а възел 10 ще се премести надолу, както е показано по-долу:
Както можем да забележим, последното дърво следва свойството на Двоично дърво за търсене и а балансирано дърво ; следователно, това е 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 дори когато има голям брой възли в дървото, тъй като височината е балансирана. |