PL 
EnglishDomyślny
Українська🌳 Drzewo AVL — samobalansujące się rotacje
Wstawiaj i usuwaj klucze w drzewie AVL i obserwuj aktualizację współczynników równowagi po każdej zmianie. Gdy poddrzewo przekroczy ±1, pojedyncze i podwójne rotacje automatycznie przywracają równowagę wysokości.
O tej symulacji
Drzewo AVL, nazwane od wynalazców Georgija Adelsona-Velskiego i Jewgienija Landisa, którzy opublikowali je w 1962 roku, to najwcześniejsze samobalansujące się drzewo poszukiwań binarnych. Każdy węzeł przechowuje współczynnik równowagi równy wysokości lewego poddrzewa minus wysokości prawego, a drzewo utrzymuje niezmiennik, że wartość ta pozostaje w przedziale {−1, 0, 1}.
🔬 Co pokazuje
Drzewo binarne z na bieżąco aktualizowanymi wysokościami i współczynnikami równowagi każdego węzła, wraz z animacją pojedynczych i podwójnych rotacji przywracających równowagę.
🎮 Jak korzystać
Wstawiaj i usuwaj klucze pojedynczo lub losowo i obserwuj, jak drzewo automatycznie się rebalansuje po każdej operacji.
💡 Czy wiesz, że…
Drzewa AVL są bardziej rygorystycznie zbalansowane niż drzewa czerwono-czarne, co daje szybsze wyszukiwanie kosztem częstszych rotacji przy wstawianiu i usuwaniu.
Często zadawane pytania
Dlaczego współczynnik równowagi musi pozostać w przedziale {−1, 0, 1}?
Ten zakres jest dokładnym progiem, który utrzymuje wysokość drzewa na poziomie O(log n). Adelson-Velsky i Landis udowodnili, że drzewo spełniające ten niezmiennik ma wysokość co najwyżej około 1,44·log₂(n+2).
Jaka jest różnica między pojedynczą a podwójną rotacją?
Pojedyncza rotacja (przypadek LL lub RR) naprawia niezrównoważenie spowodowane poddrzewem cięższym po tej samej stronie co jego ciężkie dziecko. Podwójna rotacja (przypadek LR lub RL) obsługuje niezrównoważenie zygzakowate, wymagając dwóch rotacji.
Jak drzewo AVL wypada w porównaniu z drzewem czerwono-czarnym?
Oba gwarantują wysokość O(log n), ale drzewa AVL wymuszają ściślejszy niezmiennik równowagi, dając krótsze drzewa i szybsze wyszukiwanie. Drzewa czerwono-czarne rozluźniają ograniczenie, co oznacza mniej rotacji przy wstawianiu i usuwaniu.
Dlaczego usuwanie może wymagać rotacji na każdym poziomie aż do korzenia, w przeciwieństwie do wstawiania?
Wstawienie dodaje wysokość tylko jednemu poddrzewu, więc do przywrócenia równowagi potrzeba co najwyżej jednej rotacji. Usunięcie może zmniejszyć wysokość poddrzewa, a to zmniejszenie może propagować się w górę, potencjalnie wywołując rotację rebalansującą przy każdym przodku na ścieżce do korzenia.