Zwykłe BST może zdegenerować się do listy powiązanej (operacje O(n)) jeśli klucze przychodzą w posortowanej kolejności. Samodzielnie balansujące BST-y — takie jak AVL i drzewa czerwono-czarne — automatycznie wykonują rotacje po wstawieniach/usunięciach, aby utrzymać wysokość ~log n, gwarantując operacje .
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Drzewo AVL | Drzewo czerwono-czarne | |
|---|---|---|
| Rygorystyczność balansowania | ścisłe (zrównoważone wysokością) | luźniejsze |
| Wyszukiwania | szybsze (krótsze) | nieco wolniejsze |
| Wstawianie/usuwanie | więcej rotacji | mniej rotacji |
| Najlepsze dla | obciążeń czytaniem | obciążeń pisaniem |
| Operacja | Czas |
|---|---|
| wyszukiwanie | O(log n) |
| wstawianie | O(log n) |
| usuwanie | O(log n) |
Oba utrzymują balans poprzez rotacje — lokalne reorganizacje O(1), które zachowują porządek BST jednocześnie zmniejszając wysokość.
Drzewa zrównoważone wspierają uporządkowane mapy i zestawy w bibliotekach standardowych (np. Java TreeMap, C++ std::map używają drzew czerwono-czarnych), zapewniając iterację posortowaną oraz gwarantowane operacje logarytmiczne.
Są odpowiedzią, gdy potrzbujesz zarówno porządku BST i twardej gwarancji wydajności przed wrogim wejściem.