OBOWIĄZKOWE DO PRZESŁANIA: 12.1 lub 12.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 2x(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
};
/* AVL tree */
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();
T* find_min();
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.
Napisać funkcję 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).