Zanim dowiemy się o różnicach w drzewie wyszukiwania binarnego i drzewie AVL, powinniśmy wiedzieć osobno o drzewie wyszukiwania binarnego i drzewie AVL.
Co to jest drzewo wyszukiwania binarnego?
The drzewo wyszukiwania binarnego jest drzewo drzewo binarne. Jak wiemy, drzewo to może mieć „n” liczbę dzieci, natomiast; drzewo binarne może zawierać maksymalnie dwoje dzieci. Zatem po ograniczeniu drzewa binarnego następuje również drzewo wyszukiwania binarnego. Każdy węzeł w drzewie wyszukiwania binarnego powinien mieć maksymalnie dwoje dzieci; innymi słowy, możemy powiedzieć, że drzewo wyszukiwania binarnego jest odmianą drzewa binarnego.
Drzewo wyszukiwania binarnego również jest zgodne z właściwościami wyszukiwania binarnego. W wyszukiwaniu binarnym wszystkie elementy tablicy muszą być posortowane. Element środkowy obliczamy w wyszukiwaniu binarnym, w którym lewa część środkowego elementu zawiera wartość mniejszą od wartości środkowej, a prawa część środkowego elementu zawiera wartości większe od wartości środkowej.
W drzewie wyszukiwania binarnego środkowy element staje się węzłem głównym, prawa część staje się prawym poddrzewem, a lewa część lewym poddrzewem. Dlatego możemy powiedzieć, że drzewo wyszukiwania binarnego jest kombinacją a drzewo binarne I wyszukiwanie binarne .
Uwaga: Binarne drzewo wyszukiwania można zdefiniować jako drzewo binarne, w którym wszystkie elementy lewego poddrzewa są mniejsze niż węzeł główny, a wszystkie elementy prawego poddrzewa są większe niż węzeł główny.
Złożoność czasowa w drzewie wyszukiwania binarnego
Jeśli drzewo wyszukiwania binarnego jest drzewem prawie zrównoważonym, wówczas wszystkie operacje będą miały złożoność czasową wynoszącą O(zaloguj się) ponieważ wyszukiwanie jest podzielone na lewe lub prawe poddrzewo.
blokuj reklamy na YouTube na Androida
Jeśli drzewo wyszukiwania binarnego jest przekrzywione w lewo lub w prawo, wówczas wszystkie operacje będą miały złożoność czasową wynoszącą NA) ponieważ musimy przejść aż do n elementów.
Co to jest drzewo AVL?
Jakiś Drzewo AVL to samobalansujące się drzewo poszukiwań binarnych, w którym różnica między wysokościami lewego i prawego poddrzewa nie może być większa niż jeden. Różnica ta nazywana jest czynnikiem równowagi. W drzewie AVL wartości współczynnika równowagi mogą wynosić -1, 0 lub 1.
W jaki sposób następuje samorównoważenie drzewa wyszukiwania binarnego?
Jak wiemy, drzewo AVL jest samobalansującym się drzewem wyszukiwania binarnego. Jeśli drzewo wyszukiwania binarnego nie jest zrównoważone, można je zrównoważyć samodzielnie po wprowadzeniu pewnych zmian. Te zmiany układu można wykonać za pomocą pewnych obrotów.
Przyjrzyjmy się samorównoważeniu na przykładzie.
Załóżmy, że chcemy wstawić 10, 20, 30 w drzewie AVL.
Poniżej przedstawiono sposoby wstawiania liczb 10, 20, 30 do drzewa AVL:
Krok 1: Najpierw tworzymy drzewo wyszukiwania binarnego, jak pokazano poniżej:
Krok 2: Na powyższym rysunku możemy zaobserwować, że drzewo jest niezrównoważone, ponieważ współczynnik równowagi węzła 30 wynosi 2. Aby było to drzewo AVL, musimy wykonać pewne rotacje. Jeżeli wykonamy odpowiedni obrót w węźle 20 to węzeł 30 przesunie się w dół, natomiast węzeł 20 w górę, jak pokazano poniżej:
Jak możemy zaobserwować, ostatnie drzewo jest zgodne z właściwością drzewa wyszukiwania binarnego i drzewa zrównoważonego; dlatego jest to drzewo AVL.
indeks javy
W tym przypadku było to drzewo pozostawione niezrównoważone drzewo, więc wykonujemy odpowiedni obrót w węźle.
Krok 1: Najpierw tworzymy drzewo wyszukiwania binarnego, jak pokazano poniżej:
Krok 2: Na powyższym rysunku możemy zaobserwować, że drzewo jest niezrównoważone, ponieważ współczynnik równowagi węzła 10 wynosi -2. Aby było to drzewo AVL, musimy wykonać pewne rotacje. Jest to drzewo niezrównoważone w prawo, dlatego wykonamy obrót w lewo. Jeśli wykonamy obrót w lewo na węźle 20, to węzeł 20 przesunie się w górę, a węzeł 10 w dół, jak pokazano poniżej:
Jak możemy zaobserwować, ostatnie drzewo jest zgodne z właściwością Drzewo wyszukiwania binarnego i a zrównoważone drzewo ; dlatego jest to drzewo AVL.
Krok 1: Najpierw tworzymy drzewo wyszukiwania binarnego, jak pokazano poniżej:
Krok 2: Na powyższym rysunku możemy zaobserwować, że drzewo jest niezrównoważone, ponieważ współczynnik równowagi węzła głównego wynosi 2. Aby stało się drzewem AVL, musimy wykonać pewne rotacje. Powyższy scenariusz jest niezrównoważony lewo-prawo, ponieważ jeden węzeł znajduje się na lewo od węzła nadrzędnego, a drugi na prawo od węzła nadrzędnego. Najpierw wykonamy obrót w lewo, a rotacja nastąpi pomiędzy węzłami 10 i 20. Po obrocie w lewo 20 przesunie się w górę, a 10 w dół, jak pokazano poniżej:
Uruchom polecenie cmd w Linuksie
Mimo to drzewo jest niezrównoważone, dlatego wykonujemy odpowiedni obrót na drzewie. Po wykonaniu odpowiedniego obrotu na drzewie, drzewo będzie chciało, jak pokazano poniżej:
Jak możemy zaobserwować na powyższym drzewie, drzewo to ma właściwości drzewa wyszukiwania binarnego i drzewa zrównoważonego; dlatego jest to drzewo AVL.
Krok 1: Najpierw tworzymy drzewo wyszukiwania binarnego, jak pokazano poniżej:
Krok 2: Na powyższym rysunku możemy zaobserwować, że drzewo jest niezrównoważone, ponieważ współczynnik równowagi węzła głównego wynosi 2. Aby stało się drzewem AVL, musimy wykonać pewne rotacje. Powyższy scenariusz jest niezrównoważony pomiędzy prawą i lewą stroną, ponieważ jeden węzeł znajduje się na prawo od węzła nadrzędnego, a drugi węzeł na lewo od węzła nadrzędnego. Najpierw wykonamy prawy obrót, który ma miejsce pomiędzy węzłami 30 i 20. Po prawym obrocie 20 przesunie się w górę, a 30 przesunie się w dół, jak pokazano poniżej:
Mimo to powyższe drzewo jest niezrównoważone, dlatego musimy wykonać obrót w lewo na węźle. Po wykonaniu obrotu w lewo węzeł 20 przesunie się w górę, a węzeł 10 przesunie się w dół, jak pokazano poniżej:
Jak możemy zaobserwować na powyższym drzewie, drzewo to ma właściwości drzewa wyszukiwania binarnego i drzewa zrównoważonego; dlatego jest to drzewo AVL.
Różnice między drzewem wyszukiwania binarnego a drzewem AVL
| Drzewo wyszukiwania binarnego | Drzewo AVL |
|---|---|
| Każde drzewo wyszukiwania binarnego jest drzewem binarnym, ponieważ oba drzewa zawierają maksymalnie dwoje dzieci. | Każde drzewo AVL jest również drzewem binarnym, ponieważ drzewo AVL ma również największą dwójkę dzieci. |
| W BST nie ma takiego terminu, jak współczynnik równowagi. | W drzewie AVL każdy węzeł zawiera współczynnik równowagi, którego wartość musi wynosić -1, 0 lub 1. |
| Każde drzewo wyszukiwania binarnego nie jest drzewem AVL, ponieważ BST może być drzewem zrównoważonym lub niezrównoważonym. | Każde drzewo AVL jest drzewem wyszukiwania binarnego, ponieważ drzewo AVL jest zgodne z właściwością BST. |
| Każdy węzeł w drzewie wyszukiwania binarnego składa się z trzech pól, tj. lewego poddrzewa, wartości węzła i prawego poddrzewa. | Każdy węzeł drzewa AVL składa się z czterech pól, tj. lewego poddrzewa, wartości węzła, prawego poddrzewa i współczynnika równowagi. |
| W przypadku drzewa wyszukiwania binarnego, jeśli chcemy wstawić dowolny węzeł do drzewa, porównujemy wartość węzła z wartością korzenia; jeśli wartość węzła jest większa niż wartość węzła głównego, wówczas węzeł jest wstawiany do prawego poddrzewa, w przeciwnym razie węzeł jest wstawiany do lewego poddrzewa. Po wstawieniu węzła nie ma potrzeby sprawdzania współczynnika równowagi wysokości, aby wstawienie zostało zakończone. | W przypadku drzewa AVL najpierw znajdziemy odpowiednie miejsce na wstawienie węzła. Po wstawieniu węzła obliczymy współczynnik równowagi każdego węzła. Jeśli współczynnik równowagi każdego węzła jest spełniony, wstawianie jest zakończone. Jeśli współczynnik równowagi jest większy niż 1, to musimy wykonać pewne rotacje, aby zrównoważyć drzewo. |
| W drzewie wyszukiwania binarnego wysokość lub głębokość drzewa wynosi O(n), gdzie n to liczba węzłów w drzewie wyszukiwania binarnego. | W drzewie AVL wysokość lub głębokość drzewa wynosi O (logn). |
| Jest to proste do wdrożenia, ponieważ aby wstawić węzeł, musimy postępować zgodnie z właściwościami wyszukiwania binarnego. | Jest to skomplikowane w implementacji, ponieważ w drzewie AVL musimy najpierw skonstruować drzewo AVL, a następnie sprawdzić równowagę wysokości. Jeśli wysokość jest niezrównoważona, musimy wykonać kilka obrotów, aby zrównoważyć drzewo. |
| BST nie jest drzewem zrównoważonym, ponieważ nie jest zgodny z koncepcją współczynnika równowagi. | Drzewo AVL jest drzewem o zrównoważonej wysokości, ponieważ jest zgodne z koncepcją współczynnika równowagi. |
| Wyszukiwanie jest nieefektywne w BST, gdy w drzewie dostępna jest duża liczba węzłów, ponieważ wysokość nie jest zrównoważona. | Wyszukiwanie jest efektywne w drzewie AVL nawet wtedy, gdy w drzewie znajduje się duża liczba węzłów, ponieważ wysokość jest zrównoważona. |