OBOWIĄZKOWE DO PRZESŁANIA: 11.1 lub 11.2
Drzewo AVL jest to zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Drzewo wynaleźli w roku 1962 dwaj rosyjscy matematycy Georgy Adelson-Velsky i Evgenii Landis. Każdemu węzłowi można przypisać współczynnik wyważenia (ang. balance factor), który jest równy różnicy wysokości prawego i lewego poddrzewa. W drzewie zrównoważonym współczynnik wyważenia może wynosić -1,0,+1. Przy wstawianiu elementu do drzewa lub usuwaniu elementu współczynnik może chwilowo przyjąć niedozwoloną wartość, ale wtedy wykonuje się pewną liczbę rotacji, które przywracają zrównoważenie drzewa.
Minimalna liczba węzłów w drzewie AVL o wysokości h jest określona
równaniem rekurencyjnym:
AVL(h) = AVL(h-1) + AVL(h-2) + 1,
gdzie AVL(0) = 0, AVL(1) = 1, są to liczby Leonardo.
Stąd otrzymujemy ograniczenie wysokości drzewa h w zależności
od liczby węzłów n:
lg(n+1) <= h < 1.44 lg(n+2) - 0.328.
Liczby Fibonacciego: F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1.
[AVL(h) + 1] = [AVL(h-1) + 1] + [AVL(h-2) + 1],
stąd AVL(h) + 1 = F(h+2), a na F(n) mamy zwarty wzór.
| https://en.wikipedia.org/wiki/AVL_tree | Algorithm | Average | Worst case | | Space | O(n) | O(n) | | Search | O(log n) | O(log n) | | Insert | O(log n) | O(log n) | | Delete | O(log n) | O(log n) |
| https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ | Przykładowe drzewo AVL, w nawiasach współczynniki wyważenia. | balance_factor(node) = height(node->right) - height(node->left) | 12(-1) | | / \ | | 8(-1) 18(-1) | | / \ / | | 5(-1) 11(0) 17(0) | | / | | 4(0) |
Wyszukiwanie działa jak w zwykłym drzewie BST.
Wyszukanie następnika lub poprzednika danego węzła zajmuje w najgorszym przypadku czas O(h) = O(log n). Przejście przez wszystkie węzły drzewa BST wymaga przejścia przez każde łącze dwa razy (w dół i w górę), łączy jest n-1, więc łączny czas wynosi O(n). Czas zamortyzowany znajdowania poprzednika lub następnika w drzewie AVL wynosi 2 × (n-1)/n, a więc w przybliżeniu 2.
W pierwszym etapie wstawiamy element tak jak w zwykłym drzewie BST. Dalej należy uaktualnić współczynniki wyważenia rodziców. Wstawienie jednego węzła może zmienić wysokość poddrzewa co najwyżej o jeden, a współczynnik po wstawieniu może być w zakresie [-2, +2]. Jeżeli po wstawieniu współczynniki są w zakresie [-1, +1], to nie są potrzebne rotacje. Jeżeli współczynnik danego węzła osiągnie wartość -2 lub +2, to potrzebne są rotacje poddrzewa o korzeniu w tym węźle.
Zauważmy, że idąc od wstawionego węzła w górę wystarczy znaleźć pierwszy węzeł, dla którego balance zmienił się na +2 lub -2. Po wykonaniu rotacji nie są potrzebne zmiany powyżej tego węzła.
Jeżeli idąc w górę od wstawionego węzła trafimy na węzeł, którego balance zmienił się na 0, to nie ma potrzeby iść wyżej i robić zmian.
|Wstawienie do prawego poddrzewa prawego dziecka. | | X(+1) X(+2) Y(0) | | / \ / \ / \ | | A Y(0) A Y(+1) X(0) C(-1) | | / \ / \ / \ / | | B C B C(-1) A B D | | / | | D | |Potrzebna rotacja w lewo (X) - L. | |Końcowa wysokość drzewa jest taka jak początkowa. | |Zmiana wysokości poddrzewa nie propaguje się wyżej.| |Tak będzie również w pozostałych przypadkach. |
|Wstawienie do prawego poddrzewa prawego dziecka. | | X(+1) X(+2) Y(0) | | / \ / \ / \ | | A Y(0) A Y(+1) X(0) C(+1) | | / \ / \ / \ \ | | B C B C(+1) A B D | | \ | | D | |Potrzebna rotacja w lewo (X) - L. |
|Wstawienie do lewego poddrzewa prawego dziecka. | | X(+1) X(+2) X(+2) B(0) | | / \ / \ / \ / \ | | A Y(0) A Y(-1) A B(+2) X(-1) Y(0) | | / \ / \ \ / / \ | | B C B(+1) C Y(0) A D C | | \ / \ | | D D C | |Potrzebna rotacja w prawo (Y) i w lewo (X) - RL. |
|Wstawienie do lewego poddrzewa prawego dziecka. | | X(+1) X(+2) X(+2) B(0) | | / \ / \ / \ / \ | | A Y(0) A Y(-1) A B(+1) X(0) Y(+1) | | / \ / \ / \ / \ \ | | B C B(-1) C D Y(+1) A D C | | / \ | | D C | |Potrzebna rotacja w prawo (Y) i w lewo (X) - RL. |
|Wstawienie do lewego poddrzewa lewego dziecka. | | X(-1) X(-2) Y(0) | | / \ / \ / \ | | Y(0) C Y(-1) C A(-1) X(0) | | / \ / \ / / \ | | A B A(-1) B D B C | | / | | D | |Potrzebna rotacja w prawo (X) - R. |
|Wstawienie do lewego poddrzewa lewego dziecka. | | X(-1) X(-2) Y(0) | | / \ / \ / \ | | Y(0) C Y(-1) C A(+1) X(0) | | / \ / \ \ / \ | | A B A(+1) B D B C | | \ | | D | |Potrzebna rotacja w prawo (X) - R. |
|Wstawienie do prawego poddrzewa lewego dziecka. | | X(-1) X(-2) X(-2) B(0) | | / \ / \ / \ / \ | | Y(0) C Y(+1) C B(-2) C Y(0) X(+1) | | / \ / \ / / \ \ | | A B A B(-1) Y(0) A D C | | / / \ | | D A D | |Potrzebna rotacja w lewo (Y) i w prawo (X) - LR. |
|Wstawienie do prawego poddrzewa lewego dziecka. | | X(-1) X(-2) X(-2) B(0) | | / \ / \ / \ / \ | | Y(0) C Y(+1) C B(-2) C Y(-1) X(0) | | / \ / \ / \ / / \ | | A B A B(+1) Y(-1) D A D C | | \ / | | D A | |Potrzebna rotacja w lewo (Y) i w prawo (X) - LR. |
Usuwanie węzła może być bardziej czasochłonne niż wstawianie.
// Szablon dla węzła drzewa AVL.
template <typename T>
struct AVLNode {
// the default access mode and default inheritance mode are public
T value;
int balance;
AVLNode *left, *right, *parent;
// kostruktor domyślny
AVLNode() : value(T()), balance(0),
left(nullptr), right(nullptr), parent(nullptr) {}
AVLNode(const T& item, AVLNode *p) : value(item), balance(0),
left(nullptr), right(nullptr), parent(p) {}
~AVLNode() { delete left; delete right; } // destruktor
};
// Szablon dla drzewa AVL.
template <typename T>
class AVLTree {
public:
AVLTree() : root(nullptr) {}
~AVLTree() { delete root; } // trzeba wyczyścić
void clear() { delete root; root = nullptr; }
bool empty() const { return root == nullptr; }
T& top() { assert(root != nullptr); return root->value; } // podgląd korzenia
bool insert(const T& item);
void remove(const T& item);
T* search(const T& item) const {
auto ptr = search(root, item);
return ((ptr == nullptr) ? nullptr : &(ptr->value));
}
void preorder() { preorder(root); }
void inorder() { inorder(root); }
void postorder() { postorder(root); }
void bfs(); // przejście poziomami (wszerz)
T* find_max() const;
T* find_min() const;
void display() { display(root, 0); }
virtual void visit(AVLNode<T> *node) {
assert(node != nullptr);
std::cout << "visiting " << node->value << std::endl;
}
private:
// uzupełnić ...
https://rosettacode.org/wiki/AVL_tree#C.2B.2B
Zapoznać się z implementacją drzewa AVL z serwisu rosettacode.org. Dostosować kod do standardu C++11 (zamiana NULL na nullptr). Dodać pozostałe funkcje zdefinowane dla drzew BST. Funkcja display() powinna wyświetlać dodatkowo współczynnik wyważenia dla każdego węzła.
Napisać funkcję is_avl() sprawdzającą poprawność drzewa AVL. Można obliczać wysokość drzewa AVL sprawdzając przy okazji, czy współczynnik wyważenia ma dozwoloną wartość (-1, 0, +1).
https://adtinfo.org/
Zapoznać się z biblioteką libavl (Ben Pfaff), która jest napisana w ANSI/ISO C89 z użyciem TexiWEB (literate programming).