BST biasa dapat merosot menjadi daftar tertaut (operasi O(n)) jika kunci tiba dalam urutan yang diurutkan. BST yang menyeimbangkan diri — seperti pohon AVL dan pohon merah-hitam — secara otomatis memutar simpul setelah penyisipan/penghapusan untuk menjaga tinggi ~log n, menjamin operasi .
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Pohon AVL | Pohon merah-hitam | |
|---|---|---|
| Keketatan keseimbangan | ketat (seimbang-tinggi) | lebih longgar |
| Pencarian | lebih cepat (lebih pendek) | sedikit lebih lambat |
| Penyisipan/penghapusan | lebih banyak rotasi | lebih sedikit rotasi |
| Terbaik untuk | beban kerja berat baca | beban kerja berat tulis |
| Operasi | Waktu |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
Keduanya mempertahankan keseimbangan melalui rotasi — perestrukturan O(1) lokal yang mempertahankan pengurutan BST sekaligus mengurangi tinggi.
Pohon seimbang mendukung peta dan himpunan terurut dalam pustaka standar (misalnya, Java TreeMap, C++ std::map menggunakan pohon merah-hitam), memberikan iterasi terurut plus operasi logaritmik yang dijamin.
Mereka adalah jawabannya ketika Anda membutuhkan pengurutan BST dan jaminan kinerja keras terhadap masukan yang merugikan.