Encyklopedia w MarkpolReklama:Drzewo AVL, nazywane również drzewem dopuszczalnym, to drzewo poszukiwań binarnych (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Skrót AVL pochodzi od nazwisk twórców: Adelson-Velskii oraz Landis. Zrównoważenie drzewa osiąga się przypisując każdemu węzłowi współczynnik wyważenia, który jest równy różnicy wysokości lewego i prawego poddrzewa. Może wynosić 0, +1 lub -1. Wstawiając lub usuwając elementy drzewa (tak aby zachować własności drzewa BST) modyfikuje się też współczynik wyważenia, a gdy przyjmie on niedozwoloną wartość wykonuje specjalną operację rotacji węzłów, która przywraca zrównoważenie. Koszt modyfikacji drzewa jest nieco większy niż dla zwykłego drzewa BST, ale za to własności drzewa AVL gwarantują, że pesymistyczny czas wyszukiwania elementu w drzewie o n węzłach wynosi (log2n)/2, podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n. W wielu praktycznych zastosowaniach zdarza się, że do części obiektów sięga się częściej niż do pozostałych, przykładem może być słownik. Wówczas lepszym rozwiązaniem jest zastosowanie optymalnego drzewa poszukiwań. Zobacz też: drzewo czerwono-czarne Chcesz wypromować swoją stronę w internecie?? - nie zwlekaj pozycjonowanie w Luman.biz to rozsądny wybór |
|