Usuwanie Jeśli usuwany węzeł jest liściem, zostaje usunięty. Jeśli nie jest liściem, musi zostać zastąpiony największym elementem z jego lewego poddrzewa lub najmniejszym z jego prawego poddrzewa. Wyszukany największy lub najmniejszy element ma co najwyżej jedno dziecko, które zostaje teraz dzieckiem rodzica wyszukanego elementu. Po jego usunięciu odtwarzana jest ścieżka od rodzica wyszukanego elementu do korzenia, zaś współczynniki wyważenia są aktualizowane. Odtwarzanie może być zatrzymane, jeśli współczynnik wyważenia zostaje zmieniony na -1 lub 1, oznacza to bowiem, iż wysokość poddrzewa pozostaje niezmieniona. Zmiana współczynnika wyważenia na 0 oznacza zmniejszenie wysokości poddrzewa, aktualizowanie współczynników musi być kontynuowane. Jeśli współczynnik zostanie zmieniony na -2 lub 2, to wykonywana jest rotacja w celu przywrócenia struktury AVL. W przeciwieństwie do operacji wstawiania wystąpienie rotacji nie musi oznaczać, iż drzewo zostało wyważone. W pesymistycznym przypadku rotacje będą wykonywane aż do korzenia drzewa.