Jakiś Drzewo AVL zdefiniowany jako samorównoważący Różnica między wysokościami lewego i prawego poddrzewa dla dowolnego węzła jest znana jako czynnik równowagi węzła.
Nazwa drzewa AVL pochodzi od jego wynalazców, Georgy'ego Adelsona-Velsky'ego i Evgenii Landisa, którzy opublikowali je w swoim artykule z 1962 roku Algorytm organizacji informacji.
Przykład drzew AVL:
Drzewo AVL
Powyższe drzewo to AVL, ponieważ różnice między wysokościami lewego i prawego poddrzewa dla każdego węzła są mniejsze lub równe 1.
Operacje na drzewie AVL:
Obracanie poddrzew w drzewie AVL:
Aby zachować równowagę, drzewo AVL może obracać się na jeden z następujących czterech sposobów:
Obrót w lewo :
Kiedy do prawego poddrzewa prawego poddrzewa dodawany jest węzeł, a drzewo traci równowagę, wykonujemy pojedynczy obrót w lewo.
Obrót w lewo w drzewie AVL
Prawy obrót :
Jeśli do lewego poddrzewa lewego poddrzewa zostanie dodany węzeł, drzewo AVL może utracić równowagę, wykonujemy pojedynczy obrót w prawo.
Obrót w prawo w drzewie AVL
Obrót w lewo-prawo :
Obrót w lewo-prawo to kombinacja, w której pierwszy obrót w lewo ma miejsce po wykonaniu obrotu w prawo.
Obrót w lewo-prawo w drzewie AVL
Obrót w prawo i w lewo :
Obrót w prawo-w lewo to kombinacja, w której pierwszy obrót w prawo ma miejsce po wykonaniu obrotu w lewo.
Obrót w prawo-lewo w drzewie AVL
Zastosowania drzewa AVL:
- Służy do indeksowania dużych rekordów w bazie danych, a także do sprawnego w niej wyszukiwania.
- W przypadku wszystkich typów kolekcji w pamięci, w tym zbiorów i słowników, używane są drzewa AVL.
- Aplikacje bazodanowe, w których wstawianie i usuwanie danych jest rzadsze, ale konieczne jest częste wyszukiwanie danych
- Oprogramowanie wymagające zoptymalizowanego wyszukiwania.
- Znajduje zastosowanie w obszarach korporacyjnych i grach fabularnych.
Zalety drzewa AVL:
- Drzewa AVL potrafią się samorównoważyć.
- Na pewno nie jest przekrzywiony.
- Zapewnia szybsze wyszukiwanie niż drzewa czerwono-czarne
- Lepsza złożoność czasu wyszukiwania w porównaniu do innych drzew, takich jak drzewo binarne.
- Wysokość nie może przekraczać log(N), gdzie N jest całkowitą liczbą węzłów w drzewie.
Wady drzewa AVL:
- Jest to trudne do wdrożenia.
- Ma wysokie współczynniki stałe dla niektórych operacji.
- Mniej używane w porównaniu do drzew czerwono-czarnych.
- Ze względu na dość ścisłą równowagę drzewa AVL zapewniają skomplikowane operacje wstawiania i usuwania w miarę wykonywania większej liczby rotacji.
- Wykonaj więcej przetwarzania w celu zrównoważenia.
Powiązane artykuły:
- Wprowadzenie do drzew wyszukiwania binarnego – samouczki dotyczące struktury danych i algorytmów
- Wstawienie do drzewa AVL
- Usuwanie w drzewie AVL
