drzewo AVL - AVL tree

Drzewo AVL
Drzewo AVL
Rodzaj	drzewo
Wynaleziony	1962
Wynalezione przez	Georgy Adelson-Velsky i Evgenii Landis
Złożoność czasowa w notacji duże O
Algorytm
Algorytm
Przestrzeń
Szukaj
Wstawić
Kasować

Animacja przedstawiająca wstawianie kilku elementów do drzewa AVL. Obejmuje obroty w lewo, w prawo, lewo-prawo i prawo-lewo.

Rys. 1: Drzewo AVL ze współczynnikami równowagi (zielony)

W informatyce , drzewo AVL (nazwany wynalazców A delson- V elsky i L Andis) jest samobalansujący binarne drzewo poszukiwań . Była to pierwsza taka struktura danych, jaka została wynaleziona. W drzewie AVL wysokości dwóch poddrzew potomnych dowolnego węzła różnią się najwyżej o jeden; jeśli w dowolnym momencie różnią się one o więcej niż jeden, dokonywane jest przywracanie równowagi w celu przywrócenia tej właściwości. Wyszukiwanie, wstawianie i usuwanie zajmuje czas $O (log n)$ zarówno w średnim, jak i najgorszym przypadku, gdzie jest liczbą węzłów w drzewie przed operacją. Wstawianie i usuwanie może wymagać ponownego zrównoważenia drzewa o jeden lub więcej rotacji drzewa . ${\ Displaystyle n}$

Nazwa drzewa AVL pochodzi od dwóch sowieckich wynalazców, Georgy Adelson-Velsky i Evgenii Landis , którzy opublikowali je w swoim artykule z 1962 roku „Algorytm organizacji informacji”.

Drzewa AVL są często porównywane z czerwono-czarnymi drzewami, ponieważ oba obsługują ten sam zestaw operacji i wymagają czasu na podstawowe operacje. W przypadku aplikacji intensywnie korzystających z wyszukiwań drzewa AVL są szybsze niż drzewa czerwono-czarne, ponieważ są bardziej zbalansowane. Podobnie jak czerwono-czarne drzewa, drzewa AVL są zrównoważone wysokością. Ogólnie rzecz biorąc, oba nie są ani wyważone, ani wyważone dla żadnego ; to znaczy węzły rodzeństwa mogą mieć bardzo różną liczbę potomków. ${\ Displaystyle {\ tekst {O}} (\ log n)}$ ${\ Displaystyle \ mu}$ $\mu \leq {\tfrac {1}{2}}$

Definicja

Współczynnik równowagi

W binarnym drzewie czynnikiem bilans węzła X jest zdefiniowana jako różnica wysokości

{\ Displaystyle {\ tekst {BF}} (X): = {\ tekst {wysokość}} ({\ tekst {prawe poddrzewo}} (X)) - {\ tekst {wysokość}} ({\ tekst {lewe poddrzewo}} (X))}

z jego dwóch poddrzew. Drzewo binarne jest zdefiniowane jako drzewo AVL, jeśli niezmiennik

{\ Displaystyle {\ tekst {BF}} (X) \ w {\ {-1,0, 1 \}}}

obowiązuje dla każdego węzła X w drzewie.

Węzeł X jest nazywany „lewo-ciężkim”, jeden z „prawo-ciężkim”, a jeden z jest czasami po prostu nazywany „zrównoważonym”. ${\ Displaystyle {\ tekst {BF}} (X) <0}$ ${\ Displaystyle {\ tekst {BF}} (X)> 0}$ ${\ Displaystyle {\ tekst {BF}} (X) = 0}$

Nieruchomości

Współczynniki równowagi można aktualizować, znając poprzednie współczynniki równowagi i zmianę wysokości – nie jest konieczna znajomość wzrostu bezwzględnego. Do przechowywania informacji o saldzie AVL w tradycyjny sposób wystarczą dwa bity na węzeł. Jednak późniejsze badania wykazały, że jeśli drzewo AVL jest zaimplementowane jako drzewo o zrównoważonych rangach, z dozwolonymi rangami delta wynoszącymi 1 lub 2 – co oznacza „podczas wznoszenia występuje dodatkowy przyrost wysokości o jeden lub dwa”, można to zrobić za pomocą jednego fragment.

Wysokość (liczona jako maksymalna liczba poziomów) drzewa AVL z węzłami leży w przedziale: ${\ Displaystyle h}$ ${\ Displaystyle n}$

{\ Displaystyle \ log _ {2} (n + 1) \ leq h < \ log _ {\ varphi} (n + 2) + b}

gdzie jest złotym podziałem a Dzieje się tak ponieważ drzewo AVL o wysokości zawiera co najmniej węzły gdzie jest ciąg Fibonacciego z wartościami ziarna ${\ Displaystyle \ varphi : = {\ tfrac {1 + {\ sqrt {5}}} {2}} \ około 1,618}$ ${\ Displaystyle b: = {\ Frac {\ log _ {2} 5} {2 \ log _ {2} \ varphi}} -2 \ około \; -0,3277.}$ ${\ Displaystyle h}$ ${\ Displaystyle F_ {h + 2} -1}$ ${\ Displaystyle \ {F_ {n} \} _ {n \ w \ mathbb {N}}}$ $F_{1}=F_{2}=1.$

Operacje

Operacje tylko do odczytu drzewa AVL obejmują wykonywanie tych samych czynności, które byłyby wykonywane na niezrównoważonym drzewie wyszukiwania binarnego , ale modyfikacje muszą obserwować i przywracać równowagę wysokości poddrzew.

Badawczy

Wyszukiwanie określonego klucza w drzewie AVL może odbywać się w taki sam sposób, jak w dowolnym zrównoważonym lub niezrównoważonym drzewie wyszukiwania binarnego . Aby wyszukiwanie działało skutecznie, musi korzystać z funkcji porównania, która ustala całkowitą kolejność (lub przynajmniej całkowitą preorder ) na zestawie kluczy. Liczba porównań wymaganych do udanego wyszukiwania jest ograniczona przez wysokość $h ,$ a do nieudanego wyszukiwania jest bardzo zbliżona do $h$ , więc oba są w $O(log n)$ .

Przemierzanie

Jako operacja tylko do odczytu, przechodzenie przez drzewo AVL działa tak samo, jak w każdym innym drzewie binarnym. Eksploracja wszystkich $n$ węzłów drzewa odwiedza każdy link dokładnie dwa razy: jedna wizyta w dół, aby wejść do poddrzewa zakorzenionego w tym węźle, druga wizyta w górę, aby opuścić poddrzewo tego węzła po jego zbadaniu.

Po znalezieniu węzła w drzewie AVL można uzyskać dostęp do następnego lub poprzedniego węzła w zamortyzowanym stałym czasie. Niektóre przypadki eksploracji tych "pobliskich" węzłów wymagają przechodzenia do łączy $h \propto log(n)$ (szczególnie podczas nawigowania od prawego liścia lewego poddrzewa korzenia do korzenia lub od korzenia do skrajnego lewego liścia prawego poddrzewa korzenia; w drzewie AVL na rysunku 1, nawigacja od węzła P do następnego po prawej stronie węzła Q zajmuje 3 kroki). Ponieważ w każdym drzewie jest $n -1$ połączeń, zamortyzowany koszt wynosi $2\times(n -1)/ n$ , czyli około 2.

Wstawić

Podczas wstawiania węzła do drzewa AVL, początkowo wykonujesz ten sam proces, co wstawianie do drzewa wyszukiwania binarnego . Jeśli drzewo jest puste, węzeł jest wstawiany jako korzeń drzewa. W przypadku, gdy drzewo nie było puste, idziemy w dół korzenia i rekursywnie schodzimy w dół drzewa, szukając miejsca do wstawienia nowego węzła. To przechodzenie jest sterowane przez funkcję porównania. W tym przypadku węzeł zawsze zastępuje odwołanie NULL (lewe lub prawe) zewnętrznego węzła w drzewie, tj. węzeł jest albo lewy, albo prawy-dziecko zewnętrznego węzła.

Po tym wstawieniu, jeśli drzewo staje się niezrównoważone, tylko przodkowie nowo wstawionego węzła są niezrównoważeni. Dzieje się tak, ponieważ tylko te węzły mają zmienione poddrzewa. Dlatego konieczne jest sprawdzenie, czy każdy z przodków węzła jest zgodny ze niezmiennikami drzew AVL: nazywa się to „retracingiem”. Osiąga się to poprzez rozważenie współczynnika równowagi każdego węzła.

Ponieważ przy pojedynczym wstawieniu wysokość poddrzewa AVL nie może wzrosnąć o więcej niż jeden, tymczasowy współczynnik równowagi węzła po wstawieniu będzie mieścił się w zakresie [–2,+2]. Dla każdego sprawdzonego węzła, jeśli tymczasowy współczynnik równowagi pozostaje w zakresie od –1 do +1, to tylko aktualizacja współczynnika równowagi i nie jest konieczna rotacja. Jeśli jednak tymczasowy współczynnik równowagi staje się mniejszy niż –1 lub większy niż +1, poddrzewo zakorzenione w tym węźle jest niezrównoważone AVL i konieczna jest rotacja. Przy wstawianiu, jak pokazuje poniższy kod, odpowiedni obrót natychmiast perfekcyjnie przywraca równowagę drzewa.

Na rysunku 1, wstawiając nowy węzeł Z jako dziecko węzła X, wysokość tego poddrzewa Z wzrasta od 0 do 1.

Niezmiennicza pętli retracingu dla wstawienia

Wysokość poddrzewa zakorzenionego przez Z wzrosła o 1. Jest już w kształcie AVL.

Przykładowy kod operacji wstawiania

for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
    // BF(X) has to be updated:
    if (Z == right_child(X)) { // The right subtree increases
        if (BF(X) > 0) { // X is right-heavy
            // ==> the temporary BF(X) == +2
            // ==> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BF(Z) < 0)                  // Right Left Case  (see figure 3)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                            // Right Right Case (see figure 2)
                N = rotate_Left(X, Z);      // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) < 0) {
                BF(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BF(X) = +1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    } else { // Z == left_child(X): the left subtree increases
        if (BF(X) < 0) { // X is left-heavy
            // ==> the temporary BF(X) == -2
            // ==> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BF(Z) > 0)                  // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                            // Left Left Case
                N = rotate_Right(X, Z);     // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) > 0) {
                BF(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BF(X) = -1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    // Height does not change: Height(N) == old Height(X)
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
    } else
        tree->root = N; // N is the new root of the total tree
    break;
    // There is no fall thru, only break; or continue;
}
// Unless loop is left via break, the height of the total tree increases by 1.

Aby zaktualizować współczynniki równowagi wszystkich węzłów, najpierw zauważ, że wszystkie węzły wymagające korekty leżą od dziecka do rodzica wzdłuż ścieżki wstawionego liścia. Jeśli powyższa procedura zostanie zastosowana do węzłów na tej ścieżce, zaczynając od liścia, to każdy węzeł w drzewie ponownie będzie miał współczynnik równowagi równy -1, 0 lub 1.

Cofanie może się zatrzymać, jeśli współczynnik równowagi osiągnie 0, co oznacza, że wysokość tego poddrzewa pozostaje niezmieniona.

Jeśli współczynnik równowagi wynosi ±1, to wysokość poddrzewa wzrasta o jeden i trzeba kontynuować wycofywanie.

Jeśli współczynnik równowagi chwilowo wynosi ±2, należy to naprawić przez odpowiedni obrót, po którym poddrzewo ma taką samą wysokość jak poprzednio (i jego pierwiastek współczynnik równowagi 0).

Wymagany czas to $O(log n)$ do wyszukania plus maksymalnie $O(log n)$ poziomy odtworzenia ( średnio $O(1)$ ) w drodze powrotnej do katalogu głównego, więc operacja może zostać zakończona w $O(log n)$ czas.

Kasować

Wstępne kroki usuwania węzła zostały opisane w rozdziale Drzewo wyszukiwania binarnego#Deletion . Tam skuteczne usunięcie węzła przedmiotowego lub węzła zastępczego zmniejsza wysokość odpowiedniego drzewa potomnego z 1 do 0 lub z 2 do 1, jeśli ten węzeł ma dziecko.

Zaczynając od tego poddrzewa, konieczne jest sprawdzenie każdego przodka pod kątem zgodności z niezmiennikami drzew AVL. Nazywa się to „cofaniem”.

Ponieważ przy pojedynczym usunięciu wysokość poddrzewa AVL nie może zmniejszyć się o więcej niż jeden, tymczasowy współczynnik równowagi węzła będzie mieścił się w zakresie od -2 do +2. Jeśli współczynnik równowagi pozostaje w zakresie od -1 do +1, można go dostosować zgodnie z zasadami AVL. Jeśli wynosi ±2, oznacza to, że poddrzewo jest niezrównoważone i należy je obrócić. (W przeciwieństwie do wstawiania, w którym obrót zawsze równoważy drzewo, po usunięciu może wystąpić BF(Z) ≠ 0 (patrz rysunki 2 i 3), tak że po odpowiednim pojedynczym lub podwójnym obrocie wysokość zrównoważonego poddrzewa zmniejsza się o jedno znaczenie że drzewo musi zostać ponownie zbalansowane na następnym wyższym poziomie.) Różne przypadki rotacji są opisane w sekcji Ponowne równoważenie .

Niezmiennicza pętli powrotu do usunięcia

Wysokość poddrzewa zakorzenionego przez N zmniejszyła się o 1. Jest już w kształcie AVL.

Przykładowy kod operacji usuwania

for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root)
    G = parent(X); // Save parent of X around rotations
    // BF(X) has not yet been updated!
    if (N == left_child(X)) { // the left subtree decreases
        if (BF(X) > 0) { // X is right-heavy
            // ==> the temporary BF(X) == +2
            // ==> rebalancing is required.
            Z = right_child(X); // Sibling of N (higher by 2)
            b = BF(Z);
            if (b < 0)                      // Right Left Case  (see figure 3)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                            // Right Right Case (see figure 2)
                N = rotate_Left(X, Z);      // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) == 0) {
                BF(X) = +1; // N’s height decrease is absorbed at X.
                break; // Leave the loop
            }
            N = X;
            BF(N) = 0; // Height(N) decreases by 1
            continue;
        }
    } else { // (N == right_child(X)): The right subtree decreases
        if (BF(X) < 0) { // X is left-heavy
            // ==> the temporary BF(X) == -2
            // ==> rebalancing is required.
            Z = left_child(X); // Sibling of N (higher by 2)
            b = BF(Z);
            if (b > 0)                      // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                            // Left Left Case
                N = rotate_Right(X, Z);     // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) == 0) {
                BF(X) = -1; // N’s height decrease is absorbed at X.
                break; // Leave the loop
            }
            N = X;
            BF(N) = 0; // Height(N) decreases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
    } else
        tree->root = N; // N is the new root of the total tree
 
    if (b == 0)
        break; // Height does not change: Leave the loop
 
    // Height(N) decreases by 1 (== old Height(X)-1)
}
// If (b != 0) the height of the total tree decreases by 1.

Cofanie może się zatrzymać, jeśli współczynnik równowagi osiągnie ±1 (musiało wynosić 0), co oznacza, że wysokość tego poddrzewa pozostaje niezmieniona.

Jeśli współczynnik równowagi wynosi 0 (musiał wynosić ±1), wówczas wysokość poddrzewa zmniejsza się o jeden, a cofanie musi być kontynuowane.

Jeśli współczynnik równowagi chwilowo osiągnie ±2, należy to naprawić przez odpowiedni obrót. Od współczynnika równowagi rodzeństwa Z (wyższe drzewo potomne na ryc. 2) zależy, czy wysokość poddrzewa zmniejszy się o jeden – a wycofywanie musi być kontynuowane – czy też nie zmieni się (jeśli Z ma współczynnik równowagi 0) i całe drzewo ma kształt AVL.

Wymagany czas to $O(log n)$ do wyszukania plus maksymalnie $O(log n)$ poziomy odtworzenia ( średnio $O(1)$ ) w drodze powrotnej do katalogu głównego, więc operacja może zostać zakończona w $O(log n)$ czas.

Ustaw operacje i operacje zbiorcze

Oprócz jednoelementowych operacji wstawiania, usuwania i wyszukiwania, kilka operacji na zestawach zostało zdefiniowanych na drzewach AVL: suma , przecięcie i różnica zestawu . Następnie można zaimplementować szybkie operacje zbiorcze na wstawianiu lub usuwaniu w oparciu o te ustawione funkcje. Te operacje na zestawach opierają się na dwóch operacjach pomocnika, Split i Join . Dzięki nowym operacjom wdrażanie drzew AVL może być bardziej wydajne i wysoce równoległe.

Funkcja Join na dwóch drzewach AVL $t 1$ i $t 2$ oraz klucz $k$ zwróci drzewo zawierające wszystkie elementy z $t 1$ , $t 2$ oraz $k$ . Wymaga, aby $k$ było większe niż wszystkie klucze w $t 1$ i mniejsze niż wszystkie klucze w $t 2$ . Jeśli dwa drzewa różnią się wysokością najwyżej o jeden, Join po prostu tworzy nowy węzeł z lewym poddrzewem $t 1$ , korzeniem $k$ i prawym poddrzewem $t 2$ . W przeciwnym razie załóżmy, że $t 1$ jest większe niż $t 2$ dla więcej niż jednego (drugi przypadek jest symetryczny). Join podąża za prawym grzbietem $t 1$ aż do węzła $c,$ który jest zrównoważony przez $t 2$ . W tym momencie tworzony jest nowy węzeł z lewym dzieckiem $c$ , korzeniem $k$ i prawym dzieckiem $t 2 w$ celu zastąpienia c. Nowy węzeł spełnia niezmiennik AVL, a jego wysokość jest o jeden większa niż $c$ . Wzrost wzrostu może zwiększyć wzrost jego przodków, prawdopodobnie unieważniając niezmiennik AVL tych węzłów. Można to naprawić albo za pomocą podwójnej rotacji, jeśli jest to niepoprawne u rodzica, albo pojedynczego obrotu w lewo, jeśli jest to nieprawidłowe wyżej w drzewie, w obu przypadkach przywracając wysokość dla wszelkich dalszych węzłów przodków. Połączenie będzie zatem wymagało co najwyżej dwóch obrotów. Kosztem tej funkcji jest różnica wysokości pomiędzy dwoma drzewami wejściowymi.

Implementacja pseudokodu dla algorytmu Join

function JoinRightAVL(T_L, k, T_R)
    (l,k',c) = expose(T_L)
    if (Height(c) <= Height(T_R)+1)
       T'=Node(c,k,T_R)
       if (Height(T') <= Height(l)+1) then return Node(l,k',T')
       else return rotateLeft(Node(l,k'rotateRight(T')))
    else 
        T' = JoinRightAVL(c,k,T_R)
        T = Node(l,k',T')
        if (Height(T') <= Height(l)+1) return T
        else return rotateLeft(T)

function JoinLeftAVL(T_L, k, T_R)
  /* symmetric to JoinRightAVL */

function Join(T_L, k, T_R)
    if (Height(T_L)>Height(T_R)+1) return JoinRightAVL(T_L, k, T_R)
    if (Height(T_R)>Height(T_L)+1) return JoinLeftAVL(T_L, k, T_R)
    return Node(T_L,k,T_R)

Tutaj Height(v) jest wysokością poddrzewa (węzła) $v$ . (l, K, R) = odsłonić (v) ekstrakty $v$ 'pozostało dzieci $l$ , klucz $K$ w $V$ ' korzenia i odpowiedni dla dzieci $R$ . Node(l,k,r) oznacza utworzenie węzła lewego dziecka $l$ , klucza $k$ i prawego dziecka $r$ .

Aby podzielić drzewo AVL na dwa mniejsze drzewa, mniejsze niż klucz $k$ i większe niż klucz $k$ , najpierw narysuj ścieżkę od korzenia, wstawiając $k$ do AVL. Po tym wstawieniu wszystkie wartości mniejsze niż $k$ zostaną znalezione po lewej stronie ścieżki, a wszystkie wartości większe niż $k$ zostaną znalezione po prawej stronie. Stosując Join , wszystkie poddrzewa po lewej stronie są scalane od dołu do góry za pomocą klawiszy na ścieżce jako węzłów pośrednich od dołu do góry, tworząc lewe drzewo, a prawa część jest asymetryczna. Koszt Splitu to $O(log n)$ , rząd wysokości drzewa.

Implementacja pseudokodu dla algorytmu Split

function Split(T,k)
    if (T = nil) return (nil,false,nil)
    (L,m,R) = expose(T)
    if (k = m) return (L,true,R)
    if (k<m) 
       (L',b,R') = split(L,k)
       return (L',b,join(R',m,R))
    if (k>m) 
       (L',b,R') = split(R,k)
       return (join(L,m,L'),b,R'))

Połączenie dwóch drzew AVL $t 1$ i $t 2$ reprezentujących zbiory $A$ i $B$ , jest AVL $t$ reprezentującym $A \cup B$ .

Implementacja pseudokodu dla algorytmu unijnego

function Union(t₁, t₂):
    if t₁ = nil:
        return t₂
    if t₂ = nil:
        return t₁
    t_<, t_> ← split t₂ on t₁.root
    return join(t₁.root,union(left(t₁), t_<),union(right(t₁), t_>))

Tutaj zakłada się, że Split zwraca dwa drzewa: jedno trzymające klawisze bez klucza wejściowego, drugie trzymające większe klawisze. (Algorytm nie jest destrukcyjny , ale istnieje również wersja destrukcyjna w miejscu).

Algorytm przecięcia lub różnicy jest podobny, ale wymaga procedury pomocniczej Join2, która jest taka sama jak Join, ale bez środkowego klucza. W oparciu o nowe funkcje łączenia, przecięcia lub różnicy, jeden lub wiele kluczy można wstawić lub usunąć z drzewa AVL. Ponieważ Split wywołuje Join, ale nie zajmuje się bezpośrednio kryteriami równoważenia drzew AVL, taka implementacja jest zwykle nazywana implementacją „opartą na łączeniu” .

Złożoność każdego połączenia, przecięcia i różnicy dotyczy drzew AVL o rozmiarach i . Co ważniejsze, ponieważ rekurencyjne wywołania sumy, przecięcia lub różnicy są od siebie niezależne, mogą być wykonywane równolegle z równoległą głębokością . Gdy implementacja oparta na łączeniu ma ten sam DAG obliczeniowy, co wstawianie i usuwanie pojedynczego elementu. ${\ Displaystyle {\ tekst {O}} \ lewo (m \ log \ lewo ({n \ ponad m} + 1 \ po prawej) \ po prawej)}$ ${\ Displaystyle m}$ $n\;(\geq m)$ ${\ Displaystyle {\ tekst {O}} (\ log m \ log n)}$ ${\ Displaystyle m = 1}$

Równoważenie

Jeżeli podczas operacji modyfikacji zmieni się różnica wysokości między dwoma poddrzewami potomnymi, może to być odzwierciedlone przez adaptację informacji o równowadze u rodzica, o ile wynosi < 2. Podczas operacji wstawiania i usuwania może powstać (tymczasowa) różnica wysokości wynosząca 2, co oznacza, że nadrzędne poddrzewo musi zostać „zrównoważone”. Podane narzędzia naprawcze są tak zwanymi rotacjami drzewa , ponieważ przesuwają klucze tylko "w pionie", dzięki czemu ("pozioma") sekwencja klawiszy jest w pełni zachowana (co jest niezbędne dla drzewa wyszukiwania binarnego ).

Niech X będzie węzłem, który ma (tymczasowy) współczynnik równowagi równy -2 lub +2. Zmodyfikowano jego lewe lub prawe poddrzewo. Niech Z będzie wyższym dzieckiem (patrz rysunki 2 i 3). Zauważ, że oboje dzieci są w kształcie AVL przez hipotezę indukcyjną .

W przypadku wstawienia to wstawienie przydarzyło się jednemu z dzieci Z w taki sposób, że wzrost Z wzrósł. W przypadku usunięcia to kasowanie się do rodzeństwa t ₁ o Z w taki sposób, że T ₁ jest wysokością jest już niższe zmniejszyła się. (Jest to jedyny przypadek, w którym współczynnik równowagi Z może również wynosić 0.)

Istnieją cztery możliwe warianty naruszenia:

Prawo Prawo	==> Z to prawo	dziecko rodzica X i BF(Z) ≥ 0
Lewo lewo	==> Z to lewo	dziecko rodzica X i BF(Z) ≤ 0
Prawo lewo	==> Z to prawo	dziecko rodzica X i BF(Z) < 0
Lewo prawo	==> Z to lewo	dziecko rodzica X i BF(Z) > 0

A rebalansowanie odbywa się inaczej:

Prawo Prawo	==> X jest ponownie równoważony za pomocą a	prosty	obrót `rotate_Left`	(patrz rysunek 2)
Lewo lewo	==> X jest ponownie równoważony za pomocą a	prosty	obrót `rotate_Right`	(odbicie lustrzane rysunku 2)
Prawo lewo	==> X jest ponownie równoważony za pomocą a	podwójnie	obrót `rotate_RightLeft`	(patrz rysunek 3)
Lewo prawo	==> X jest ponownie równoważony za pomocą a	podwójnie	obrót `rotate_LeftRight`	(odbicie lustrzane rysunku 3)

Tym samym sytuacje są oznaczane jako CB , gdzie C (= kierunek dziecka) i B (= równowaga) pochodzą ze zbioru { Lewo , Prawo } z Prawem := − Lewo . Naruszenie równowagi w przypadku C == B jest naprawiane przez prosty obrót rotate_(− C ), podczas gdy przypadek C != B jest naprawiany przez podwójny obrót rotate_CB .

Koszt rotacji, prostej lub podwójnej, jest stały.

Prosta rotacja

Rysunek 2 przedstawia właściwą sytuację. W górnej połowie węzeł X ma dwa drzewa potomne o współczynniku równowagi równym +2 . Ponadto, wewnętrzna dziecko T ₂₃ z Z (czyli gdy Z lewej dziecka jest odpowiedni dla dzieci odpowiednio. Prawo dzieci, gdy Z jest w lewo dziecka) nie jest większa niż ich rodzeństwa t ₄ . Może to nastąpić poprzez zwiększenie wysokości poddrzewa t ₄ lub zmniejszenie wysokości poddrzewa t ₁ . W tym drugim przypadku może również wystąpić blada sytuacja, w której t ₂₃ ma taką samą wysokość jak t ₄ .

Wynik obrotu w lewo jest pokazany w dolnej połowie rysunku. Trzy linki (grube krawędzie na rysunku 2) i dwa współczynniki równowagi mają zostać zaktualizowane.

Jak widać na rysunku, przed wstawieniem warstwa liści znajdowała się na poziomie h+1, tymczasowo na poziomie h+2, a po obrocie ponownie na poziomie h+1. W przypadku delecji warstwa liści znajdowała się na poziomie h+2, gdzie jest ponownie, gdy t ₂₃ i t ₄ były tej samej wysokości. W przeciwnym razie warstwa liści osiągnie poziom h+1, tak że wysokość obróconego drzewa maleje.

Rys. 2: Prosty obrót
obrót_w lewo ( X , Z )

Fragment kodu prostego obrotu w lewo

Wejście:	X = korzeń poddrzewa do obrócenia w lewo
	Z = prawe dziecko X, Z jest prawe-ciężkie
	z wysokością == $Wysokość(LewePoddrzewo($ X $))+2$
Wynik:	nowy korzeń zbalansowanego poddrzewa

node *rotate_Left(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    t23 = left_child(Z); // Inner child of Z
    right_child(X) = t23;
    if (t23 != null)
        parent(t23) = X;
    left_child(Z) = X;
    parent(X) = Z;
    // 1st case, BF(Z) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Z) == 0) { // t23 has been of same height as t4
        BF(X) = +1;   // t23 now higher
        BF(Z) = –1;   // t4 now lower than X
    } else
    { // 2nd case happens with insertion or deletion:
        BF(X) = 0;
        BF(Z) = 0;
    }
    return Z; // return new root of rotated subtree
}

Podwójna rotacja

Rysunek 3 przedstawia sytuację z prawej i lewej strony. W górnej trzeciej części węzeł X ma dwa drzewa potomne o współczynniku równowagi równym +2 . Ale w przeciwieństwie do figury 2, wewnętrzne dziecko Y z Z jest wyższe niż jego rodzeństwo t ₄ . Może się to zdarzyć przez wstawienie samego Y lub zwiększenie wysokości jednego z jego poddrzew t ₂ lub t ₃ (w konsekwencji, że mają one różną wysokość) lub zmniejszenie wysokości poddrzewa t ₁ . W tym drugim przypadku, może on również wystąpić, że T ₂ i T ₃ są na tej samej wysokości.

Wynik pierwszego, prawego obrotu pokazano w środkowej trzeciej części rysunku. (W odniesieniu do współczynników równowagi, ten obrót nie jest tego samego rodzaju, co inne pojedyncze obroty AVL, ponieważ różnica wysokości między Y i t ₄ wynosi tylko 1.) Wynik ostatniego obrotu w lewo jest pokazany w dolnej trzeciej części figury. Zaktualizowanych ma zostać pięć ogniw (grube krawędzie na rysunku 3) i trzy współczynniki równowagi.

Jak widać na rysunku, przed wstawieniem warstwa liści znajdowała się na poziomie h+1, przejściowo na poziomie h+2, a po dwukrotnym obrocie ponownie na poziomie h+1. W przypadku usunięcia warstwa liści znajdowała się na poziomie h+2, a po dwukrotnej rotacji jest na poziomie h+1, tak że wysokość obróconego drzewa maleje.

Rys. 3: Podwójny obrót rotate_RightLeft ( X , Z )
= rotate_Right wokół Z , a następnie
rotate_Left wokół X

Fragment kodu podwójnego obrotu prawo-lewo

Wejście:	X = korzeń poddrzewa do obrócenia
	Z = jego prawe dziecko, lewe-ciężkie
	z wysokością == $Wysokość(LewePoddrzewo($ X $))+2$
Wynik:	nowy korzeń zbalansowanego poddrzewa

node *rotate_RightLeft(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    Y = left_child(Z); // Inner child of Z
    // Y is by 1 higher than sibling
    t3 = right_child(Y);
    left_child(Z) = t3;
    if (t3 != null)
        parent(t3) = Z;
    right_child(Y) = Z;
    parent(Z) = Y;
    t2 = left_child(Y);
    right_child(X) = t2;
    if (t2 != null)
        parent(t2) = X;
    left_child(Y) = X;
    parent(X) = Y;
    // 1st case, BF(Y) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Y) == 0) {
        BF(X) = 0;
        BF(Z) = 0;
    } else
    // other cases happen with insertion or deletion:
        if (BF(Y) > 0) { // t3 was higher
            BF(X) = –1;  // t1 now higher
            BF(Z) = 0;
        } else {
            // t2 was higher
            BF(X) = 0;
            BF(Z) = +1;  // t4 now higher
        }
    BF(Y) = 0;
    return Y; // return new root of rotated subtree
}

Porównanie z innymi konstrukcjami

Zarówno drzewa AVL, jak i czerwono-czarne (RB) są samobilansującymi się binarnymi drzewami poszukiwań i są powiązane matematycznie. Rzeczywiście, każde drzewo AVL może mieć kolor czerwono-czarny, ale istnieją drzewa RB, które nie są zrównoważone AVL. Do utrzymania AVL ewent. Istotną rolę odgrywają niezmienniki drzewa RB, rotacje. W najgorszym przypadku, nawet bez rotacji, wstawienia lub usunięcia AVL lub RB wymagają inspekcji $O (log n)$ i/lub aktualizacji współczynników równowagi AVL lub odpowiednio. Kolory RB. Insercje i delecje RB oraz insercje AVL wymagają od zera do trzech rekurencyjnych rotacji ogona i przebiegają w zamortyzowanym czasie $O(1)$ , a zatem średnio równie stałe. Delecje AVL wymagające rotacji $O(log n)$ w najgorszym przypadku są również średnio $O(1)$ . Drzewa RB wymagają przechowywania jednego bitu informacji (koloru) w każdym węźle, podczas gdy drzewa AVL najczęściej używają dwóch bitów dla współczynnika równowagi, chociaż, gdy są przechowywane u dzieci, wystarczy jeden bit o znaczeniu «niższy niż rodzeństwo». Większą różnicą między tymi dwiema strukturami danych jest ich limit wysokości.

Dla drzewa o wielkości $n \geq 1$

wysokość drzewa AVL wynosi co najwyżej
${\ Displaystyle {\ zacząć {tablica} {ll} h & \ leqq \; c \ log _ {2} (n + d) + b \ \ & < \; c \ log _ {2} (n + 2) + b\end{tablica}}}$

gdzie Golden Ratio , i .

{\ Displaystyle \ varphi : = {\ tfrac {1 + {\ sqrt {5}}} {2}} \ około 1,618}

{\ Displaystyle c: = {\ tfrac {1} {\ log _ {2} \ varphi}} \ około 1.440,}

{\ Displaystyle b: = {\ tfrac {c} {2}} \ log _ {2} 5-2 \ około \; -0,328,}

{\ Displaystyle d: = 1 + {\ tfrac {1} {\ varphi ^ {4} {\ sqrt {5}}}} \ około 1,065}

wysokość drzewa RB wynosi co najwyżej
${\ Displaystyle {\ zacząć {tablica} {ll} h & \ leqq \; 2 \ log _ {2} (n + 1) \ koniec {tablica}}}$ .

Drzewa AVL są sztywniej zrównoważone niż drzewa RB o asymptotycznej relacji AVL/RB 0,720 wysokości maksymalnych. W przypadku insercji i delecji Ben Pfaff wykazuje w 79 pomiarach związek AVL/RB między 0,677 a 1,077 z medianą ≈0,947 i średnią geometryczną ≈0,910.

Zobacz też

Bibliografia

^ ^a ^b ^c ^d ^e ^f Eric Alexander. "Drzewa AVL" . Zarchiwizowane od oryginału 31 lipca 2019 r.CS1 maint: nieodpowiedni adres URL ( link )
^ Sedgewick, Robert (1983). "Drzewa Zrównoważone" . Algorytmy . Addisona-Wesleya. P. 199 . Numer ISBN 0-201-06672-6.
^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). „Algorytm organizacji informacji”. Materiały Akademii Nauk ZSRR (w języku rosyjskim). 146 : 263-266. Tłumaczenie na język angielski Myron J. Ricci in Soviet Mathematics - Doklady , 3:1259-1263, 1962.
^ ^B Pfaff, Ben (czerwiec 2004). „Analiza wydajności BST w oprogramowaniu systemowym” (PDF) . Uniwersytet Stanforda .
^ Drzewa AVL nie są wyważone? (co oznacza: drzewa AVL nie są zbalansowane μ?)
Tym samym: Drzewo binarne nazywa się-balanced, z, jeśli dla każdego węzła, nierówność ${\ Displaystyle \ mu}$ ${\ Displaystyle 0 \ leq \ mu \ leq {\ tfrac {1} {2}}}$ ${\ Displaystyle N}$
${\ Displaystyle {\ tfrac {1} {2}} - \ mu \ leq {\ tfrac {| N_ {l} |} {| N | +1}} \ leq {\ tfrac {1} {2}} + \mu}$
trzyma i jest minimalny w przypadku tej właściwości. jest liczbą węzłów poniżej drzewa z korzeniem (w tym korzeniem) i jest lewym węzłem podrzędnym . ${\ Displaystyle \ mu}$ $|N|$ ${\ Displaystyle N}$ ${\ Displaystyle N_ {l}}$ ${\ Displaystyle N}$
^ ^a ^b ^c ^d Knuth, Donald E. (2000). Sortowanie i wyszukiwanie (wyd. 2, wyd. 6., na nowo aktualizowane i wyd. rew.). Boston [ua]: Addison-Wesley. Numer ISBN 0-201-89685-0.
^ Rajinikanth. "Drzewo AVL: Struktury danych" . btechsmartclass.com . Pobrano 2018-03-09 .
^ Dixit, JB (2010). Opanowanie struktur danych za pomocą języka „C” . New Delhi, Indie: University Science Press, wydawnictwo Laxmi Publications Pvt. Ltd. ISBN 9789380386720. OCLC 939446542 .
^ ^B ^c mosiądz, Peter (2008). Zaawansowane struktury danych . Cambridge: Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 9780511438202. OCLC 312435417 .
^ Hubbard, John Rast (2000). Zarys teorii Schauma i problemy struktur danych w Javie . Nowy Jork: McGraw-Hill. Numer ISBN 0071378707. OCLC 48139308 .
^ ^B ^c Pfaff, Ben (2004). Wprowadzenie do binarnych drzew wyszukiwania i zrównoważonych drzew . Fundacja Wolnego Oprogramowania, Inc.
^ Weiss, Mark Allen. (2006). Struktury danych i analiza algorytmów w C++ (wyd. 3). Boston: Pearson Addison-Wesley. P. 145. ISBN 0-321-37531-9. OCLC 61278554 .CS1 maint: data i rok ( link )
^ ^B Blelloch Guy E .; Ferizovic, Daniel; Sun, Yihan (2016), "Just join for równoległych uporządkowanych zestawów", Symposium on Parallel Algorithms and Architectures , ACM, s. 253-264, arXiv : 1602.02120 , doi : 10.1145/2935764.2935768 , ISBN 978-1-4503-4210-0, S2CID 2897793.
^ Paweł E. Czarny (13.04.2015). "Drzewo AVL" . Słownik algorytmów i struktur danych . Narodowy Instytut Norm i Technologii . Źródło 2016-07-02 .
^ Mehlhorn i Sanders 2008 , s. 165, 158
^ Dinesh P. Mehta, Sartaj Sahni (red.) Podręcznik struktur danych i aplikacji 10.4.2
^ Czerwono-czarne drzewo # Dowód asymptotycznych granic

Dalsza lektura

Donalda Knutha . The Art of Computer Programming , tom 3: Sortowanie i wyszukiwanie , wydanie trzecie. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Strony 458–475 rozdziału 6.2.3: Zrównoważone Drzewa.

Zewnętrzne linki

Ten artykuł zawiera materiał z domeny publicznej z dokumentu NIST : Black, Paul E. „AVL Tree” . Słownik algorytmów i struktur danych .

[wiscurl-1] ^ ^a ^b ^c ^d ^e ^f Eric Alexander. "Drzewa AVL" . Zarchiwizowane od oryginału 31 lipca 2019 r.CS1 maint: nieodpowiedni adres URL ( link )

[2] Sedgewick, Robert (1983). "Drzewa Zrównoważone" . Algorytmy . Addisona-Wesleya. P. 199 . Numer ISBN 0-201-06672-6.

[3] Adelson-Velsky, Georgy; Landis, Evgenii (1962). „Algorytm organizacji informacji”. Materiały Akademii Nauk ZSRR (w języku rosyjskim). 146 : 263-266. Tłumaczenie na język angielski Myron J. Ricci in Soviet Mathematics - Doklady , 3:1259-1263, 1962.

[Pfaff1-4] B Pfaff, Ben (czerwiec 2004). „Analiza wydajności BST w oprogramowaniu systemowym” (PDF) . Uniwersytet Stanforda .

[5] Drzewa AVL nie są wyważone? (co oznacza: drzewa AVL nie są zbalansowane μ?)
Tym samym: Drzewo binarne nazywa się-balanced, z, jeśli dla każdego węzła, nierówność ${\ Displaystyle \ mu}$ ${\ Displaystyle 0 \ leq \ mu \ leq {\ tfrac {1} {2}}}$ ${\ Displaystyle N}$
${\ Displaystyle {\ tfrac {1} {2}} - \ mu \ leq {\ tfrac {| N_ {l} |} {| N | +1}} \ leq {\ tfrac {1} {2}} + \mu}$
trzyma i jest minimalny w przypadku tej właściwości. jest liczbą węzłów poniżej drzewa z korzeniem (w tym korzeniem) i jest lewym węzłem podrzędnym . ${\ Displaystyle \ mu}$ $|N|$ ${\ Displaystyle N}$ ${\ Displaystyle N_ {l}}$ ${\ Displaystyle N}$

[Knuth-6] Knuth, Donald E. (2000). Sortowanie i wyszukiwanie (wyd. 2, wyd. 6., na nowo aktualizowane i wyd. rew.). Boston [ua]: Addison-Wesley. Numer ISBN 0-201-89685-0.

[7] Rajinikanth. "Drzewo AVL: Struktury danych" . btechsmartclass.com . Pobrano 2018-03-09 .

[dixit-mastering-data-structures-8] Dixit, JB (2010). Opanowanie struktur danych za pomocą języka „C” . New Delhi, Indie: University Science Press, wydawnictwo Laxmi Publications Pvt. Ltd. ISBN 9789380386720. OCLC 939446542 .

[brass-advanced-data-structures-9] B ^c mosiądz, Peter (2008). Zaawansowane struktury danych . Cambridge: Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 9780511438202. OCLC 312435417 .

[hubbard-outline-theory-problems-10] Hubbard, John Rast (2000). Zarys teorii Schauma i problemy struktur danych w Javie . Nowy Jork: McGraw-Hill. Numer ISBN 0071378707. OCLC 48139308 .

[Pfaff-11] B ^c Pfaff, Ben (2004). Wprowadzenie do binarnych drzew wyszukiwania i zrównoważonych drzew . Fundacja Wolnego Oprogramowania, Inc.

[12] Weiss, Mark Allen. (2006). Struktury danych i analiza algorytmów w C++ (wyd. 3). Boston: Pearson Addison-Wesley. P. 145. ISBN 0-321-37531-9. OCLC 61278554 .CS1 maint: data i rok ( link )

[join-based-13] B Blelloch Guy E .; Ferizovic, Daniel; Sun, Yihan (2016), "Just join for równoległych uporządkowanych zestawów", Symposium on Parallel Algorithms and Architectures , ACM, s. 253-264, arXiv : 1602.02120 , doi : 10.1145/2935764.2935768 , ISBN 978-1-4503-4210-0, S2CID 2897793.

[14] Paweł E. Czarny (13.04.2015). "Drzewo AVL" . Słownik algorytmów i struktur danych . Narodowy Instytut Norm i Technologii . Źródło 2016-07-02 .

[15] Mehlhorn i Sanders 2008 , s. 165, 158

[Dinesh-16] Dinesh P. Mehta, Sartaj Sahni (red.) Podręcznik struktur danych i aplikacji 10.4.2

[17] Czerwono-czarne drzewo # Dowód asymptotycznych granic

Languages

In other projects