Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Drzewa AVL

SPIS TREŚCI
Podrozdziały

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 ( log 2 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 ( log 2n ), 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  = h L  - h R

gdzie: h L  i h R  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, h L  > h R

bf  =  0 – oba poddrzewa są równej wysokości, h L  = h R

bf  = -1 – prawe poddrzewo jest wyższe o jeden poziom od lewego poddrzewa, h L  < h R

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
Drzewo spełnia własność AVL
     obrazek
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:

h L  = 0
h R  = 2

bf
  = h L  - h R  = 0 - 2 = -2

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

Pascal
type
  PAVLNode = ^AVLNode;
  AVLNode  = record
    up    : PAVLNode;
    left  : PAVLNode;
    right : PAVLNode;
    key   : typ_danych;
    bf    : integer;
  end;
   C++
struct AVLNode
{
  AVLNode * up;
  AVLNode * left;
  AVLNode * right;
  typ_danych key;
  int bf;
};
   Basic
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.

Na początek:  podrozdziału   strony 

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  = h BL - h BR,      B.bf  = -1,       h BL - h BR = -1,     h BR = h BL + 1

Oznaczmy wysokość lewego poddrzewa węzła B przez h, czyli h BL = h. Wtedy prawe poddrzewo węzła B będzie posiadało wysokość h BR = 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:

h B = 1 + max ( h BL, h BR )

U nas najwyższe jest prawe poddrzewo, zatem:

h B = 1 + h BR = 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  = h AL - h AR,     A.bf  = -2,     h AL - h AR = -2,     h AL = h AR - 2

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

h AR = h B = h  + 2

I ostatecznie otrzymujemy:

h AL = h AR - 2 = h  + 2 - 2 = h

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

h AL = h
h BL = h
h BR = 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  = h AL - h BL = h  - h  = 0
B.bf  = h A - h BR = 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 kroku 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 kroku K12  
K11: root  ← B 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 kroku 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 kroku K12  
K11: root  ← B 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  = h CL - h CR,     C.bf  = -1,     h CR = h CL + 1

Zatem lżejsze jest poddrzewo lewe. Oznaczmy:

h CL = h
h
CR = h  + 1
h C = h  + 2

Teraz przechodzimy do węzła B:

B.bf  = h BL - h BR,     B.bf  = 1,    h BR = h BL - 1 = h C - 1 = ( h  + 2 ) - 1 = h  + 1
h B = h  + 3

Na koniec pozostaje węzeł A:

A.bf  = h AL - h AR,     A.bf  = -2,     h AL = h AR - 2 = h B - 2 = ( h  + 3 ) - 2 = h  + 1

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

h AL = h  + 1
h BR = h  + 1
h CL = h
h CR = h  + 1

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

A.bf  = h AL - h CL = ( h  + 1 ) - h  = 1
B.bf  = h A - h C = ( h  + 2 ) - ( h  + 2 ) = 0
C.bf  = h CR - h BR = ( 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 kroku 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 kroku K17  
K16: root  ← C 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 kroku 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 kroku K17  
K16: root  ← C 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  
Na początek:  podrozdziału   strony 

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
Zmienne 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: p  ← root  
K08: Jeśli p  = nil,
to root  ← w  i zakończ
sprawdzamy, czy drzewo jest puste
K09: Jeśli k  < ( pkey  ),
to idź do kroku K13
porównujemy klucze
K10: Jeśli ( pright  ) = nil,
to ( pright  ) ← w
    i idź do kroku 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 kroku K09 i kontynuujemy pętlę
K13 Jeśli ( pleft  ) = nil, to: ( pleft  ) ← w
    Idź do kroku K16
to samo dla lewego syna
K14: p  ← ( pleft  )  
K15: Idź do kroku K09  
K16: ( wup  ) ← p uzupełniamy ojca węzła
K17: Jeśli ( pbf  ) = 0,
to idź do kroku 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 r  ≠ nil:
wykonuj kroki K23...K26
wskazania r i p to ojciec i syn na tej ścieżce
K23:     Jeśli ( rbf  ) ≠ 0,
    to idź do kroku 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:     p  ← r przemieszczamy się w górę drzewa
K26:     r  ← ( rup  )  
K27: Zakończ  
K28: Jeśli ( rbf  ) = -1,
to idź do kroku 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  ).

Wstawianie węzła

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.

Na początek:  podrozdziału   strony 

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

obrazek

obrazek

obrazek

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.
Zmienne 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 kroku 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 kroku 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 kroku 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 kroku 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: root  ← y inaczej y wstawiamy do korzenia
K19: Jeśli nest  = false,
to idź
do kroku K43
sprawdzamy zagnieżdżenie
K20: z  ← y ustawiamy wskaźniki, będziemy szli w kierunku korzenia drzewa
K21: y  ← ( xup  )  
K22: Dopóki y  ≠ nil,
wykonuj
kroki K23...K42
w pętli sprawdzamy różne przypadki
K23:     Jeśli ( ybf  ) ≠ 0,
    to idź do kroku 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 kroku K31
 
K27: ( ybf  ) ← 0 przypadek 2
K28:     z  ← y 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 kroku K35
 
K33:     Jeśli ( ybf  ) = 1,
    to LL ( root, y  )
    Inaczej RR ( root, y  )
przypadek 3A
K34:     Idź do kroku K43 przerywamy pętlę
K35:     Jeśli ( ybf  ) ≠ ( tbf  ),
    to idź do kroku K40
 
K36:     Jeśli ( ybf  ) = 1,
    to LL ( root, y  )
    inaczej RR ( root, y  )
przypadek 3B
K37:     z  ← t 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  

Przykładowe programy

Uwaga:

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.
Pascal
// 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.
C++
// 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;
}
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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.