Sade bir BST, anahtarlar sıralı sırayla gelirse bağlantılı bir listeye dejenere olabilir (O(n) işlemleri). Kendi kendini dengeleyen BST'ler — AVL ve kırmızı-siyah ağaçlar gibi — ekleme/silme işlemlerinden sonra düğümleri otomatik olarak döndürerek yüksekliği ~log n tutup işlemlerini garanti eder.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL ağacı | Kırmızı-siyah ağaç | |
|---|---|---|
| Dengeleme katılığı | kesin (yükseklik dengeleme) | daha gevşek |
| Aramalar | daha hızlı (daha kısa) | biraz daha yavaş |
| Ekleme/silme | daha fazla dönüş | daha az dönüş |
| En iyi kullanılan | okuma-yoğun iş yükleri | yazma-yoğun iş yükleri |
| İşlem | Zaman |
|---|---|
| arama | O(log n) |
| ekleme | O(log n) |
| silme | O(log n) |
Her ikisi de döndürmeler aracılığıyla dengeyi korur — BST sıralamasını korurken yüksekliği azaltan yerel O(1) yeniden yapılandırmalar.
Dengeli ağaçlar, standart kitaplıklarda sıralı haritalar ve kümeleri destekler (örn. Java TreeMap, C++ std::map kırmızı-siyah ağaçlar kullanır), sıralı yineleme artı garantili logaritmik işlemler sağlar.
BST'nin sıralamasına ve düşmanca girdilere karşı sert bir performans garantisine ihtiyacınız olduğunda cevaptırlar.