Wstawiając lub usuwając elementy drzewa (tak, by zachować własności drzewa BST), modyfikuje się też współczynnik 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 BST, ale za to własności drzewa AVL gwarantują, że pesymistyczny czas wyszukiwania elementu w drzewie o n węzłach wynosi 1.44(log2n), podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n.
Drzewa AVL są często porównywane z drzewami czerwono-czarnymi, ponieważ pozwalają na wykonanie tych samych operacji (dodawanie, usuwanie oraz wyszukiwanie elementów) przy równej co do rzędu pesymistycznej złożoności czasowej O(log n). Przy powtarzających się wyszukiwaniach drzewa AVL są jednak wydajniejszePfaff, Ben (czerwiec 2004). Performance Analysis of BSTs in System Software (PDF). Stanford University..
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ń.