Czym jest drzewo AVL?

Każdy węzeł drzewa AVL przechowuje własną wysokość: liczbę krawędzi na najdłuższej ścieżce do liścia. Liść ma wysokość 1, a puste poddrzewo ma wysokość 0. Na podstawie wysokości dwojga dzieci węzła możesz obliczyć jego współczynnik równowagi: height(left) - height(right).

Węzeł jest zrównoważony, gdy jego współczynnik równowagi wynosi -1, 0 lub 1. Zasada drzewa AVL jest prosta: każdy węzeł musi być zawsze zrównoważony. Gdy wstawienie lub usunięcie sprawi, że współczynnik równowagi węzła osiągnie 2 lub -2, drzewo wykonuje rotację: lokalne przestawienie kilku wskaźników, które przywraca równowagę w stałym czasie, nie naruszając porządku drzewa wyszukiwań.

Istnieją cztery przypadki rotacji (lewo-lewo, prawo-prawo, lewo-prawo, prawo-lewo), ale wszystkie sprowadzają się do dwóch podstawowych operacji: pojedynczej rotacji w lewo i pojedynczej rotacji w prawo. W kolejnych lekcjach zbudujesz obie od podstaw.