Drzewa AVL


Tematy pokrewne   Podrozdziały
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew
  Wiadomości podstawowe
Rotacje drzewa AVL
    Rotacja RR
    Rotacja LL
    Rotacja RL
    Rotacja LR
Wstawianie węzła do drzewa AVL
Usuwanie węzła z drzewa AVL

Wiadomości podstawowe

Drzewo binarnych wyszukiwań BST (ang. BST – Binary Search Tree) jest dobrą strukturą danych do szybkiego wyszukiwania elementów. Jeśli wysokość drzewa jest minimalna, to operacja wyszukiwania elementu posiada pesymistyczną klasę złożoności obliczeniowej O(log2 n). Jest to wynik bardzo korzystny. Np. wyszukanie danej w drzewie BST zawierającym 1.000.000 elementów wymaga jedynie co najwyżej 20 porównań. Gdybyśmy elementy te umieścili w tablicy lub na liście liniowej, to analogiczne wyszukiwanie wymagałoby co najwyżej 1.000.000 operacji porównań. Co więcej, funkcja logarytmiczna rośnie wolniej od funkcji liniowej, zatem zysk powiększa się przy wzroście liczby elementów – jeśli będzie ich 1000 razy więcej, to w przypadku tablicy i listy czas wyszukiwania wydłuży się 1000 razy (przyrośnie liniowo), natomiast dla drzewa BST otrzymamy co najwyżej 30 operacji porównań.

Niestety, drzewa BST w klasycznej postaci posiadają nieprzyjemną wadę – mogą się degenerować do list liniowych, a wtedy tracimy ich podstawową zaletę – klasę złożoności O(log2n), która w przypadku niekorzystnym może stać się klasą O(n). Problem ten można załagodzić przez stosowanie algorytmów równoważących drzewa BST, np. algorytmu DSW. Niemniej jednak jest to czasami kłopotliwe. Aby rozwiązać problem degeneracji drzew BST, wymyślono różne ich odmiany. Jedną z nich, najstarszą, jest drzewo AVL (ang. AVL Tree). Nazwa bierze się od nazwisk dwóch radzieckich wynalazców Georgija Adelsona-Wielskiego (ros. Гео́ргий Макси́мович Адельсо́н-Ве́льский) oraz Evgenija Landisa (ros. Евгений Михайлович Ландис), którzy w roku 1962 opublikowali pracę na temat drzew AVL.

Drzewo AVL jest drzewem BST, w którym dla każdego węzła wysokość jego poddrzew dla lewego i prawego syna różni się co najwyżej o 1. Aby osiągnąć ten warunek, drzewo AVL posiada zmodyfikowane procedury wstawiania i usuwania węzłów. Równoważenie uzyskuje się poprzez odpowiednie rotacje w lewo i w prawo węzłów drzewa na ścieżce w kierunku korzenia, jeśli został zaburzony warunek drzewa AVL (wysokości poddrzew różnią się co najwyżej o 1) po wstawieniu nowego węzła lub po usunięciu istniejącego węzła.

 

Każdy węzeł drzewa AVL posiada dodatkowe pole o nazwie bf (ang. balance factor – współczynnik równowagi). Wartość tego pola spełnia równanie:

 

bf = hL - hR

gdzie: hL i hR to odpowiednio wysokości lewego i prawego poddrzewa.

 

Z powyższego wzoru możemy wysnuć następujące wnioski:

 

bf =  1 – lewe poddrzewo jest wyższe o jeden poziom od prawego poddrzewa, hL > hR

bf =  0 – oba poddrzewa są równej wysokości, hL = hR

bf = -1 – prawe poddrzewo jest wyższe o jeden poziom od lewego poddrzewa, hL < hR

 

Innych wartości w drzewie AVL współczynnik bf nie może przyjmować – ograniczenie to nosi nazwę własności drzewa AVL (ang. AVL tree property). Poniżej przedstawiamy dwa drzewa, w których węzły oprócz kluczy posiadają również pola bf zapisane po dwukropku:

 

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

 

W prawym drzewie węzeł o kluczu 20 posiada współczynnik równowagi równy -2, ponieważ dla tego węzła mamy:

 

hL = 0
hR = 2

bf = hL - hR = 0 - 2 = -2

 

Węzły drzew AVL będziemy reprezentowali następującą strukturą:

 

Lazarus Code::Blocks Free Basic
type
  PAVLNode = ^AVLNode;
  AVLNode  = record
    up    : PAVLNode;
    left  : PAVLNode;
    right : PAVLNode;
    key   : typ_danych;
    bf    : integer;
  end;
struct AVLNode
{
  AVLNode * up;
  AVLNode * left;
  AVLNode * right;
  typ_danych key;
  int bf;
};
Type AVLNode
  up As AVLNode Ptr
  left As AVLNode Ptr
  right As AVLNode Ptr
  key As typ_danych
  bf As Integer
End Type

 

Znaczenie poszczególnych pól jest następujące:

 

up  –  adres rodzica węzła
left  – adres lewego syna
right  – adres prawego syna
key  – klucz, według którego są uporządkowane węzły drzewa
bf  – współczynnik równowagi

 

Oprócz powyższych pól węzły mogą oczywiście zawierać dodatkowe pola potrzebne w implementacji tej struktury danych w określonej aplikacji.

 

Rotacje drzewa AVL

Wyszukiwanie informacji w drzewie AVL niczym nie różni się od wyszukiwania informacji w drzewie BST, zatem możemy stosować tutaj ten sam algorytm. Dotyczy to również znajdowania poprzedników i następników węzła. Różnice pojawiają się przy wstawianiu i usuwaniu węzłów, ponieważ operacje te mogą prowadzić do zmiany wysokości poddrzew. 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 przywracamy równowagę:

 

obrazek

 

Węzeł 1 stał się lewym 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. To jest właśnie cel wykonywania rotacji - zrównoważenie wysokości poddrzew, gdy różnią się one od siebie wysokością 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ć obrotem RR, ponieważ wystąpią konflikty pomiędzy niezaznaczonymi na rysunku synami węzłów. Najpierw dokonujemy obrotu LL węzłów 2 i 3 (sprowadza on węzły do układu RR), 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 synów. Węzeł biegunowy rotacji oznaczamy kolorem czerwonym.

 

Rotacja 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 synem węzła B. Lewy syn węzła B (BL) staje się prawym synem 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
A.bf = - 2,   B.bf = -1

 

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

 

B.bf = hBL - hBR,     B.bf = -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 -2, to wnioskujemy, iż przeważa o dwa poziomy prawe poddrzewo A:

 

A.bf = hAL - hAR,    A.bf = -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 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:

 

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

 

obrazek

Przypadek nr 2
A.bf = -2,   B.bf = 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:

 

A.bf = -1
B.bf =  1

obrazek

Przypadek nr 3
A.bf = -2,   B.bf = 1

W przypadku nr 3 otrzymujemy po rotacji:

 

A.bf = -1
B.bf =  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! Zamiast niej będą stosowane rotacje podwójne.

 

Podsumujmy zatem:

 

Przed rotacją
A.bf -2 -2
B.bf -1 0
Po rotacji RR
A.bf 0 -1
B.bf 0 1

Algorytm rotacji RR dla drzewa AVL

Wejście:

root  –  referencja do zmiennej, która przechowuje adres korzenia drzewa AVL
A  –  wskazanie węzła głównego rotacji.

Wyjście:

Wykonanie rotacji RR

Dane pomocnicze:

B  –  wskazanie węzła B
p  –  wskazanie ojca A

Lista kroków

K01: B ← (Aright) ; w B umieszczamy adres prawego syna węzła A
K02: p ← (Aup) ; w p umieszczamy ojca A
K03: (Aright) ← (Bleft) ; prawym synem A staje się lewy syn B
K04: Jeśli (Aright) ≠ nil, to (Arightup) ← A ; jeśli prawy syn istnieje, to jego ojcem jest teraz A
K05: (Bleft) ← A ; lewym synem B staje się A
K06: (Bup) ← p ; ojcem B jest ojciec węzła A
K07: (Aup) ← B ; natomiast A zmienia ojca na B
K08: Jeśli p = nil, to idź do K11 ; sprawdzamy, czy węzeł A był korzeniem
K09: Jeśli (pleft) = A, to (pleft) ← B
Inaczej                     (pright) ← B
; jeśli nie, to uaktualniamy jego ojca
K10: Idź do K12  
K11: rootB ; jeśli A był korzeniem, to uaktualniamy korzeń
K12: Jeśli (Bbf) = -1, to (Abf) ←  0, (Bbf) ← 0
Inaczej                    (Abf) ← -1, (Bbf) ← 1
; modyfikujemy współczynniki równowagi
K13: Zakończ  

 

Rotacja 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 synem węzła B. Prawy syn węzła B (BR) staje się lewym synem 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ą
A.bf 2 2
B.bf 1 0
Po rotacji RR
A.bf 0 1
B.bf 0 -1

 

Algorytm rotacji LL dla drzewa AVL

Wejście:

root  –  referencja do zmiennej, która przechowuje adres korzenia drzewa AVL
A  –  wskazanie węzła głównego rotacji.

Wyjście:

Wykonanie rotacji LL

Dane pomocnicze:

B  –  wskazanie węzła B
p  –  wskazanie ojca A

Lista kroków

K01: B ← (Aleft) ; w B umieszczamy adres lewego syna węzła A
K02: p ← (Aup) ; w p umieszczamy ojca A
K03: (Aleft) ← (Bright) ; lewym synem A staje się prawy syn B
K04: Jeśli (Aleft) ≠ nil, to (Aleftup) ← A ; jeśli lewy syn istnieje, to jego ojcem jest teraz A
K05: (Bright) ← A ; prawym synem B staje się A
K06: (Bup) ← p ; ojcem B jest ojciec węzła A
K07: (Aup) ← B ; natomiast A zmienia ojca na B
K08: Jeśli p = nil, to idź do K11 ; sprawdzamy, czy węzeł A był korzeniem
K09: Jeśli (pleft) = A, to (pleft) ← B
Inaczej                     (pright) ← B
; jeśli nie, to uaktualniamy jego ojca
K10: Idź do K12  
K11: rootB ; jeśli A był korzeniem, to uaktualniamy korzeń
K12: Jeśli (Bbf) = 1, to (Abf) ← 0, (Bbf) ←  0
Inaczej                   (Abf) ← 1, (Bbf) ← -1
; modyfikujemy współczynniki równowagi
K13: Zakończ  

 

Rotacja RL

obrazek

 

Rotacja RL jest złożeniem rotacji LL i rotacji RR, dlatego nosi nazwę rotacji podwójnej. Pierwsza rotacja LL sprowadza gałąź drzewa do postaci dogodnej dla następnej rotacji RR. Zamiast jednak wykonywać kolejno rotację RR, a następnie LL, zaprojektujemy algorytm, który od razu przekształca pozycje węzłów do pozycji końcowej. Węzeł C zastępuje węzeł A. Węzeł A staje się lewym dzieckiem węzła C i przejmuje lewego syna węzła C w miejsce swojego prawego syna. Węzeł B staje się prawym synem C i przejmuje prawego syna węzła C w miejsce swojego lewego syna. 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
A.bf = -2,   B.bf = 1,   C.bf = -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:

 

C.bf = hCL - hCR,    C.bf = -1,    hCR = hCL + 1

 

Zatem lżejsze jest poddrzewo lewe. Oznaczmy:

 

hCL = h
h
CR = h + 1
hC = h + 2

 

Teraz przechodzimy do wierzchołka B:

 

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

 

Na koniec pozostaje wierzchołek A:

 

A.bf = hAL - hAR,    A.bf = -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:

 

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

obrazek

Przypadek nr 2
A.bf = -2,   B.bf = 1,   C.bf = 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:

 

A.bf = 0
B.bf = 0
C.bf = 0

 

obrazek

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

 

W przypadku nr 3 otrzymujemy:

 

A.bf = 0
B.bf = -1
C.bf = 0

 

Podsumujmy otrzymane wyniki:

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

 

Z tabelki wynika, iż współczynnik równowagi C.bf jest zawsze zerowany, a pozostałe zależą od początkowej wartości C.bf.

 

Algorytm rotacji RL dla drzewa AVL

Wejście:

root  – referencja do zmiennej przechowującej adres korzenia drzewa AVL
A  –  wskazanie węzła głównego rotacji

Wyjście:

Wykonanie rotacji RL

Dane pomocnicze:

B  –  wskazanie węzła B
C  –  wskazanie węzła C
p  – wskazanie ojca A

Lista kroków

K01: B ← (Aright) ; ustawiamy adresy węzłów biorących udział w rotacji
K02: C ← (Bleft)  
K03: p ← (Aup)  
K04: (Bleft) ← (Cright) ; lewym synem B staje się prawy syn C
K05: Jeśli (Bleft) ≠ nil, to (Bleftup) ← B ; jeśli lewy syn B istnieje, to B staje się jego ojcem
K06: (Aright) ← (Cleft) ; prawym synem A staje się lewy syn C
K07: Jeśli (Aright) ≠ nil, to (Arightup) ← A ; jeśli prawy syn A istnieje, to A staje się jego ojcem
K08: (Cleft) ← A ; lewym synem C staje się A
K09: (Cright) ← B ; prawym synem C staje się B
K10: (Aup) ← C ; ojcem A staje się C
K11: (Bup) ← C ; ojcem B staje się C
K12: (Cup) ← p ; ojcem C staje się były ojciec A
K13: Jeśli p = nil, to idź do K16 ; sprawdzamy, czy A był korzeniem
K14: Jeśli (pleft) = A, to (pleft) ← C
Inaczej  (pright) ← C
; jeśli nie, to uaktualniamy byłego ojca A, aby był ojcem C
K15: Idź do K17  
K16: rootC ; w przeciwnym razie uaktualniamy korzeń
K17: Jeśli (Cbf) = -1, to (Abf) ← 1
Inaczej                    (Abf) ← 0
; uaktualniamy współczynniki równowagi
K18: Jeśli (Cbf) = 1, to (Bbf) ← -1
Inaczej                   (Bbf) ←  0
 
K19: (Cbf) ← 0  
K20: Zakończ  

 

Rotacja 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 synem węzła C i przejmuje on prawego syna CR w miejsce swojego lewego syna. Węzeł B staje się lewym synem C i przejmuje on lewego syna C w miejsce swojego prawego syna. Współczynniki równowagi zmieniają się następująco (proponuję ci sprawdzenie tych wyników):

 

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

 

Współczynnik równowagi C.bf jest zawsze zerowany, a pozostałe zależą od początkowej wartości C.bf.

 

Algorytm rotacji LR dla drzewa AVL

Wejście:

root  – referencja do zmiennej przechowującej adres korzenia drzewa AVL
A  –  wskazanie węzła głównego rotacji

Wyjście:

Wykonanie rotacji LR

Dane pomocnicze:

B  –  wskazanie węzła B
C  –  wskazanie węzła C
p  – wskazanie ojca A

Lista kroków

K01: B ← (Aleft) ; ustawiamy adresy węzłów biorących udział w rotacji
K02: C ← (Bright)  
K03: p ← (Aup)  
K04: (Bright) ← (Cleft) ; prawym synem B staje się lewy syn C
K05: Jeśli (Bright) ≠ nil, to (Brightup) ← B ; jeśli prawy syn B istnieje, to B staje się jego ojcem
K06: (Aleft) ← (Cright) ; lewym synem A staje się prawy syn C
K07: Jeśli (Aleft) ≠ nil, to (Aleftup) ← A ; jeśli lewy syn A istnieje, to A staje się jego ojcem
K08: (Cright) ← A ; prawym synem C staje się A
K09: (Cleft) ← B ; lewym synem C staje się B
K10: (Aup) ← C ; ojcem A staje się C
K11: (Bup) ← C ; ojcem B staje się C
K12: (Cup) ← p ; ojcem C staje się były ojciec A
K13: Jeśli p = nil, to idź do K16 ; sprawdzamy, czy A był korzeniem
K14: Jeśli (pleft) = A, to (pleft) ← C
Inaczej  (pright) ← C
; jeśli nie, to uaktualniamy byłego ojca A, aby był ojcem C
K15: Idź do K17  
K16: rootC ; w przeciwnym razie uaktualniamy korzeń
K17: Jeśli (Cbf) = 1, to (Abf) ← -1
Inaczej                    (Abf) ← 0
; uaktualniamy współczynniki równowagi
K18: Jeśli (Cbf) = -1, to (Bbf) ← 1
Inaczej                   (Bbf) ←  0
 
K19: (Cbf) ← 0  
K20: Zakończ  

 

Wstawianie węzła do drzewa AVL

Operacja wstawiania węzła do drzewa AVL jest dwuetapowa. Pierwszy etap jest identyczny z operacją wstawiania węzła do drzewa BST. Następnie, idąc w górę w kierunku korzenia drzewa, musimy odpowiednio zmodyfikować współczynniki równowagi węzłów i jeśli natrafimy na współczynnik bf równy 2 lub -2, to za pomocą rotacji zrównoważamy drzewo AVL – rotacja powoduje przywrócenie danemu poddrzewu wysokości sprzed wykonania operacji wstawiania. Zatem po wykonaniu tej rotacji drzewo AVL jest zrównoważone i możemy zakończyć wstawianie elementu.

 

Algorytm wstawiania węzła do drzewa AVL

Wejście
root  –  referencja do zmiennej, która przechowuje adres korzenia drzewa AVL
k  –  klucz wstawianego węzła
Wyjście:
Drzewo AVL z nowym węzłem o kluczu k
Elementy pomocnicze:
w,p,r  –  wskazania węzłów
LL(roor,x), RR(root,x)
LR(root,x), RL(root,x)
 –  rotacje węzłów, x jest wskazaniem węzła głównego rotacji
Lista kroków:
K01: Utwórz nowy węzeł ; tworzymy nowy węzeł
K02: w ← adres nowego węzła  
K03: (wleft) ← nil ; inicjujemy pola węzła
K04: (wright) ← nil  
K05: (wkey) ← k  
K06: (wbf) ← 0  
K07: proot  
K08: Jeśli p = nil, to rootw i zakończ ; sprawdzamy, czy drzewo jest puste
K09: Jeśli k < (pkey), to idź do K13 ; porównujemy klucze
K10: Jeśli (pright) = nil, to
    (pright) ← w
    Idź do K16
; jeśli prawy syn nie istnieje, to
; nowy węzeł staje się prawym synem
; i wychodzimy z pętli
K11: p ← (pright) ; inaczej przechodzimy do prawego syna
K12: Idź do K09 ; i kontynuujemy pętlę
K13 Jeśli (pleft) = nil, to:
    (pleft) ← w
    Idź do K16
; to samo dla lewego syna
K14: p ← (pleft)  
K15: Idź do K09  
K16: (wup) ← p ; uzupełniamy ojca węzła
K17: Jeśli (pbf) = 0, to idź do K20 ; modyfikujemy współczynniki równowagi w kierunku korzenia
K18: (pbf) ← 0 ; patrz: UWAGA NR 1
K19: Zakończ  
K20: Jeśli (pleft) = w, to (pbf) ← 1
Inaczej                    (pbf) ← -1
; patrz: UWAGA NR 2
K21: r ← (pup) ; będziemy się przemieszczać w górę drzewa AVL w poszukiwaniu węzła, który
; stracił równowagę w wyniku dodania elementu n.
K22: Dopóki rnil: wykonuj kroki K23...K26 ; wskazania r i p to ojciec i syn na tej ścieżce
K23:     Jeśli (rbf) ≠ 0, to idź do K28 ; jeśli r.bf = 0, to obie gałęzie r były w równowadze przed dodaniem węzła
K24:     Jeśli (rleft) = p, to (rbf) ←  1
    Inaczej                   (rbf) ← -1
; zwiększamy lub zmniejszamy r.bf w zależności od tego, w której
  gałęzi węzła r został dodany węzeł w. Gałąź ta jest cięższa!
K25:     pr ; przemieszczamy się w górę drzewa
K26:     r ← (rup)  
K27: Zakończ  
K28: Jeśli (rbf) = -1, to idź do K32 ; sprawdzamy, która z gałęzi r była cięższa
K29: Jeśli (rright) = p, to (rbf) ← 0 i zakończ ; prawa gałąź ze wstawionym elementem równoważy lewą gałąź - kończymy
K30: Jeśli (pbf) = -1, to LR(root,r)
Inaczej                    LL(root,r)
; patrz UWAGA NR 3
K31: Zakończ  
K32: Jeśli (rleft) = p, to (rbf) ← 0 i zakończ ; lewa gałąź ze wstawionym elementem równoważy prawą gałąź
K33: Jeśli (pbf) = 1, to RL(root,r)
Inaczej                  RR(root,r)
; patrz: UWAGA NR 4
K34: Zakończ  

 

obrazek

UWAGA NR 1: w kroku K17 sprawdzamy współczynnik równowagi bf ojca wstawionego węzła w. 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ści 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 ojca musi przyjąć wartość 0. Drzewo AVL zostaje zrównoważone, kończymy operację.

obrazek

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

obrazek

UWAGA NR 3: w kroku K30 wiemy, że przeważało lewe poddrzewo węzła r i jest to poddrzewo, w którym wstawiliśmy nowy element, ponieważ węzeł p 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 p 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.

 

Usuwanie węzła z drzewa AVL

Usuwanie węzła z drzewa AVL jest operacją dosyć skomplikowaną, ponieważ wymaga rozważenia dużej liczby przypadków przy przywracaniu równowagi. Przy wstawianiu węzła wystarczyło na ścieżce wiodącej od tego 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 - rotacje należy 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.

Zasada działania algorytmu usuwającego węzeł jest następująca:

Usuwamy węzeł x z drzewa AVL.

obrazek

  • 2: y.bf ≠ 0 i skrócone zostało cięższe poddrzewo. W takim przypadku y.bf ← 0, lecz algorytmu nie kończymy, ponieważ drzewo o wierzchołku y ma teraz mniejszą o 1 wysokość, co może wywierać wpływ na zrównoważenie węzłów na wyższych poziomach drzewa AVL. Za węzeł z przyjmujemy obecny węzeł y, za węzeł y przyjmujemy rodzica y.

obrazek

  • 3: bf(y) ≠ 0 i skrócone zostało lżejsze poddrzewo . Musimy rozważyć kilka przypadków w cięższym poddrzewie.
    • 3A: współczynnik bf(t) dziecka węzła y w cięższym poddrzewie jest równy 0. Wykonujemy odpowiednią rotację pojedynczą: RR (bf(y) = -1) lub LL (bf(y) = 1). Rotacja nie zmienia wysokości poddrzewa, ale likwiduje niezrównoważenie. Zatem algorytm możemy zakończyć zwracając x.

obrazek

  • 3B: Współczynnik y.bf jest taki sam jak współczynnik t.bf. Wykonujemy odpowiednią rotację pojedynczą:  RR (y.bf = -1) lub LL (y.bf = 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 y.bf i t.bf są przeciwne. Wykonujemy rotację podwójną: RL (y.bf = -1) lub LR (y.bf = 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

 

Algorytm usuwania węzła z drzewa AVL – removeAVL(root,x)

Wejście
root  –  referencja do zmiennej, która przechowuje adres korzenia drzewa AVL
x  –  wskazanie węzła do usunięcia
Wyjście:
Wskazanie x oraz drzewo AVL bez węzła x.
Elementy pomocnicze:
t,y,z  –  wskazania węzłów
LL(root,x), RR(root,x)
LR(root,x), RL(root,x)
 –  rotacje węzłów, x jest wskazaniem węzła głównego rotacji
pred(x)  –  zwraca wskazanie poprzednika węzła x
nest  –  zmienne logiczna, która wskazuje zagnieżdżenie
Lista kroków:
K01: Jeśli ((xleft) = 0) obrazek ((xright) = 0), to idź do K05 ; jeśli węzeł x posiada obu synów, to
K02: y ← removeAVL(root,pred(x)) ; rekurencyjnie usuwamy poprzednik x, zapamiętując go w y
K03: nest ← false ; zerujemy zagnieżdżenie
K04: Idź do K08  
K05: Jeśli (xleft) ≠ nil, to y ← (xleft), (xleft) ← nil
Inaczej                      y ← (xright), (xright) ← nil
; węzeł posiada jednego syna lub wcale
K06: (xbf) ← 0 ; x.bf = 0, ponieważ ewentualny syn trafił do y
K07: nest ← true ; ustawiamy zagnieżdżenie
K08: Jeśli y = nil, to idź do K15 ; jeśli y istnieje, to wstawiamy go za x
K09: (yup) ← (xup) ; ojcem y staje się ojciec węzła x
K10: (yleft) ← (xleft) ; lewy syn x staje się lewym synem y
K11: Jeśli (yleft) ≠ nil, to (yleftup) ← y ; jeśli lewy syn istnieje, to jego ojcem staje się y
K12: (yright) ← (xright) ; to samo dla prawego syna
K13: Jeśli (yright) ≠ nil, to (yrightup) ← y  
K14: (ybf) ← (xbf)  
K15: Jeśli (xup) = nil, to idź do K18 ; jeśli x posiada ojca, to
K16: Jeśli (xupleft) = x, to (xupleft) ← y
Inaczej                          (xupright) ← y
; synem tego ojca staje się y
K17: Idź do K19  
K18: rooty ; inaczej y wstawiamy do korzenia
K19: Jeśli nest = false, to idź do K43 ; sprawdzamy zagnieżdżenie
K20: zy ; ustawiamy wskaźniki, będziemy szli w kierunku korzenia drzewa
K21: y ← (xup)  
K22: Dopóki ynil, wykonuj kroki K23...K42 ; w pętli sprawdzamy różne przypadki
K23:     Jeśli (ybf) ≠ 0, to idź do K26  
K24:     Jeśli (yleft) = z, to (ybf) ← -1 ; przypadek nr 1
K25     Idź do K43 ; przerywamy pętlę
K26:     Jeśli (((ybf) ≠ 1) obrazek ((yleft) ≠ z)) obrazek
            (((ybf) ≠ -1) obrazek ((yright) ≠ z)), to idź do K31
 
K27:     (ybf) ← 0 ; przypadek 2
K28:     zy ; przechodzimy na wyższy poziom drzewa
K29:     y ← (yup)  
K30:     Następny obieg pętli K22  
K31:     Jeśli (yleft) = z, to t ← (yright)
    Inaczej                    t ← (yleft)
; t wskazuje syna y przeciwnego do z
K32:     Jeśli (tbf) = 0, to idź do K35  
K33:     Jeśli (ybf) = 1, to LL(root,y)
    Inaczej                  RR(root,y)
; przypadek 3A
K34:     Idź do K43 ; przerywamy pętlę
K35:     Jeśli (ybf) ≠ (tbf), to idź do K40  
K36:     Jeśli (ybf) = 1, to LL(root,y)
    Inaczej                  RR(root,y)
; przypadek 3B
K37:     zt ; idziemy na wyższy poziom
K38:     y ← (tup)  
K39:     Następny obieg pętli K22  
K40:     Jeśli (ybf) = 1, to LR(root,y)
    Inaczej                  RL(root,y)
; przypadek 3C
K41:     z ← (yup) ; idziemy na wyższy poziom i kontynuujemy pętlę
K42:     y ← (zup)  
K43: Zakończ z wynikiem x  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program tworzy drzewo AVL z 32 węzłów o kluczach od 1 do 32. Wyświetla je. Następnie usuwa z niego 15 losowych węzłów i wyświetla ponownie drzewo AVL.

 

Lazarus
// Drzewo AVL
// Data: 22.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program AVL;

// Definicja typu węzłów drzewa AVL
//---------------------------------
type
  PAVLNode = ^AVLNode;
  AVLNode  = record
    up    : PAVLNode;
    left  : PAVLNode;
    right : PAVLNode;
    key   : integer;
    bf    : integer;
  end;

// Zmienne globalne
//-----------------
var
  cr,cl,cp : string;      // łańcuchy do znaków ramek

// Procedura wypisuje drzewo
//--------------------------
procedure printBT(sp,sn : string; v : PAVLNode);
var
  s : string;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then s[length(s) - 1] := ' ';
    printBT(s+cp,cr,v^.right);

    s := Copy(sp,1,length(sp)-2);
    writeln(s,sn,v^.key,':',v^.bf);

    s := sp;
    if sn = cl then s[length(s) - 1] := ' ';
    printBT(s+cp,cl,v^.left);
  end
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PAVLNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end
end;

// Rotacja RR
//-----------
procedure RR(var root : PAVLNode; A : PAVLNode);
var
  B,p : PAVLNode;
begin
  B := A^.right; p := A^.up;

  A^.right := B^.left;
  if A^.right <> nil then A^.right^.up := A;

  B^.left := A;
  B^.up := p;
  A^.up := B;

  if p <> nil then
  begin
    if p^.left = A then p^.left := B else p^.right := B;
  end
  else root := B;

  if B^.bf = -1 then
  begin
    A^.bf := 0; B^.bf := 0;
  end
  else
  begin
    A^.bf := -1; B^.bf := 1;
  end
end;

// Rotacja LL
//-----------
procedure LL(var root : PAVLNode; A : PAVLNode);
var
  B,p : PAVLNode;
begin
  B := A^.left; p := A^.up;

  A^.left := B^.right;
  if A^.left <> nil then A^.left^.up := A;

  B^.right := A;
  B^.up := p;
  A^.up := B;

  if p <> nil then
  begin
    if p^.left = A then p^.left := B else p^.right := B;
  end
  else root := B;

  if B^.bf = 1 then
  begin
    A^.bf := 0; B^.bf := 0;
  end
  else
  begin
    A^.bf := 1; B^.bf := -1;
  end
end;

// Rotacja RL
//-----------
procedure RL(var root : PAVLNode; A : PAVLNode);
var
  B,C,p : PAVLNode;
begin
  B := A^.right; C := B^.left; p := A^.up;

  B^.left := C^.right;
  if B^.left <> nil then B^.left^.up := B;

  A^.right := C^.left;
  if A^.right <> nil then A^.right^.up := A;

  C^.left := A;   C^.right := B;
  A^.up   := C;   B^.up    := C;

  C^.up := p;

  if p <> nil then
  begin
    if p^.left = A then p^.left := C else p^.right := C;
  end
  else root := C;

  if C^.bf = -1 then A^.bf :=  1 else A^.bf := 0;
  if C^.bf =  1 then B^.bf := -1 else B^.bf := 0;

  C^.bf := 0;
end;

// Rotacja LR
//-----------
procedure LR(var root : PAVLNode; A : PAVLNode);
var
  B,C,p : PAVLNode;
begin
  B := A^.left; C := B^.right; p := A^.up;

  B^.right := C^.left;
  if B^.right <> nil then B^.right^.up := B;

  A^.left := C^.right;
  if A^.left <> nil then A^.left^.up := A;

  C^.right := A;   C^.left := B;
  A^.up    := C;   B^.up   := C;

  C^.up := p;

  if p <> nil then
  begin
    if p^.left = A then p^.left := C else p^.right := C;
  end
  else root := C;

  if C^.bf =  1 then A^.bf := -1 else A^.bf := 0;
  if C^.bf = -1 then B^.bf :=  1 else B^.bf := 0;

  C^.bf := 0;
end;

// Wstawia nowy węzeł do drzewa AVL
// root - referencja korzenia
// k    - klucz nowego węzła
//---------------------------------
procedure insertAVL(var root : PAVLNode; k : integer);
var
  w,p,r : PAVLNode;
  t     : boolean;
begin
  new(w);                  // tworzymy dynamicznie nowy węzeł
  w^.left  := nil;         // inicjujemy pola
  w^.right := nil;
  w^.up    := nil;
  w^.key   := k;
  w^.bf    := 0;

  //----------------------------------------
  // FAZA 1 - wstawienie węzła do drzewa AVL
  //----------------------------------------

  p := root;               // rozpoczynamy od korzenia

  if p = nil then          // jeśli drzewo jest puste, to węzeł w
    root := w              // umieszczamy w korzeniu
  else
  begin                    // inaczej szukamy miejsce dla w
    while true do
      if k < p^.key then   // porównujemy klucze
      begin
        if p^.left = nil then // jeśli p nie posiada lewego syna, to
        begin
          p^.left := w;    // lewym synem p staje się węzeł w
          break;           // wychodzimy z pętli
        end;
        p := p^.left;      // inaczej przechodzimy do lewego syna
      end
      else
      begin
        if p^.right = nil then // jeśli p nie posiada prawego syna, to
        begin
          p^.right := w;   // prawym synem staje się węzeł w
          break;           // wychodzimy z pętli
        end;
        p := p^.right;     // inaczej przechodzimy do prawego syna
      end;

    w^.up := p;            // ojcem w jest p

    //---------------------------------
    // FAZA 2 - równoważenie drzewa AVL
    //---------------------------------

    if p^.bf then
      p^.bf := 0           // UWAGA NR 1
    else
    begin
      if p^.left = w then  // UWAGA NR 2
        p^.bf := 1
      else
        p^.bf := -1;

      r := p^.up;          // będziemy szli w górę drzewa w kierunku korzenia
                           // r i p wskazują ojca i syna na tej ścieżce
      t := false;
      while r <> nil do
      begin
        if r^.bf then
        begin
          t := true;       // ustalamy wynik pętli
          break;           // przerywamy pętlę
        end;
                           // inaczej modyfikujemy r.bf
        if r^.left = p then r^.bf :=  1
        else                r^.bf := -1;

        p := r;            // przechodzimy w górę na wyższy poziom
        r := r^.up;
      end;

      if t then            // jeśli r.bf = +/- 1, to musimy
      begin                // równoważyć drzewo
        if r^.bf = 1 then
        begin
          if r^.right = p then r^.bf := 0  // gałęzie się równoważą
          else if p^.bf = -1 then LR(root,r)
          else                    LL(root,r);
        end
        else
        begin              // r.bf = -1
          if r^.left = p then r^.bf := 0  // gałęzie się równoważą
          else if p^.bf = 1 then RL(root,r)
          else                   RR(root,r);
        end;
      end;
    end;
  end;
end;

// Funkcja znajduje poprzednik węzła p
//------------------------------------
function predAVL(p : PAVLNode) : PAVLNode;
var
  r : PAVLNode;
begin
  if p <> nil then
  begin
    if p^.left <> nil then
    begin
      p := p^.left;
      while p^.right <> nil do p := p^.right;
    end
    else
    repeat
      r := p;
      p := p^.up;
    until (p = nil) or (p^.right = r);
  end;
  predAVL := p;
end;

// Funkcja szuka w drzewie AVL węzła o zadanym kluczu.
// Jeśli go znajdzie, zwraca jego wskazanie. Jeżeli nie,
// to zwraca wskazanie puste.
// Parametrami są:
// p - wskazanie korzenia drzewa AVL
// k - klucz poszukiwanego węzła
//----------------------------------------------------
function findAVL(p : PAVLNode; k : integer) : PAVLNode;
begin

  while (p <> nil) and (p^.key <> k) do
    if k < p^.key then p := p^.left
    else               p := p^.right;

  findAVL := p;
end;

// Funkcja usuwa rekurencyjnie węzeł x
// root - referencja do zmiennej z adresem korzenia
// x - wskazanie usuwanego węzła
//-------------------------------------------------
function removeAVL(var root : PAVLNode; x : PAVLNode) : PAVLNode;
var
  t,y,z : PAVLNode;
  nest  : boolean;

begin
  if (x^.left <> nil) and (x^.right <> nil) then
  begin
    y    := removeAVL(root,predAVL(x));
    nest := false;
  end
  else
  begin
    if x^.left <> nil then
    begin
      y := x^.left; x^.left := nil;
    end
    else
    begin
      y := x^.right; x^.right := nil;
    end;
    x^.bf := 0;
    nest  := true;
  end;

  if y <> nil then
  begin
    y^.up := x^.up;
    y^.left  := x^.left;  if y^.left  <> nil then y^.left^.up  := y;
    y^.right := x^.right; if y^.right <> nil then y^.right^.up := y;
    y^.bf := x^.bf;
  end;
    
  if x^.up <> nil then
  begin
    if x^.up^.left = x then x^.up^.left := y else x^.up^.right := y;
  end
  else root := y;
    
  if nest then
  begin
    z := y;
    y := x^.up;
    while y <> nil do
    begin
      if y^.bf = 0 then
      begin              // Przypadek nr 1
        if y^.left = z then y^.bf := -1 else y^.bf := 1;
        break;
      end
      else
      begin
        if ((y^.bf = 1) and (y^.left = z)) or ((y^.bf = -1) and (y^.right = z)) then
        begin           // Przypadek nr 2
          y^.bf := 0;
          z := y; y := y^.up;
        end
        else
        begin
          if y^.left = z then t := y^.right else t := y^.left;
          if t^.bf = 0 then
          begin         // Przypadek 3A
            if y^.bf = 1 then LL(root,y) else RR(root,y);
            break;                      
          end
          else if y^.bf = t^.bf then
          begin         // Przypadek 3B
            if y^.bf = 1 then LL(root,y) else RR(root,y);
            z := t; y := t^.up;
          end
          else
          begin         // Przypadek 3C
            if y^.bf = 1 then LR(root,y) else RL(root,y);
            z := y^.up; y := z^.up;
          end
        end
      end
    end
  end;
  removeAVL := x;
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

var
  Tk   : array[0..31] of integer;  // tablica kluczy węzłów
  i,x,i1,i2  : integer;
  root : PAVLNode;                 // korzeń drzewa AVL

begin
  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;            // Inicjujemy generator pseudolosowy

  root := nil;          // Tworzymy puste drzewo AVL

  for i := 0 to 31 do   // Tablicę wypełniamy wartościami kluczy
    Tk[i] := i + 1;

  for i := 1 to 300 do  // Mieszamy tablicę
  begin
    i1 := random(32);   // Losujemy 2 indeksy
    i2 := random(32);

    x := Tk[i1];        // Wymieniamy Tk[i1] <-->. Tk[i2]
    Tk[i1] := Tk[i2];
    Tk[i2] := x;
  end;

  for i := 0 to 31 do   // Na podstawie tablicy tworzymy drzewo AVL
  begin
    write(Tk[i],' ');
    insertAVL(root,Tk[i]);
  end;

  writeln; writeln;

  printBT('','',root);  // Wyświetlamy zawartość drzewa AVL

  writeln; writeln;

  for i := 1 to 300 do  // Ponownie mieszamy tablicę
  begin
    i1 := random(32); i2 := random(32);
    x := Tk[i1]; Tk[i1] := Tk[i2]; Tk[i2] := x;
  end;

  for i := 0 to 14 do   // Usuwamy 15 węzłów
  begin
    write(Tk[i],' ');
    removeAVL(root,findAVL(root,Tk[i]));
  end;

  writeln; writeln;

  printBT('','',root);  // Wyświetlamy zawartość drzewa AVL

  DFSRelease(root);     // Usuwamy drzewo AVL z pamięci

end.
Code::Blocks
// Drzewo AVL
// Data: 22.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja typu węzłów drzewa AVL
//---------------------------------
struct AVLNode
{
  AVLNode * up, * left, * right;
  int key, bf;
};

// Zmienne globalne
//-----------------

string cr,cl,cp;      // łańcuchy do znaków ramek

// Procedura wypisuje drzewo
//--------------------------
void printBT(string sp, string sn, AVLNode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr) s[s.length() - 2] = ' ';
    printBT(s + cp, cr, v->right);

    s = s.substr(0,sp.length()-2);
    cout << s << sn << v->key << ":" << v->bf << endl;

    s = sp;
    if(sn == cl) s[s.length() - 2] = ' ';
    printBT(s + cp, cl, v->left);
  }
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(AVLNode * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// Rotacja RR
//-----------
void RR(AVLNode * & root, AVLNode * A)
{
  AVLNode * B = A->right, * p = A->up;

  A->right = B->left;
  if(A->right) A->right->up = A;

  B->left = A;
  B->up = p;
  A->up = 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;
  }
}

// Rotacja LL
//-----------
void LL(AVLNode * & root, AVLNode * A)
{
  AVLNode * B = A->left, * p = A->up;

  A->left = B->right;
  if(A->left) A->left->up = A;

  B->right = A;
  B->up = p;
  A->up = 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;
  }
}

// Rotacja RL
//-----------
void RL(AVLNode * & root, AVLNode * A)
{
  AVLNode * B = A->right, * C = B->left, * p  = A->up;

  B->left = C->right;
  if(B->left) B->left->up = B;

  A->right = C->left;
  if(A->right) A->right->up = A;

  C->left = A;
  C->right = B;
  A->up = B->up = C;
  C->up = p;

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

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

  C->bf = 0;
}

// Rotacja LR
//-----------
void LR(AVLNode * & root, AVLNode * A)
{
  AVLNode * B = A->left, * C = B->right, * p = A->up;

  B->right = C->left;
  if(B->right) B->right->up = B;

  A->left = C->right;
  if(A->left) A->left->up = A;

  C->right = A;
  C->left = B;
  A->up = B->up = C;
  C->up = p;

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

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

  C->bf = 0;
}

// Wstawia nowy węzeł do drzewa AVL
// root - referencja korzenia
// k    - klucz nowego węzła
//---------------------------------
void insertAVL(AVLNode * & root, int k)
{
  AVLNode * w,* p,* r;
  bool t;

  w = new AVLNode;        // tworzymy dynamicznie nowy węzeł
  w->left = w->right = w->up = NULL;
  w->key  = k;
  w->bf  = 0;

  //----------------------------------------
  // FAZA 1 - wstawienie węzła do drzewa AVL
  //----------------------------------------

  p = root;              // rozpoczynamy od korzenia

  if(!p) root = w;       // jeśli drzewo jest puste, to węzeł w umieszczamy w korzeniu
  else
  {                      // inaczej szukamy miejsce dla w
    while(true)
      if(k < p->key)     // porównujemy klucze
      {
        if(!p->left)     // jeśli p nie posiada lewego syna, to
        {
          p->left = w;   // lewym synem p staje się węzeł w
          break;         // wychodzimy z pętli
        }
        p = p->left;     // inaczej przechodzimy do lewego syna
      }
      else
      {
        if(!p->right)    // jeśli p nie posiada prawego syna, to
        {
          p->right = w;  // prawym synem staje się węzeł w
          break;         // wychodzimy z pętli
        }
        p = p->right;    // inaczej przechodzimy do prawego syna
      }

    w->up = p;           // ojcem w jest p

    //---------------------------------
    // FAZA 2 - równoważenie drzewa AVL
    //---------------------------------

    if(p->bf) p->bf = 0; // UWAGA NR 1
    else
    {
      if(p->left == w)   // UWAGA NR 2
        p->bf = 1;
      else
        p->bf = -1;

      r = p->up;        // będziemy szli w górę drzewa w kierunku korzenia
                        // r i p wskazują ojca i syna na tej ścieżce
      t = false;
      while(r)
      {
        if(r->bf)
        {
          t = true;     // ustalamy wynik pętli
          break;        // przerywamy pętlę
        };
                        // inaczej modyfikujemy r.bf
        if(r->left == p) r->bf =  1;
        else             r->bf = -1;

        p = r;          // przechodzimy w górę na wyższy poziom
        r = r->up;
      }

      if(t)             // jeśli r.bf = +/- 1, to musimy
      {                 // równoważyć drzewo
        if(r->bf == 1)
        {
          if(r->right == p) r->bf = 0;  // gałęzie się równoważą
          else if(p->bf == -1) LR(root,r);
          else                 LL(root,r);
        }
        else
        {              // r.bf = -1
          if(r->left == p) r->bf = 0;  // gałęzie się równoważą
          else if(p->bf == 1) RL(root,r);
          else                RR(root,r);
        }
      }
    }
  }
}

// Funkcja znajduje poprzednik węzła p
//------------------------------------
AVLNode * predAVL(AVLNode * p)
{
  AVLNode * r;

  if(p)
  {
    if(p->left)
    {
      p = p->left;
      while(p->right) p = p->right;
    }
    else
      do
      {
        r = p;
        p = p->up;
      } while(p && p->right != r);
  }
  return p;
}

// Funkcja szuka w drzewie AVL węzła o zadanym kluczu.
// Jeśli go znajdzie, zwraca jego wskazanie. Jeżeli nie,
// to zwraca wskazanie puste.
// Parametrami są:
// p - wskazanie korzenia drzewa AVL
// k - klucz poszukiwanego węzła
//----------------------------------------------------
AVLNode * findAVL(AVLNode * p, int k)
{
  while(p && p->key != k)
    p = (k < p->key) ? p->left: p->right;

  return p;
}

// Funkcja usuwa rekurencyjnie węzeł x
// root - referencja do zmiennej z adresem korzenia
// x - wskazanie usuwanego węzła
//-------------------------------------------------
AVLNode * removeAVL(AVLNode * & root, AVLNode * x)
{
  AVLNode  *t,*y,*z;
  bool nest;

  if(x->left && x->right)
  {
    y    = removeAVL(root,predAVL(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->up    = x->up;
    y->left  = x->left;  if(y->left)  y->left->up  = y;
    y->right = x->right; if(y->right)  y->right->up = y;
    y->bf    = x->bf;
  }

  if(x->up)
  {
    if(x->up->left == x) x->up->left = y; else x->up->right = y;
  }
  else root = y;

  if(nest)
  {
    z = y;
    y = x->up;
    while(y)
    {
      if(!y->bf)
      {              // Przypadek nr 1
        if(y->left == z)  y->bf = -1; else y->bf = 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->up;
        }
        else
        {
          if(y->left == z)  t = y->right; else t = y->left;
          if(!t->bf)
          {         // Przypadek 3A
            if(y->bf == 1) LL(root,y); else RR(root,y);
            break;
          }
          else if(y->bf == t->bf)
          {         // Przypadek 3B
            if(y->bf == 1) LL(root,y); else RR(root,y);
            z = t; y = t->up;
          }
          else
          {         // Przypadek 3C
            if(y->bf == 1) LR(root,y); else RL(root,y);
            z = y->up; y = z->up;
          }
        }
      }
    }
  }
  return x;
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

int main()
{
  int Tk[32];   // tablica kluczy węzłów
  int i,x,i1,i2;
  AVLNode * root = NULL;

  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  srand(time(NULL));        // inicjujemy generator pseudolosowy

  for(i = 0; i < 32; i++)   // Tablicę wypełniamy wartościami kluczy
    Tk[i] = i + 1;

  for(i = 0; i < 300; i++)  // Mieszamy tablicę
  {
    i1 = rand() % 32;       // Losujemy 2 indeksy
    i2 = rand() % 32;

    x = Tk[i1];             // Wymieniamy Tk[i1] <--> Tk[i2]
    Tk[i1] = Tk[i2];
    Tk[i2] = x;
  }

  for(i = 0; i < 32; i++)   // Na podstawie tablicy tworzymy drzewo AVL
  {
    cout << Tk[i] << " ";
    insertAVL(root,Tk[i]);
  }

  cout << endl << endl;

  printBT("","",root);      // Wyświetlamy zawartość drzewa AVL

  cout << endl << endl;

  for(i = 0; i < 300; i++)  // Ponownie mieszamy tablicę
  {
    i1 = rand() % 32; i2 = rand() % 32;
    x = Tk[i1]; Tk[i1] = Tk[i2]; Tk[i2] = x;
  }

  for(i = 0; i < 15; i++)    // Usuwamy 15 węzłów
  {
    cout << Tk[i] << " ";
    removeAVL(root,findAVL(root,Tk[i]));
  }

  cout << endl << endl;

  printBT("","",root);      // Wyświetlamy zawartość drzewa AVL

  DFSRelease(root);         // Usuwamy drzewo AVL z pamięci

  return 0;
}
Free Basic
' Drzewo AVL
' Data: 22.05.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Definicja typu węzłów drzewa AVL
'---------------------------------
Type AVLNode
  up As AVLNode Ptr
  Left As AVLNode Ptr
  Right As AVLNode Ptr
  key As Integer
  bf As Integer
End Type

' Zmienne globalne
'-----------------
Dim Shared As String * 2 cr,cl,cp ' łańcuchy do ramek

' Procedura wypisuje drzewo
'--------------------------
Sub printBT(sp As String, sn As String, v As AVLNode Ptr)

  Dim As String s

  If v Then
    s = sp
    If sn = cr Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cr, v->Right)

    s = Mid(s,1, Len(sp)-2)
    Print Using "&&&:&";s;sn;v->key;v->bf

    s = sp
    If sn = cl Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cl, v->Left)
  End If
End Sub

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease(v As AVLNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' Rotacja RR
'-----------
Sub RR(ByRef root As AVLNode Ptr, ByVal A As AVLNode Ptr)
	
  Dim As AVLNode Ptr B = A->right, p = A->up

  A->right = B->Left
  If A->Right Then A->right->up = A

  B->left = A
  B->up = p
  A->up = B

  If p Then
    if p->left = A Then
    	p->left = B
    Else
    	p->right = B
    End If
  Else
    root = B
  End If

  If B->bf = -1 Then
  	 A->bf =  0: B->bf = 0
  Else
    A->bf = -1: B->bf = 1
  End If
End Sub

' Rotacja LL
'-----------
Sub LL(ByRef root As avlNode Ptr, ByVal A As AVLNode Ptr)

  Dim As AVLNode Ptr B = A->left, p = A->up

  A->left = B->Right
  If A->left Then A->left->up = A

  B->right = A
  B->up = p
  A->up = B

  If p Then
    If p->left = A Then
    	p->left = B
    Else
    	p->right = B
    End If
  Else
    root = B
  End If

  if B->bf = 1 Then
  	 A->bf = 0: B->bf = 0
  Else
    A->bf = 1: B->bf = -1
  End If
End Sub

' Rotacja RL
'-----------
Sub RL(ByRef root As AVLNode Ptr, ByVal A As AVLNode Ptr)
	
  Dim As AVLNode Ptr B = A->right, C = B->left, p = A->up

  B->left = C->Right
  if B->left Then B->left->up = B

  A->right = C->Left
  If A->Right Then A->right->up = A

  C->left = A
  C->right = B
  A->up = C
  B->up = C
  C->up = p

  If p Then
    if p->left = A Then
    	p->left = C
    Else
    	p->right = C
    End If
  Else
    root = C
  End If

  If C->bf = -1 Then A->bf = 1: Else A->bf = 0
  If C->bf =  1 Then B->bf = -1: Else B->bf = 0
  C->bf = 0
End Sub

' Rotacja LR
'-----------
sub LR(ByRef root As AVLNode Ptr, ByVal A As AVLNode Ptr)

  Dim As AVLNode Ptr B = A->left, C = B->right, p = A->up

  B->right = C->Left
  If B->right Then B->right->up = B

  A->left = C->Right
  if A->left Then A->left->up = A

  C->right = A
  C->left = B
  A->up = C
  B->up = C
  C->up = p

  if p Then
    If p->left = A Then p->left = C: else p->right = C
  Else
    root = C
  End If

  If C->bf =  1 Then A->bf = -1: Else A->bf = 0
  If C->bf = -1 Then B->bf =  1: Else B->bf = 0

  C->bf = 0
End Sub

' Wstawia nowy węzeł do drzewa AVL
' root - referencja korzenia
' k    - klucz nowego węzła
'---------------------------------
sub insertAVL(ByRef root As AVLNode Ptr, k As Integer)
	
  Dim As AVLNode Ptr w,p,r
  Dim As Integer t

  w = new AVLNode        ' tworzymy dynamicznie nowy węzeł
  w->left  = 0
  w->right = 0
  w->up    = 0
  w->key   = k
  w->bf    = 0

  '----------------------------------------
  ' FAZA 1 - wstawienie węzła do drzewa AVL
  '----------------------------------------

  p = root              ' rozpoczynamy od korzenia

  If p = 0 Then
  	 root = w            ' jeśli drzewo jest puste, to węzeł w umieszczamy w korzeniu
  Else                  ' inaczej szukamy miejsce dla w                   
    While 1
      If k < p->key Then' porównujemy klucze
        If p->Left = 0 Then ' jeśli p nie posiada lewego syna, to
          p->left = w   ' lewym synem p staje się węzeł w
          Exit While    ' wychodzimy z pętli
        End If
        p = p->Left     ' inaczej przechodzimy do lewego syna
      Else
        If p->Right = 0 Then ' jeśli p nie posiada prawego syna, to
          p->right = w  ' prawym synem staje się węzeł w
          Exit While    ' wychodzimy z pętli
        End If
        p = p->Right    ' inaczej przechodzimy do prawego syna
      End If
    Wend

    w->up = p           ' ojcem w jest p

    '---------------------------------
    ' FAZA 2 - równoważenie drzewa AVL
    '---------------------------------

    If p->bf Then
    	p->bf = 0         ' UWAGA NR 1
    Else                ' UWAGA NR 2
      If p->left = w Then p->bf = 1: Else p->bf = -1

      r = p->up         ' będziemy szli w górę drzewa w kierunku korzenia
                        ' r i p wskazują ojca i syna na tej ścieżce
      t = 0
      While r
        If r->bf Then
          t = 1         ' ustalamy wynik pętli
          Exit While    ' przerywamy pętlę
        End If
                        ' inaczej modyfikujemy r.bf
        If r->left = p Then r->bf = 1: Else r->bf = -1

        p = r           ' przechodzimy w górę na wyższy poziom
        r = r->up
      Wend

      If t = 1 Then     ' jeśli r.bf = +/- 1, to musimy równoważyć drzewo
        If r->bf = 1 Then
          If r->right = p Then
          	r->bf = 0   ' gałęzie się równoważą
          ElseIf p->bf = -1 Then
            LR(root,r)
          Else
            LL(root,r)
          End If
        Else            ' r.bf = -1
          If r->left = p Then
            r->bf = 0  ' gałęzie się równoważą
          ElseIf p->bf = 1 Then
            RL(root,r)
          Else
            RR(root,r)
          End If
        End If
      End If
    End If
  End If
End Sub

' Funkcja znajduje poprzednik węzła p
'------------------------------------
Function predAVL(ByVal p As AVLNode Ptr) As AVLNode Ptr

  Dim As AVLNode Ptr r

  If p Then
    If p->Left Then
      p = p->Left
      While p->Right
      	p = p->Right
      Wend
    Else
      Do
        r = p
        p = p->up
      Loop Until p = 0 OrElse p->Right = r
    End If 
  End If

  Return p
  
End Function

' Funkcja szuka w drzewie AVL węzła o zadanym kluczu.
' Jeśli go znajdzie, zwraca jego wskazanie. Jeżeli nie,
' to zwraca wskazanie puste.
' Parametrami są:
' p - wskazanie korzenia drzewa AVL
' k - klucz poszukiwanego węzła
'----------------------------------------------------
Function findAVL(p As AVLNode Ptr, k As Integer) As AVLNode Ptr

  While (p <> 0) AndAlso (p->key <> k)
    If k < p->key Then
    	p = p->Left
    Else
    	p = p->Right
    End If
  Wend
  
  Return p
  
End Function

' Funkcja usuwa rekurencyjnie węzeł x
' root - referencja do zmiennej z adresem korzenia
' x - wskazanie usuwanego węzła
'-------------------------------------------------
Function removeAVL(ByRef root As AVLNode Ptr, x As AVLNode Ptr) As AVLNode Ptr

  Dim As AVLNode Ptr t,y,z
  Dim As Integer nest

  If (x->Left <> 0) And (x->Right <> 0) Then
    y    = removeAVL(root,predAVL(x))
    nest = 0
  Else
    If x->Left Then
      y = x->left: x->left = 0
    Else
      y = x->right: x->right = 0
    End If
    x->bf = 0
    nest  = 1
  End If

  If y Then
    y->up    = x->up
    y->left  = x->left:  If y->Left  Then y->left->up  = y
    y->right = x->right: If y->Right Then y->right->up = y
    y->bf    = x->bf
  End If

  If x->up Then
    If x->up->left = x then x->up->left = y: Else x->up->right = y
  Else
    root = y
  End If

  If nest = 1 Then
    z = y
    y = x->up
    While y
      If y->bf = 0 Then ' Przypadek nr 1
        If y->left = z then y->bf = -1: else y->bf = 1
        Exit While
      Else
        If ((y->bf = 1) AndAlso (y->left = z)) OrElse _
        	  ((y->bf = -1) AndAlso (y->right = z)) Then ' Przypadek nr 2
          y->bf = 0
          z = y: y = y->up
        Else
          If y->left = z Then t = y->right: Else t = y->Left
          If t->bf = 0 then ' Przypadek 3A
            If y->bf = 1 Then LL(root,y): Else RR(root,y)
            Exit While
          ElseIf y->bf = t->bf Then ' Przypadek 3B
            If y->bf = 1 Then LL(root,y): Else RR(root,y)
            z = t: y = t->up
          Else ' Przypadek 3C
            If y->bf = 1 Then LR(root,y): Else RL(root,y)
            z = y->up: y = z->up
          End If
        End If
      End If
    Wend
  End If
  Return x
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer Tk(31)    ' tablica kluczy węzłów
Dim As Integer i,i1,i2
Dim As AVLNode Ptr root = 0

' ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
' wstawiać znaki konsoli do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218) + Chr(196)
cl = Chr(192) + Chr(196)
cp = Chr(179) + " "

Randomize                ' Inicjujemy generator pseudolosowy

For i = 0 To 31          ' Tablicę wypełniamy wartościami kluczy
  Tk(i) = i + 1
Next

For i = 1 To 300         ' Mieszamy tablicę
  i1 = Int(Rnd() * 32)   ' Losujemy 2 indeksy
  i2 = Int(Rnd() * 32)
  Swap Tk(i1),Tk(i2)     ' Wymieniamy Tk[i1] <--> Tk[i2]
Next

For i = 0 To 31          ' Na podstawie tablicy tworzymy drzewo AVL
  Print Tk(i);
  insertAVL(root,Tk(i))
Next

Print: Print

printBT("","",root)      ' Wyświetlamy zawartość drzewa AVL

Print: Print

For i = 1 To 300         ' Ponownie ieszamy tablicę
  i1 = Int(Rnd() * 32): i2 = Int(Rnd() * 32)
  Swap Tk(i1),Tk(i2)
Next

For i = 0 To 14          ' Usuwamy 15 węzłów
  Print Tk(i);
  removeAVL(root,findAVL(root,Tk(i)))
Next

Print: Print

printBT("","",root)      ' Wyświetlamy zawartość drzewa AVL

DFSRelease(root)         ' Usuwamy drzewo BST z pamięci

End
Wynik
 23 3 26 11 4 2 28 9 7 10 5 18 20 21 12 15 25 17 30 6 29 19 16 14 22 13 1 24 31 32 8 27

        ┌─32:0
      ┌─31:0
      │ └─30:0
    ┌─29:0
    │ └─28:1
    │   └─27:0
  ┌─26:-1
  │ └─25:1
  │   └─24:0
┌─23:-1
│ │   ┌─22:0
│ │ ┌─21:-1
│ └─20:-1
│   └─19:0
18:0
│   ┌─17:1
│   │ └─16:0
│ ┌─15:1
│ │ │   ┌─14:0
│ │ │ ┌─13:0
│ │ │ │ └─12:0
│ │ └─11:-1
│ │   └─10:0
└─9:0
  │     ┌─8:0
  │   ┌─7:-1
  │ ┌─6:-1
  │ │ └─5:0
  └─4:-1
    │ ┌─3:0
    └─2:0
      └─1:0


3 23 12 2 17 27 24 31 13 6 10 15 16 1 8

      ┌─32:0
    ┌─30:-1
  ┌─29:-1
  │ └─28:0
┌─26:0
│ │ ┌─25:0
│ └─22:1
│   │ ┌─21:0
│   └─20:0
│     └─19:0
18:-1
│ ┌─14:1
│ │ └─11:0
└─9:0
  │ ┌─7:0
  └─5:0
    └─4:0

 

 


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

©2019 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