Średni czas wykonywania operacji na drzewach poszukiwań binarnych zależy od średniej wysokości drzewa. Podobnie pesymistyczny czas wykonania operacji zależy od wysokości drzewa (tj. długości najdłuższej ścieżki od korzenia do liści). Najlepiej, gdy wynosi ona w przybliżeniu gdzie to liczba węzłów w drzewie. Powoduje to że zarówno w lewym i prawym poddrzewie jest mniej więcej tyle samo węzłów, a tym samym dojście do każdego liścia zajmuje mniej więcej tyle samo kroków. Jest tak w przypadku, gdy drzewo jest zrównoważone, wówczas różnica wysokości lewego i prawego poddrzewa każdego z węzłów wynosi co najwyżej 1. Drzewo jest doskonale zrównoważone, gdy liczby elementów prawego i lewego poddrzewa każdego węzła różnią się najwyżej o jeden.
Powszechnie używane struktury gwarantujące zrównoważenie to drzewa AVL i drzewa czerwono-czarne. Posiadają one bardziej skomplikowane reguły wstawiania i usuwania, jak również przechowują dodatkowe wartości pomocnicze w węzłach drzewa.