Drzewa zrównoważone (np. AVL, Red‑Black) to samo‑równoważące drzewa BST, które po wstawieniach i usunięciach wykonują rotacje, aby wysokość była rzędu log n. Gwarantuje to operacje wyszukiwania, wstawiania i usuwania w O(log n) nawet w pesymistycznym przypadku.