Drzewa AVL

MP001 - drzewa poszukiwań binarnych - BST


Przedstawione w poprzednim rozdziale drzewa BST są bardzo wygodną strukturą do poszukiwań danych. Operacje wstawiana, usuwania oraz wyszukiwania posiadają dla drzew BST złożoność obliczeniową klasy O(log n), jeśli drzewo BST jest zrównoważone. Niestety, drzewa BST mogą degenerować się do list liniowych, co powoduje wzrost klasy złożoności obliczeniowej dla wymienionych operacji do O(n). Typowym przykładem jest utworzenie drzewa BST z kolejnych węzłów, których klucze tworzą ciąg rosnący lub malejący. Np. dla kluczy 1,2,3,4,5,6 otrzymamy następujące drzewo BST:

obrazek

W przedstawionej powyżej strukturze danych znikają zalety wyszukiwania binarnego. Klasa złożoności obliczeniowej operacji wyszukiwania degeneruje się z O(log n) do O(n).

Aby uniknąć tego rodzaju degeneracji, wymyślono wiele różnych odmian drzew BST. Jedną z prostszych są drzewa AVL (ang. AVL trees). Nazwa AVL pochodzi od dwóch nazwisk rosyjskich twórców tej struktury danych: Georgija Adelsona-Wielskiego (ros. Гео́ргий Макси́мович Адельсо́н-Ве́льский) oraz Jewgienija Michajłowicza Łandisa (ros. Евгений Михайлович Ландис).

Drzewo AVL jest drzewem poszukiwań binarnych BST, w którym poddrzewa każdego węzła różnią się wysokością (ilością poziomów) co najwyżej o 1.
Gwarantuje to zrównoważenie drzewa AVL.

Węzeł drzewa AVL jest wzbogacony o parametr bf zwany współczynnikiem równowagi (ang. balance factor):

bf(w) = hL(w) - hR(w)

gdzie w jest węzłem, a hR(w) i hL(w) są odpowiednio wysokościami prawego i lewego poddrzewa węzła w

Z powyższego wzoru oraz z definicji drzewa AVL wynika co następuje:

bf(w) =  1 → lewe poddrzewo jest cięższe o jeden poziom od prawego poddrzewa, hL(w) > hR(w)

bf (w)=  0 → oba poddrzewa są równej wysokości, hL(w) = hR(w)

bf(w) = -1 → prawe poddrzewo jest cięższe o jeden poziom od lewego poddrzewa, hL(w) < hR(w)

W drzewie AVL współczynnik bf nie może przyjmować innych wartości - ograniczenie to nosi nazwę własności drzewa AVL (ang. AVL tree property). Na poniższych rysunkach w węzłach drzewa BST umieściliśmy klucz oraz parametr bf rozdzielone dwukropkiem.

obrazek obrazek
Drzewo spełnia własność AVL Drzewo nie spełnia własności AVL

W języku C++ węzeł drzewa AVL możemy reprezentować poniższą strukturą:

struct AVLNode
{
  AVLNode * p, * left, * right;
  int key, bf;
};

Rotacja węzłów w drzewie AVL

Współczynniki równowagi bf w drzewie AVL mogą się zmienić tylko w przypadku, gdy zmianie ulega wysokość jakiegoś poddrzewa jednego z węzłów. Z kolei do sytuacji tej może dojść tylko przy wstawianiu nowego węzła (operacja insert) lub przy usuwaniu węzła (operacja delete). Pozostałe operacje (search, min, max, succ, pred, preorder, inorder i postorder) nie zmieniają wysokości poddrzew, zatem mogą one być identyczne jak w zwykłym drzewie BST.

Operacje insert oraz delete dla drzewa AVL składają się z dwóch faz - pierwsza faza jest identyczna jak w przypadku drzewa BST, druga faza ma za zadanie sprawdzić, czy pierwsza faza nie naruszyła własności AVL, a jeśli tak, to własność AVL musi być przywrócona.

Własność AVL przywracamy przy pomocy tzw. rotacji, czyli odpowiedniego przemieszczenia 3 węzłów. Istnieją 4 rodzaje rotacji - dwie pojedyncze oraz dwie podwójne:

Oznaczenia RR, LL, RL i LR określają sposób połączenia węzłów przed wykonaniem rotacji. Jeśli węzły łączą się prawymi krawędziami, mamy do czynienia z przypadkiem RR, jeśli tylko lewymi, to jest to przypadek LL. Mieszane połączenia są oznaczane jako LR i RL.

Rotacje wykonujemy, gdy natrafimy w drzewie AVL na węzeł o parametrze bf równym 2 lub -2. Taka wartość parametru bf świadczy o niezrównoważeniu węzła - jego poddrzewa różnią się wysokością o 2. Rotacja przywraca równowagę w węźle. Załóżmy, iż w wyniku wstawiania lub usuwania otrzymaliśmy następujący układ węzłów:

obrazek

Widzimy wyraźnie, iż węzeł 1 posiada niezrównoważone poddrzewa - lewe jest puste, a prawe ma wysokość 2. Stąd jego parametr bf przyjmuje wartość 2.  Dokonujemy rotacji RR węzłów 1, 2 i 3 w punkcie zaczepienia 1 i otrzymujemy równowagę:

obrazek

Węzeł 1 stał się prawym potomkiem węzła 2. Węzeł 2 zajął miejsce węzła 1. Rotacja zmniejszyła o 1 wysokość poddrzewa prawego i zwiększyła o 1 wysokość poddrzewa lewego. Skoro prawe było o dwa poziomy wyższe od lewego, to teraz się zrównały. I to jest właśnie cel wykonywania rotacji - zrównoważenie wysokości poddrzew, gdy różnią się one od siebie o więcej niż 1. Zwróć uwagę, iż rotacja nie zmienia własności drzewa BST ani kolejności przechodzenia inorder. Rotację LL wykonujemy analogicznie - jest ona lustrzanym odbiciem rotacji RR.

Problem pojawia się przy poniższej konfiguracji węzłów (RL):

obrazek

Takiego układu nie można po prostu obrócić RR, gdyż nastąpią konflikty pomiędzy niezaznaczonymi na rysunku dziećmi węzłów. Najpierw dokonujemy obrotu LL węzłów 2 i 3, a następnie obracamy RR węzły 1 i 2. Całość nosi nazwę obrotu podwójnego RL:

obrazek

Ponieważ pojedynczy obrót nie zmienia własności BST, również obrót podwójny nie zmienia jej, gdyż składa się on z dwóch obrotów pojedynczych.

Podamy teraz dokładne algorytmy wykonywania poszczególnych rotacji węzłów, które uwzględniają posiadanie przez węzły potomków. Węzeł biegunowy rotacji oznaczamy kolorem czerwonym.

Algorytm rotacji RR

obrazek

W rotacji uczestniczą węzły A i B. Węzeł B zajmuje miejsce węzła A, węzeł A staje się lewym dzieckiem węzła B. Lewe dziecko węzła B (BL) staje się prawym dzieckiem węzła A. Aby wyznaczyć współczynniki równowagi bf obu węzłów A i B po rotacji, rozważmy poniższe przypadki:

obrazek

Przypadek nr 1
bf(A) = - 2,   bf(B) = -1

Zaczynamy od węzła B. Ponieważ bf(B) = -1, to przeważa prawa gałąź BL. Wynika to bezpośrednio ze wzoru na współczynnik równowagi:

bf(B) = hBL - hBR,     bf(B) = -1,      hBL - hBR = -1,    hBR = hBL + 1

Oznaczmy wysokość lewego poddrzewa węzła B przez h, czyli hBL = h. Wtedy prawe poddrzewo węzła B będzie posiadało wysokość hBR = h + 1, o jeden większą od lewego poddrzewa.

Teraz obliczymy wysokość poddrzewa, którego korzeniem jest węzeł B. Wzór jest bardzo prosty - do wysokości najwyższego poddrzewa dodajemy jedynkę, czyli:

hB = 1 + max(hBL, hBR)

U nas najwyższe jest prawe poddrzewo, zatem:

hB = 1 + hBR = 1 + h + 1 = h + 2

Przechodzimy do węzła A. Ponieważ jego współczynnik równowagi wynosi -1, to wnioskujemy, iż przeważa o dwa poziomy prawe poddrzewo A:

bf(A) = hAL - hAR,    bf(A) = -2,    hAL - hAR = -2,    hAL = hAR - 2

Prawe poddrzewo węzła A jest poddrzewem, którego korzeń znajduje się w wierzchołku B. Stąd:

hAR = hB = h + 2

I ostatecznie otrzymujemy:

hAL = hAR - 2 = h + 2 - 2 = h

Wyznaczyliśmy względne wysokości wszystkich dzieci wierzchołków A i B dla rozważanego przypadku:

hAL = h
hBL = h
hBR = h + 1

Podkreślam, że nie interesują nas konkretne wartości h - to zależy już od konkretnego drzewa AVL. Mając wyznaczone względne wysokości poddrzew możemy wyliczyć współczynniki równowagi bf węzłów A i B po rotacji (patrz rysunek powyżej):

bf(A) = hAL - hBL = h - h = 0
bf(B) = hA - hBR = h + 1 - (h + 1) = 0

obrazek

Przypadek nr 2
bf(A) = - 2,   bf(B) = 0

Wykonując podobne operację (wykonaj je sam jako ćwiczenie) w przypadku drugim dochodzimy do wniosku, iż po rotacji węzły A i B otrzymają następujące współczynniki równowagi:

bf(A) = -1
bf(B) =  1

obrazek

Przypadek nr 3
bf(A) = - 2,   bf(B) = 1

W przypadku nr 3 otrzymujemy po rotacji:

bf(A) = -1
bf(B) =  2

Wynika z tego prosty wniosek - w takim układzie współczynników równowagi węzłów rotacja RR nie rozwiązuje problemu równowagi drzewa AVL. Nie będziemy zatem jej stosować dla przypadku nr 3!

Podsumujmy zatem:

Przed rotacją
bf(A) -2 -2
bf(B) -1 0
Po rotacji
bf(A) 0 -1
bf(B) 0 1

Algorytm

Wejście:

root  - korzeń drzewa BST
A  - węzeł, w którym występuje zaburzenie równowagi w prawym poddrzewie

Wyjście:

Węzeł drzewa, który zastąpił po rotacji węzeł A (prawe dziecko A).

Dane pomocnicze:

B  - prawe dziecko węzła A
P  - rodzic węzła A

Lista kroków

K01: B ← right(A)  
K02: P ← p(A)  
K03: rght(A) ← left(B) ; przenosimy lewe dziecko BL do prawego dziecka węzła A
K04: Jeśli right(A) ≠ NIL, to p(right(A)) ← A ; rodzicem BL jest teraz węzeł A
K05: left(B) ← A ; węzeł A staje się lewym dzieckiem węzła B
K06: p(B) ← P ; rodzic A staje się rodzicem B
K07: p(A) ← B ; rodzicem A staje się węzeł B
K08: Jeśli P ≠ NIL, idź do K10 ; czy węzeł B jest korzeniem drzewa AVL?
K09: root ← B i idź do K11 ; tak, ustaw nowy korzeń
K10: Jeśli left(P) = A, left(P) ← B
inaczej              right(P) ← B
; nie, zmieniamy dziecko rodzica z A na B
K11: Jeśli bf(B) = -1, to bf(A) ← 0;   bf(B) ← 0
inaczej                bf(A) ← -1;   bf(B) ← 1
; ustawiamy współczynniki równowagi
K12: Zwróć B i zakończ  

 

AVLNode * AVLrotationRR(AVLNode * &root, AVLNode * A)
{
  AVLNode * B = A->right, * P = A->p;

  A->right = B->left;
  if(A->right) A->right->p = A;
  B->left = A;
  B->p = P;
  A->p = B;
  if(P)
  {
    if(P->left == A) P->left = B; else P->right = B;
  }
  else root = B;

  if(B->bf == -1)
  {
    A->bf = B->bf = 0;
  }
  else
  {
    A->bf = -1; B->bf = 1;
  }
  return B;
}

Algorytm rotacji LL

obrazek

Rotacja LL jest lustrzanym odbiciem rotacji RR. W rotacji uczestniczą węzły A i B. Węzeł B zajmuje miejsce węzła A, węzeł A staje się prawym dzieckiem węzła B. Prawe dziecko węzła B (BR) staje się lewym dzieckiem węzła A. Współczynniki równowagi węzłów A i B po rotacji wyznaczamy w identyczny sposób, jak przy rotacji RR - można je również wywnioskować na podstawie własności symetrii tych rotacji. Proponuję wykonanie tych działań jako ćwiczenie samodzielne. My otrzymaliśmy następujące wyniki:

Przed rotacją
bf(A) 2 2
bf(B) 1 0
Po rotacji
bf(A) 0 1
bf(B) 0 -1

Wejście:

root  - korzeń drzewa BST
A  - węzeł, w którym występuje zaburzenie równowagi w lewym poddrzewie

Wyjście:

Węzeł drzewa, który zastąpił po rotacji węzeł A (lewe dziecko A).

Dane pomocnicze:

B  - lewe dziecko węzła A
P  - rodzic węzła A

Lista kroków

K01: B ← left(A)  
K02: P ← p(A)  
K03: left(A) ← right(B) ; przenosimy prawe dziecko BL do lewego dziecka węzła A
K04: Jeśli left(A) ≠ NIL, to p(left(A)) ← A ; rodzicem BR jest teraz węzeł A
K05: right(B) ← A ; węzeł A staje się prawym dzieckiem węzła B
K06: p(B) ← P ; rodzic A staje się rodzicem B
K07: p(A) ← B ; rodzicem A staje się węzeł B
K08: Jeśli P ≠ NIL, idź do K10 ; czy węzeł B jest korzeniem drzewa AVL?
K09: root ← B i idź do K11 ; tak, ustaw nowy korzeń
K10: Jeśli left(P) = A, left(P) ← B
inaczej              right(P) ← B
; nie, zmieniamy dziecko rodzica z A na B
K11: Jeśli bf(B) = 1, to bf(A) ← 0;   bf(B) ←  0
inaczej               bf(A) ← 1;   bf(B) ← -1
; ustawiamy współczynniki równowagi
K12: Zwróć B i zakończ  

 

AVLNode * AVLrotationLL(AVLNode * &root, AVLNode * A)
{
  AVLNode * B = A->left, * P = A->p;

  A->left = B->right;
  if(A->left) A->left->p = A;
  B->right = A;
  B->p = P;
  A->p = B;
  if(P)
  {
    if(P->left == A) P->left = B; else P->right = B;
  }
  else root = B;

  if(B->bf == 1)
  {
    A->bf = B->bf = 0;
  }
  else
  {
    A->bf = 1; B->bf = -1;
  }

  return B;
}

Algorytm rotacji RL

obrazek

Rotacja RL jest złożeniem rotacji RR i rotacji LL, dlatego nosi nazwę rotacji podwójnej. Pierwsza rotacja RR sprowadza gałąź drzewa do postaci dogodnej dla następnej rotacji LL. Zamiast jednak wykonywać kolejno rotację w prawo, a następnie w lewo, zaprojektujemy algorytm, który dokonuje tych obrotów jednocześnie. Węzeł C zastępuje węzeł A. Węzeł A staje się lewym dzieckiem węzła C i przejmuje on lewe dziecko C w miejsce swojego prawego dziecka. Węzeł B staje się prawym dzieckiem C i przejmuje on prawe dziecko C w miejsce swojego lewego dziecka. Określenie współczynników bf po rotacji wykonamy podobnie jak przy rotacjach pojedynczych - przeanalizujemy wysokości poddrzew przed i po rotacji podwójnej.

obrazek

Przypadek nr 1
bf(A) = - 2,   bf(B) = 1,   bf(C) = -1

Współczynniki bf węzłów A, B i C po rotacji wyznaczamy w podobny sposób, jak w przypadku rotacji RR. Rozpoczynamy od najniższego węzła C:

bf(C) = hCL - hCR,    bf(C) = -1,    hCR = hCL + 1

Zatem lżejsze jest poddrzewo lewe. Oznaczmy hCL = h.

hCR = h + 1
hC = h + 2

Teraz przechodzimy do wierzchołka B:

bf(B) = hBL - hBR,    bf(B) = 1,   hBR = hBL - 1 = hC - 1 = (h + 2) - 1 = h + 1
hB = h + 3

Na koniec pozostaje wierzchołek A:

bf(A) = hAL - hAR,    bf(A) = -2,    hAL = hAR - 2 = hB - 2 = (h + 3) - 2 = h + 1

Wyznaczyliśmy względne wysokości poddrzew wierzchołków A, B i C:

hAL = h + 1
hBR = h + 1
hCL = h
hCR = h + 1

Możemy zatem obliczyć współczynniki równowagi bf wierzchołków A, B i C po wykonaniu rotacji RL:

bf(A) = hAL - hCL = (h + 1) - h = 1
bf(C) = hCR - hBR = (h + 1) - (h + 1) = 0
bf(B) = hA - hC = (h + 2) - (h + 2) = 0

obrazek

Przypadek nr 2
bf(A) = - 2,   bf(B) = 1,   bf(C) = 0

W przypadku nr 2 nie trudno obliczyć wyżej podanym sposobem (zrób to jako ćwiczenie), iż po rotacji RL wierzchołki A, B i C przyjmą następujące współczynniki równowagi:

bf(A) = 0
bf(B) = 0
bf(C) = 0

obrazek

Przypadek nr 3
bf(A) = - 2,   bf(B) = 1,   bf(C) = 1

W przypadku nr 3 otrzymujemy:

bf(A) = 0
bf(B) = -1
bf(C) = 0

Podsumujmy otrzymane wyniki:

Przed rotacją RL
bf(A) -2 -2 -2
bf(B) 1 1 1
bf(C) -1 0 1
Po rotacji RL
bf(A) 1 0 0
bf(B) 0 0 -1
bf(C) 0 0 0

Z tabelki wynika, iż bf(C) jest zawsze zerowany, a pozostałe zależą od początkowej wartości bf(C).

Wejście:

root  - korzeń drzewa BST
A  - węzeł, w którym występuje zaburzenie równowag w prawym poddrzewie

Wyjście:

Węzeł drzewa, który zastąpił po rotacji węzeł A.

Dane pomocnicze:

B  - prawe dziecko węzła A
C  - lewe dziecko węzła B
P  - rodzic węzła A

Lista kroków

K01: B ← right(A)  
K02: C ← left(B)  
K03: P ← p(A)  
K04: left(B) ← right(C) ; prawy potomek CR staje się lewym potomkiem węzła B
K05: Jeśli left(B) ≠ NIL, to p(left(B)) ← B ; rodzicem CR jest teraz węzeł B
K06: right(A) ← left(C) ; lewy potomek CL staje się prawym potomkiem węzła A
K07: Jeśli right(A) ≠ NIL, to p(right(A)) ← A ; rodzicem CL jest teraz węzeł A
K08: left(C) ← A ; węzeł A robimy lewym potomkiem węzła C
K09: p(A) ← C ; węzeł C jest teraz rodzicem węzła A
K10: right(C) ← B ; prawym potomkiem C staje się węzeł B
K11: p(B) ← C ; a jego rodzicem jest węzeł C
K12: p(C) ← P ; rodzic A staje się rodzicem C
K13: Jeśli P ≠ NIL, idź do K15 ; czy węzeł C jest korzeniem drzewa AVL?
K14: root ← C i idź do K16 ; tak, ustaw nowy korzeń
K15: Jeśli left(P) = A, left(P) ← C
inaczej              right(P) ← C
; nie, zmieniamy dziecko rodzica z A na C
K16: Jeśli bf(C) = -1, to bf(A) ← 1
inaczej                 bf(A) ← 0
; ustawiamy nowe współczynniki równowagi
K17: Jeśli bf(C) = 1, bf(B) ← -1
inaczej            bf(B) ←  0
 
K18: bf(C) ← 0  
K19: Zwróć C i zakończ  

 

AVLNode * AVLrotationRL(AVLNode * &root, AVLNode * A)
{
  AVLNode * B = A->right, * C = B->left, * P = A->p;

  B->left = C->right;
  if(B->left) B->left->p = B;
  A->right = C->left;
  if(A->right) A->right->p = A;
  C->left = A;
  C->right = B;
  A->p = B->p = C;
  C->p = P;
  if(P)
  {
    if(P->left == A) P->left = C; else P->right = C;
  }
  else root = C;

  A->bf = (C->bf == -1) ?  1 : 0;
  B->bf = (C->bf ==  1) ? -1 : 0;
  C->bf = 0;

  return C;
}

Algorytm rotacji LR

obrazek

Podobnie jak w przypadku rotacji pojedynczych RR i LL, rotacja LR jest lustrzanym odbiciem rotacji RL. Węzeł C zastępuje węzeł A. Węzeł A staje się prawym dzieckiem węzła C i przejmuje on prawe dziecko CR w miejsce swojego lewego dziecka. Węzeł B staje się lewym dzieckiem C i przejmuje on lewe dziecko C w miejsce swojego prawego dziecka. Współczynniki równowagi zmieniają się następująco (proponuję ci sprawdzenie tych wyników):

Przed rotacją LR
bf(A) 2 2 2
bf(B) -1 -1 -1
bf(C) -1 0 1
Po rotacji LR
bf(A) 0 0 -1
bf(B) 1 0 0
bf(C) 0 0 0

Wejście:

root  - korzeń drzewa BST
A  - węzeł, w którym występuje zaburzenie równowag w lewym poddrzewie

Wyjście:

Węzeł drzewa, który zastąpił po rotacji węzeł A.

Dane pomocnicze:

B  - lewe dziecko węzła A
C  - prawe dziecko węzła B
P  - rodzic węzła A

Lista kroków

K01: B ← left(A)  
K02: C ← right(B)  
K03: P ← p(A)  
K04: right(B) ← left(C) ; lewy potomek CL staje się prawym potomkiem węzła B
K05: Jeśli right(B) ≠ NIL, to p(right(B)) ← B ; rodzicem CL jest teraz węzeł B
K06: left(A) ← right(C) ; prawy potomek CR staje się lewym potomkiem węzła A
K07: Jeśli left(A) ≠ NIL, to p(left(A)) ← A ; rodzicem CR jest teraz węzeł A
K08: right(C) ← A ; węzeł A robimy prawym potomkiem węzła C
K09: p(A) ← C ; węzeł C jest teraz rodzicem węzła A
K10: left(C) ← B ; lewym potomkiem C staje się węzeł B
K11: p(B) ← C ; a jego rodzicem jest węzeł C
K12: p(C) ← P ; rodzic A staje się rodzicem C
K13: Jeśli P ≠ NIL, idź do K15 ; czy węzeł C jest korzeniem drzewa AVL?
K14: root ← C i idź do K16 ; tak, ustaw nowy korzeń
K15: Jeśli left(P) = A, left(P) ← C
inaczej              right(P) ← C
; nie, zmieniamy dziecko rodzica z A na C
K16: Jeśli bf(C) = 1, to bf(A) ← -1
inaczej                bf(A) ←  0
; ustawiamy nowe współczynniki równowagi
K17: Jeśli bf(C) = -1, bf(B) ← 1
inaczej             bf(B) ←  0
 
K18: bf(C) ← 0  
K19: Zwróć C i zakończ  

 

AVLNode * AVLrotationLR(AVLNode * &root, AVLNode * A)
{
  AVLNode * B = A->left, * C = B->right, * P = A->p;

  B->right = C->left;
  if(B->right) B->right->p = B;
  A->left = C->right;
  if(A->left) A->left->p = A;
  C->right = A;
  C->left = B;
  A->p = B->p = C;
  C->p = P;
  if(P)
  {
    if(P->left == A) P->left = C; else P->right = C;
  }
  else root = C;

  A->bf = (C->bf ==  1) ? -1 : 0;
  B->bf = (C->bf == -1) ?  1 : 0;
  C->bf = 0;

  return C;
}

Wstawianie węzła w drzewie AVL

Operacja wstawiania nowego elementu do drzewa AVL jest dwuetapowa. Pierwszy etap przebiega identycznie jak dla drzewa BST. Nowy węzeł jest zawsze dodawany w liściu drzewa. W drugim etapie idąc od rodzica wstawionego węzła ku korzeniowi drzewa sprawdzamy, czy dodanie węzła nie naruszyło własności AVL. Jeśli tak, to za pomocą odpowiedniej rotacji węzłów przywracamy równowagę w węźle. Po wykonaniu rotacji zrównoważenie drzewa zostaje przywrócone, operacja wstawiania nowego węzła kończy się.

Algorytm wstawiania nowego węzła do drzewa AVL

Wejście:

root  - korzeń drzewa AVL
n  - wstawiany węzeł

Wyjście:

true, jeśli węzeł został dodany do drzewa AVL
false, jeśli węzeł nie został dodany. W takim przypadku węzeł jest usuwany z pamięci

Dane pomocnicze:

x, y, z  - węzły drzewa AVL
key(w)  - klucz węzła w
left(w)  - lewy potomek węzła w
right(w)  - prawy potomek węzła w
p(w)  - rodzic węzła w
bf(w)  - współczynnik równowagi węzła w

Lista kroków

K01: y ← NIL ; y wskazuje rodzica aktualnie przeglądanego węzła
K02: x ← root ; wyszukiwanie rozpoczynamy od korzenia drzewa AVL
K03: left(n) ← NIL;    right(n) ← NIL ; zerujemy pola left i right wstawionego elementu
K04: bf(n) ← 0 ; zerujemy współczynnik równowagi wstawionego węzła
K05: Dopóki x ≠ NIL wykonuj kroki K06...K08 ; przeszukujemy drzewo AVL
K06:     Jeśli key(n) = key(x), usuń węzeł i zakończ z false ; natrafiliśmy na węzeł o tym samym kluczu, co klucz wstawianego elementu
K07:     y ← x ; zapamiętujemy adres bieżąco odwiedzanego elementu
K08:     Jeśli key(n) < key(x), to x ← left(x)
    inaczej                         x ← right(x)
; jeśli klucz wstawianego elementu jest mniejszy od klucza bieżącego elementu,
  to wybieramy lewego potomka jako następny do odwiedzenia element.
  Inaczej wybieramy prawego potomka.
K09: p(n) ← y ; y zawsze pamięta rodzica
K11: Jeśli y = NIL, to root ← n i zakończ z true ; drzewo AVL jest puste, wstawiamy pierwszy element
K12: Jeśli key(n) < key(y), to left(y) ← n
inaczej                         right(y) ← n
; porównujemy klucz n z kluczem y. W zależności od wyniku węzeł
  n dowiązujemy do pola left lub right jego rodzica.
K13: Jeśli bf(y) ≠ 0, to bf(y) ← 0 i zakończ z true ; patrz: UWAGA NR 1
K14: Jeśli left(y) = n, to bf(y) ←  1
inaczej                 bf(y) ← -1
; patrz UWAGA NR 2
K15: z ← p(y) ; będziemy się przemieszczać w górę drzewa AVL w poszukiwaniu węzła, który
  stracił równowagę w wyniku dodania elementu n
K16: Dopóki z ≠ NIL, wykonuj kroki K17...K19 ; z - y  tworzą rodzinę (ojciec - dziecko) wzdłuż ścieżki do korzenia
K17     Jeśli bf(z) ≠ 0, idź do K21 ; bf(z) = 0 - obie gałęzie z były w równowadze
K18:     Jeśli left(z) = y, to bf(z) ←  1
    inaczej                 bf(z) ← -1
; zwiększamy lub zmniejszamy bf(z) w zależności od tego, w której
  gałęzi węzła z znajduje się jego potomek y. Gałąź ta jest cięższa!
K19:     y ←  z;   z ← p(z) ; przesuwamy się w górę drzewa w kierunku korzenia
K20: Zakończ z true  
K21: Jeśli bf(z) = -1, idź do K24 ; bf(z) = 1 - lewa gałąź z była cięższa
K22 Jeśli right(z) = y, to bf(z) = 0 i zakończ z true ; prawa gałąź ze wstawionym elementem zrównoważa lewą gałąź - kończymy
K23: Jeśli bf(y) = -1, wykonaj rotację LR (root,z)
inaczej            wykonaj rotację LL (root,z)
i zakończ w obu przypadkach
; patrz UWAGA NR 3
K24: Jeśli left(z) = y, to bf(z) = 0 i zakończ z true ; bf(z) = -1 - prawa gałąź była cięższa, teraz jest równowaga
K25: Jeśli bf(y) = 1, wykonaj rotację RL (root,z)
inaczej           wykonaj rotację RR (root,z)
; patrz UWAGA NR 4
K26: Zakończ z true  
obrazek

UWAGA NR 1: w kroku K13 sprawdzamy współczynnik równowagi bf rodzica y wstawionego węzła n. Jeśli jest on różny od zera, to go zerujemy i kończymy. Wyjaśnienie jest bardzo proste. Współczynnik bf różny od zera może posiadać w drzewie AVL wartość tylko -1 lub 1. Ponieważ dołączyliśmy nowy węzeł do pustego liścia, to przed operacją w gałęzi tej nie było żadnego poddrzewa - zatem wysokość jego była równa 0. Skoro bf rodzica jest różny od 0, to w drugiej gałęzi musiał być dokładnie jeden węzeł, co dawało poddrzewo o wysokości 1. Po dodaniu nowego węzła w obu gałęziach, lewej i prawej, mamy po jednym węźle, zatem współczynnik bf ich rodzica musi przyjąć wartość 0. Drzewo AVL zostaje zrównoważone, zatem kończymy operację.

obrazek

UWAGA NR 2: w kroku K14 wiemy, że przed operacją dodawania nowego węzła węzeł y rodzica miał współczynnik bf równy 0. Ponieważ dodaliśmy nowy element n do pustego liścia węzła y, zatem druga gałąź również była pusta. Sprawdzamy, która gałąź rodzica y stała się cięższa (zwiększyła się wysokość poddrzewa) po dodaniu nowego elementu n. W zależności od wyniku ustawiamy współczynnik bf rodzica wstawionego węzła na 1 (nowy węzeł n jest w lewej gałęzi węzła y i ona jest teraz cięższa) lub na -1 (nowy węzeł n jest w prawej gałęzi węzła y).

obrazek

UWAGA NR 3: w kroku K22 wiemy, że przeważało lewe poddrzewo węzła z i jest to poddrzewo, w którym wstawiliśmy nowy element, ponieważ węzeł y stanowi jego korzeń. Musimy skorygować zrównoważenie wykonując rotację. Rodzaj rotacji wybieramy w zależności od tego, które poddrzewo węzła y jest cięższe - jeśli lewe, to mamy rotację pojedynczą LL, a jeśli prawe, to musimy wykonać rotację podwójną LR.

 

UWAGA NR 4: tutaj mamy lustrzane odbicie sytuacji opisanej powyżej.

bool AVLinsert(AVLNode * &root, AVLNode * n)
{
  AVLNode * x = root, * y, * z;

  y = n->left = n->right = NULL;
  n->bf = 0;

  while(x)
  {
    if(x->key == n->key)
    {
      delete n;
      return false;
    }
    y = x;
    x = (n->key < x->key) ? x->left : x->right;
  }

  if(!(n->p = y))
  {
    root = n;
    return true;
  }

  if(n->key < y->key) y->left = n; else y->right = n;
  if(y->bf)
  {
    y->bf = 0;
    return true;
  }
  y->bf = (y->left == n) ? 1 : -1;
  z = y->p;
  while(z)
  {
    if(z->bf) break;
    z->bf = (z->left == y) ? 1 : -1;
    y = z; z = z->p;
  }

  if(!z) return true;

  if(z->bf == 1)
  {
    if(z->right == y)
    {
      z->bf = 0;
      return true;
    }
    if(y->bf == -1) AVRrotationLR(root,z); else AVRrotationLL(root,z);
    return true;
  }
  else
  {
    if(z->left == y)
    {
      z->bf = 0;
      return true;
    }
    if(y->bf == 1) AVRrotationRL(root,z); else AVRrotationRR(root,z);
    return true;
  }
}

Usuwanie węzła z drzewa AVL

Usuwanie węzła z drzewa AVL jest operacją dosyć skomplikowaną, ponieważ wymaga ona rozważenia dużej liczby przypadków przy przywracaniu równowagi drzewa AVL. W przypadku wstawiania węzła wystarczyło na ścieżce wiodącej od wstawionego węzła do korzenia wykryć konfigurację węzłów, których rotacja przywracała równowagę w drzewie. Po wykonaniu rotacji drzewo AVL znów było w równowadze i operacja wstawiania mogła się zakończyć. Przy usuwaniu węzła mamy nieco inną sytuację. Tutaj poddrzewo, w którym dokonaliśmy usunięcia węzła, zmniejsza swoją wysokość, co może propagować się w górę aż do samego korzenia drzewa. Jedna rotacja zatem może nie być wystarczająca do przywrócenia równowagi w drzewie - należy je kolejno wykonywać dla coraz wyższych węzłów dotąd, aż zniwelujemy zmniejszenie wysokości poddrzewa. Po drodze należy rozważać wiele różnych przypadków konfiguracji węzłów.

Ponieważ algorytm usuwania węzła jest dosyć rozbudowany, podamy go jedynie w formie opisowej oraz jako funkcję w języku C++. Jednakże jako ćwiczenie proponuję zdolnym czytelnikom zapis tego algorytmu w wybranej postaci: pseudokod, lista kroków czy schemat blokowy.

Usuwamy węzeł x z drzewa AVL.

obrazek

obrazek

obrazek

  • 3B: Współczynnik bf(y) jest taki sam jak współczynnik bf(t). Wykonujemy odpowiednią rotację pojedynczą:  RR (bf(y) = -1) lub LL (bf(y) = 1). Rotacja zmniejsza wysokość poddrzewa, algorytm wciąż kontynuujemy. Za węzeł z przyjmujemy węzeł t, za węzeł y przyjmujemy rodzica t.

obrazek

  • 3C: Współczynniki bf(y) i bf(t) są przeciwne. Wykonujemy rotację podwójną: RL (bf(y) = -1) lub LR (bf(y) = 1).  Węzeł s musi posiadać najwyższe poddrzewo o wysokość h-1 (drugie może mieć wysokość h-1 lub h-2), aby był spełniony warunek równowagi w węźle t. Rotacja zmniejsza wysokość poddrzewa, zatem algorytm wciąż kontynuujemy. Za węzeł z przyjmujemy węzeł s, za węzeł y przyjmujemy rodzica s.

obrazek

AVLNode * AVLremove(AVLNode * &root, AVLNode * x)
{
  AVLNode * t, * y, * z;
  bool nest;

  if((x->left) && (x->right))
  {
    y = remove(pred(x));
    nest = false;
  }
  else
  {
    if(x->left)
    {
      y = x->left; x->left = NULL;
    }
    else
    {
      y = x->right; x->right = NULL;
    }
    x->bf = 0;
    nest = true;
  }

  if(y)
  {
    y->p = x->p;
    if(y->left  = x->left)  y->left->p  = y;
    if(y->right = x->right) y->right->p = y;
    y->bf = x->bf;
  }
    
  if(x->p)
  {
    if(x->p->left == x) x->p->left = y; else x->p->right = y;
  }
  else root = y;
    
  if(nest)
  {
    z = y;
    y = x->p;
    while(y)
    {
      if(!(y->bf))
      {

// Przypadek nr 1

        y->bf = (y->left == z) ? -1 : 1;
        break;
      }
      else
      {
        if(((y->bf ==  1) && (y->left  == z)) || ((y->bf == -1) && (y->right == z)))
        {

// Przypadek nr 2

          y->bf = 0;
          z = y; y = y->p;
        }
        else
        {
          t = (y->left == z) ? y->right : y->left;
          if(!(t->bf))
          {
          
// Przypadek 3A

            if(y->bf == 1) AVLrotationLL(root, y); else AVLrotationRR(root, y);
            break;                      
          }
          else if(y->bf == t->bf)
          {
               
// Przypadek 3B

            if(y->bf == 1) AVLrotationLL(root, y); else AVLrotationRR(root, y);
            z = t; y = t->p;            
          }
          else
          {

// Przypadek 3C

            if(y->bf == 1) AVLrotationLR(root, y); else AVLrotationRL(root, y);
            z = y->p; y = z->p;              
          }
        }
      }
    }
  }
  return x;
}

Program testowy

Program umożliwia przetestowanie poszczególnych operacji na drzewie AVL. W układzie jest on identyczny z programem dla drzew BST. Zmianie uległy jedynie funkcje specyficzne dla drzew AVL. Program nie był intensywnie testowany, dlatego wszelkie usterki w jego działaniu proszę zgłaszać administratorowi, za co będziemy bardzo wdzięczni.

// Test procedur obsługi drzewa AVL
// (C)2008 mgr Jerzy Wałaszek
// Koło informatyczne I LO w Tarnowie
//-----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// definicja typu danych reprezentującego węzeł drzewa AVL
//--------------------------------------------------------

struct AVLNode
{
  AVLNode * p, * left, * right;
  int key, bf;
};

// Definicja klasy obsługującej drzewo AVL
//----------------------------------------

class AVL
{
  public:

    AVLNode * root;  // korzeń drzewa
    int count;       // liczba węzłów
  
    AVL();
    ~AVL();
    AVLNode * rotationRR(AVLNode * A);
    AVLNode * rotationLL(AVLNode * A);
    AVLNode * rotationRL(AVLNode * A);
    AVLNode * rotationLR(AVLNode * A);
    bool      insert(AVLNode * n);
    AVLNode * search(int key);
    int       maxKey(AVLNode * x);
    int       minKey(AVLNode * x);
    AVLNode * maxNode(AVLNode * x);
    AVLNode * minNode(AVLNode * x);
    AVLNode * pred(AVLNode * x);
    AVLNode * succ(AVLNode * x);
    AVLNode * remove(AVLNode * x);
    void      preorder(AVLNode * x);
    void      inorder(AVLNode * x);
    void      postorder(AVLNode * x);
    void      walk(AVLNode * x);
    void      coutAVLcount();
};

// **********************************************
// *** Definicje funkcji składowych klasy AVL ***
// **********************************************

// Konstruktor klasy AVL
//----------------------

AVL::AVL()
{
  root = NULL;
  count = 0;
}

// Destruktor klasy AVL
//---------------------

AVL::~AVL()
{
  while(root) delete(remove(root));
}

// Rotacja RR
//-----------

AVLNode * AVL::rotationRR(AVLNode * A)
{
  AVLNode * B = A->right, * P = A->p;

  A->right = B->left;
  if(A->right) A->right->p = A;
  B->left = A;
  B->p = P;
  A->p = B;
  if(P)
  {
    if(P->left == A) P->left = B; else P->right = B;
  }
  else root = B;

  if(B->bf == -1)
  {
    A->bf = B->bf = 0;
  }
  else
  {
    A->bf = -1; B->bf = 1;
  }
  return B;
}

// Rotacja LL
//-----------

AVLNode * AVL::rotationLL(AVLNode * A)
{
  AVLNode * B = A->left, * P = A->p;

  A->left = B->right;
  if(A->left) A->left->p = A;
  B->right = A;
  B->p = P;
  A->p = B;
  if(P)
  {
    if(P->left == A) P->left = B; else P->right = B;
  }
  else root = B;

  if(B->bf == 1)
  {
    A->bf = B->bf = 0;
  }
  else
  {
    A->bf = 1; B->bf = -1;
  }

  return B;
}

// Rotacja RL
//-----------

AVLNode * AVL::rotationRL(AVLNode * A)
{
  AVLNode * B = A->right, * C = B->left, * P = A->p;

  B->left = C->right;
  if(B->left) B->left->p = B;
  A->right = C->left;
  if(A->right) A->right->p = A;
  C->left = A;
  C->right = B;
  A->p = B->p = C;
  C->p = P;
  if(P)
  {
    if(P->left == A) P->left = C; else P->right = C;
  }
  else root = C;

  A->bf = (C->bf == -1) ?  1 : 0;
  B->bf = (C->bf ==  1) ? -1 : 0;
  C->bf = 0;

  return C;
}

// Rotacja LR
//-----------

AVLNode * AVL::rotationLR(AVLNode * A)
{
  AVLNode * B = A->left, * C = B->right, * P = A->p;

  B->right = C->left;
  if(B->right) B->right->p = B;
  A->left = C->right;
  if(A->left) A->left->p = A;
  C->right = A;
  C->left = B;
  A->p = B->p = C;
  C->p = P;
  if(P)
  {
    if(P->left == A) P->left = C; else P->right = C;
  }
  else root = C;

  A->bf = (C->bf ==  1) ? -1 : 0;
  B->bf = (C->bf == -1) ?  1 : 0;
  C->bf = 0;

  return C;
}

// Wstawia element do struktury AVL
//---------------------------------

bool AVL::insert(AVLNode * n)
{
  AVLNode * x = root, * y, * z;

  y = n->left = n->right = NULL;
  n->bf = 0;

  while(x)
  {
    if(x->key == n->key)
    {
      delete n;
      return false;
    }
    y = x;
    x = (n->key < x->key) ? x->left : x->right;
  }
  
  count++;
  
  if(!(n->p = y))
  {
    root = n;
    return true;
  }
  if(n->key < y->key) y->left = n; else y->right = n;
  if(y->bf)
  {
    y->bf = 0;
    return true;
  }
  y->bf = (y->left == n) ? 1 : -1;
  z = y->p;
  while(z)
  {
    if(z->bf) break;
    z->bf = (z->left == y) ? 1 : -1;
    y = z; z = z->p;
  }

  if(!z) return true;

  if(z->bf == 1)
  {
    if(z->right == y)
    {
      z->bf = 0;
      return true;
    }
    if(y->bf == -1) rotationLR(z); else rotationLL(z);
    return true;
  }
  else
  {
    if(z->left == y)
    {
      z->bf = 0;
      return true;
    }
    if(y->bf == 1) rotationRL(z); else rotationRR(z);
    return true;
  }
}

// Wyszukuje element wg wartości klucza
//-------------------------------------

AVLNode * AVL::search(int key)
{
  AVLNode * x = root;

  while((x) && (x->key != key))
    x = (key < x->key) ? x->left : x->right;

  return x;  
}

// Zwraca masymalną wartość klucza
//--------------------------------

int AVL::minKey(AVLNode * x)
{
  while(x->left) x = x->left;
  return x->key;  
}

// Zwraca minimalną wartość klucza
//--------------------------------

int AVL::maxKey(AVLNode * x)
{
  while(x->right) x = x->right;
  return x->key;  
}

// Zwraca węzeł z maksymalnym kluczem
//-----------------------------------

AVLNode * AVL::minNode(AVLNode * x)
{
  while(x->left) x = x->left;
  return x;
}

// Zwraca węzeł z minimalnym kluczem
//----------------------------------

AVLNode * AVL::maxNode(AVLNode * x)
{
  while(x->right) x = x->right;
  return x;
}

// Zwraca węzeł poprzednika
//-------------------------

AVLNode * AVL::pred(AVLNode * x)
{
  if(x->left) return maxNode(x->left);

  AVLNode * y;

  do
  {
    y = x;
    x = x->p;
  } while(x && (x->right != y));

  return x;  
}

// Zwraca węzeł następnika
//------------------------

AVLNode * AVL::succ(AVLNode * x)
{
  if(x->right) return minNode(x->right);

  AVLNode * y;

  do
  {
    y = x;
    x = x->p;
  } while(x && (x->left != y));

  return x;
}

// Usuwa element x ze struktury AVL. Zwraca usunięty węzeł
//--------------------------------------------------------

AVLNode * AVL::remove(AVLNode * x)
{
  AVLNode * t, * y, * z;
  bool nest;

  if((x->left) && (x->right))
  {
    y = remove(pred(x));
    count++;
    nest = false;
  }
  else
  {
    if(x->left)
    {
      y = x->left; x->left = NULL;
    }
    else
    {
      y = x->right; x->right = NULL;
    }
    x->bf = 0;
    nest = true;
  }

  if(y)
  {
    y->p = x->p;
    if(y->left  = x->left)  y->left->p  = y;
    if(y->right = x->right) y->right->p = y;
    y->bf = x->bf;
  }
    
  if(x->p)
  {
    if(x->p->left == x) x->p->left = y; else x->p->right = y;
  }
  else root = y;
    
  if(nest)
  {
    z = y;
    y = x->p;
    while(y)
    {
      if(!(y->bf))
      {

// Przypadek nr 1

        y->bf = (y->left == z) ? -1 : 1;
        break;
      }
      else
      {
        if(((y->bf ==  1) && (y->left  == z)) || ((y->bf == -1) && (y->right == z)))
        {

// Przypadek nr 2

          y->bf = 0;
          z = y; y = y->p;
        }
        else
        {
          t = (y->left == z) ? y->right : y->left;
          if(!(t->bf))
          {
          
// Przypadek 3A

            if(y->bf == 1) rotationLL(y); else rotationRR(y);
            break;                      
          }
          else if(y->bf == t->bf)
          {
               
// Przypadek 3B

            if(y->bf == 1) rotationLL(y); else rotationRR(y);
            z = t; y = t->p;            
          }
          else
          {

// Przypadek 3C

            if(y->bf == 1) rotationLR(y); else rotationRL(y);
            z = y->p; y = z->p;              
          }
        }
      }
    }
  }
  count--;
  return x;
}

// Przechodzi przez drzewo AVL metodą preorder
//--------------------------------------------

void AVL::preorder(AVLNode * x)
{
  if(x)
  {
    cout << x->key << endl;  // tutaj przetwarzamy bieżący węzeł
    preorder(x->left);
    preorder(x->right);
  }  
}

// Przechodzi przez drzewo AVL metodą inorder
//-------------------------------------------

void AVL::inorder(AVLNode * x)
{
  if(x)
  {
    inorder(x->left);
    cout << x->key << endl;  // tutaj przetwarzamy bieżący węzeł
    inorder(x->right);
  }
}

// Przechodzi przez drzewo AVL metodą postorder
//---------------------------------------------

void AVL::postorder(AVLNode * x)
{
  if(x)
  {
    postorder(x->left);
    postorder(x->right);
    cout << x->key << endl;  // tutaj przetwarzamy bieżący węzeł
  }  
}

// Przechodzi przez drzewo wypisując zawartość węzłów
//---------------------------------------------------

void AVL::walk(AVLNode * x)
{
  cout << x->key << " : bf = " << setw(2) << x->bf << " : Left-> ";
  if(x->left) cout << setw(3) << x->left->key;
  else        cout << "NIL";
  cout << ", Right-> ";
  if(x->right) cout << setw(3) << x->right->key;
  else         cout << "NIL";
  cout << " : p -> ";
  if(x->p) cout << setw(3) << x->p->key;
  else     cout << "NIL";
  cout << endl;
  if(x->left)  walk(x->left);
  if(x->right) walk(x->right);
}


// Wypisuje do cout liczbę węzłów drzewa AVL
//------------------------------------------

void AVL::coutAVLcount()
{
  cout << "\nLiczba wezlow drzewa AVL : " << count << endl << endl;  
}

// **********************************
// *** Funkcje obsługi opcji menu ***
// **********************************


// Dodaje nowe węzły do drzewa AVL
//--------------------------------

void add(AVL * T)
{
  cout << "Dodawanie nowych wezlow do drzewa AVL\n"
          "-------------------------------------\n\n";
  T->coutAVLcount();
  cout << "Podaj liczbe wezlow do utworzenia, a nastepnie wprowadz odpowiednia\n"
          "liczbe kluczy nowych wezlow.\n\n";

  int i,n;

  AVLNode * x;
  
  cin >> n;
  for(i = 0; i < n; i++)
  {
    x = new AVLNode;
    cin >> x->key;
    T->insert(x);      
  }
  
  cout << endl;
  T->walk(T->root);
  T->coutAVLcount();      
}

// Usuwa węzeł o zadanym kluczu
//-----------------------------

void del(AVL * T)
{
  cout << "Usuwanie wezla drzewa AVL o zadanym kluczu\n"
          "------------------------------------------\n\n";
  T->coutAVLcount();
  
  AVLNode * x;
  int key;
  
  cout << "Podaj klucz usuwanego wezla : "; cin >> key;

  x = T->search(key);
  
  if(x)
  {
    delete T->remove(x);
    cout << endl;
    if(T->root) T->walk(T->root);
    T->coutAVLcount();    
  }
  else cout << "\nBrak wezla o takim kluczu\n";
}

// Sprawdza, czy drzewo zawiera węzeł o zadanym kluczu
//----------------------------------------------------

void check(AVL * T)
{
  cout << "Sprawdzenie obecnosci wezla o danym kluczu w drzewie AVL\n"
          "--------------------------------------------------------\n\n"
          "Podaj klucz wezla : ";

  int key;
  
  cin >> key;
  
  cout << endl;
  
  if(T->search(key)) cout << "Wezel znaleziony.\n";
  else               cout << "W drzewie AVL brak wezla o podanym kluczu\n";
}

// Znajduje minimalny i maksymalny klucz
//--------------------------------------

void minmax(AVL * T)
{
  cout << "Znajdowanie minimalnego i maksymalnego klucza w drzewie AVL\n"
          "-----------------------------------------------------------\n\n"
          "Klucz minimalny  : " << T->minKey(T->root) << endl <<
          "Klucz maksymalny : " << T->maxKey(T->root) << endl;
}

// Znajduje poprzednik węzła o zadanym kluczu
//-------------------------------------------

void pred(AVL * T)
{
  cout << "Znajdowanie poprzednika w drzewie AVL\n"
          "-------------------------------------\n\n"
          "Podaj klucz wezla : ";
  int key;
  AVLNode * x;
  
  cin >> key;
  cout << endl;
  
  x = T->search(key);
  
  if(x)
  {
    x = T->pred(x);
    if(x) cout << "Poprzednikiem [" << key << "] jest " << x->key << endl;
    else  cout << "Wezel [" << key << "] nie posiada poprzednika\n";   
  }
  else cout << "Wezel o podanym kluczu nie istnieje w drzewie AVL\n";
}

// Znajduje następnik węzła o zadanym kluczu
//------------------------------------------

void succ(AVL * T)
{
  cout << "Znajdowanie nastepnika w drzewie AVL\n"
          "------------------------------------\n\n"
          "Podaj klucz wezla : ";
  int key;
  AVLNode * x;
  
  cin >> key;
  cout << endl;
  
  x = T->search(key);
  
  if(x)
  {
    x = T->succ(x);
    if(x) cout << "Nastepnikiem [" << key << "] jest " << x->key << endl;
    else  cout << "Wezel [" << key << "] nie posiada nastepnika\n";   
  }
  else cout << "Wezel o podanym kluczu nie istnieje w drzewie AVL\n";     
}

// Przechodzi przez drzewo algorytmem preorder
//--------------------------------------------

void preorder(AVL * T)
{
  cout << "Przechodzenie drzewa AVL algorytmem preorder\n"
          "--------------------------------------------\n\n";
  T->preorder(T->root);    
}

// Przechodzi przez drzewo algorytmem inorder
//--------------------------------------------

void inorder(AVL * T)
{
  cout << "Przechodzenie drzewa AVL algorytmem inorder\n"
          "-------------------------------------------\n\n";
  T->inorder(T->root);
}

// Przechodzi przez drzewo algorytmem postorder
//--------------------------------------------

void postorder(AVL * T)
{
  cout << "Przechodzenie drzewa AVL algorytmem postorder\n"
          "---------------------------------------------\n\n";
  T->postorder(T->root);     
}

// **********************
// *** Program główny ***
// **********************

main()
{
  AVL * T = new AVL();
  int choice;
  
  do
  {
    system("cls"); // w Linuxie wstaw clear

    cout << "Test funkcji obslugi drzew AVL\n"
            "==============================\n\n"
            "Wybor Funkcja\n"
            "-------------\n"
            " [0]  Koniec\n"
            " [1]  Dodaj wezly\n"
            " [2]  Usun wezel\n"
            " [3]  Sprawdz obecnosc wezla\n"
            " [4]  Wezel min i max\n"
            " [5]  Poprzednik\n"
            " [6]  Nastepnik\n"
            " [7]  Preorder\n"
            " [8]  Inorder\n"
            " [9]  Postorder\n"
            "--------------\n"
            "Twoj wybor : ";

    cin >> choice;

    system("cls");

    switch(choice)
    {
      case 1 : add(T);       break;
      case 2 : del(T);       break;
      case 3 : check(T);     break;
      case 4 : minmax(T);    break;
      case 5 : pred(T);      break;
      case 6 : succ(T);      break;
      case 7 : preorder(T);  break;
      case 8 : inorder(T);   break;
      case 9 : postorder(T); break;
    }

    if((choice >= 1) && (choice <= 9))
    {
      cout << endl;
      system("pause");
    }

  } while(choice);
  
  delete T;
}


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe