Drzewo AVL - Algorytm

Z jej treści możemy dowiedzieć się więcej na takie tematy, jak: czym jest drzewo AVL, wstawianie dokumentu do drzewa AVL, algorytm wstawiana operacji dla drzew AVL. Notatka zawiera odpowiednie wzory i rysunki.

Drzewa AVL (Adelson-Wielskij, Łandis)
najstarsza postać drzew zrównoważonych
Drzewo AVL to drzewo binarnych poszukiwań, w którym dla każdego wierzchołka v wysokości poddrzew drzewa o korzeniu v różnią się co najwyżej o 1.
Reprezentacja:
w każdym węźle:
info, left, right - jak dla zwykłych BST bal (balance - współczynnik zrównoważenia):
bal(v)=h(prawe_podrz(v))-h(lewe_poddrz(v))
Jeśli drzewo BST jest AVL, to dla każdego węzła v, bal(v) = +1, jeśli poddrzewo prawe w węźle v wyższe niż lewe, bal(v) = -1, jeśli lewe wyższe, bal(v) = 0, jeśli oba poddrzewa równej wysokości.
Twierdzenie. Wysokość drzewa AVL o n wierzchołkach nie przekracza 1.45 log n = Θ(log n).
Dowód:
Jeśli BST ma n wierzchołków, to ma N = n+1 liści zewnętrznych (pustych poddrzew, czyli odsyłaczy NIL).
Niech N(h) = najmniejsza możliwa liczba liści zewnętrznych w drzewie AVL o wysokości h.
N(0) = 2 N(1) = 3 N(2) = 5, Fakt: N(h) = N(h-1)+N(h-2)
gdyż minimalne drzewo AVL o wysokości h powstaje z dołączenia do korzenia dwóch minimalnych drzew AVL, o wysokości (h-1) i (h-2), a liczba liści zewnętrznych w tak powstałym drzewie jest sumą liści zewnętrznych w obu poddrzewach.
Zatem: N(h) = F(h+3), gdzie F(i) jest i-tą liczbą Fibonacciego.
Własność liczb Fibonacciego:
∅ k-2 ≤ F(k) ≤ ∅ k-1 gdzie ∅ = (1 + √ 5)/2 (złoty podział)
Z pierwszej nierówności:
∅h+1 ≤ N(h) = h+1 ≤ log∅N(h) = h ≤ 1.45 log(n+1)-1≤ 1.45 log n,
QED
Operacja wstawienia elementu do drzewa AVL:
wykonaj wstawienie jak dla zwykłego BST
przywróć własność AVL, jeśli została zaburzona
Przywracanie własności AVL: rotacje.
Rotacja pojedyncza w lewo:
węzeł w (oś rotacji) jest najniżej położonym węzłem w którym współczynnik zrównoważenia jest spoza dopuszczalnego zakresu
h, h+1 oznaczają wysokości poddrzew, x jest elementem którego wstawienie zaburzyło równowagę. Prosty test poprawności:
kolejność inorder przed rotacją: A, w, B, u, C.
kolejność inorder po rotacji: A, w, B, u, C.
a zatem poprawnie.
Rotacja w prawo symetrycznie.
Algorytm rotacji:
procedure rot1L(link &w) // parametr w przekazany przez referencję!
u right(w)
right(w) left(u) left(u) w
w u
end.
Koszt O(1).
... zobacz całą notatkę