Wyszukiwanie Wyszukiwanie w drzewie AVL jest wykonywane tak samo jak w niezrównoważonym BST dzięki serii porównań wartości wyszukiwanej z wierzchołkami, poczynając od korzenia. Wynik porównania oraz istnienie poddrzew pozwala stwierdzić, czy element szukany jest wierzchołkiem, znajduje się w lewym bądź prawym poddrzewie, czy też nie należy do drzewa. Zachowanie struktury AVL pozwala jednak na redukcję pesymistycznego czasu wyszukiwania do O(lg n).
Operacja wyszukiwania nie modyfikuje struktury drzewa, więc nigdy nie pociąga wyważania drzewa (rotacji węzłów).
Zobacz też
algorytm DSW drzewo splay
Przypisy
Linki zewnętrzne Wizualizacja drzew AVL Aplet pokazujący istotę drzew AVL
AVL