BST biasa boleh merosot menjadi senarai terpaut (operasi O(n)) jika kunci tiba dalam urutan tersusun. BST yang menyeimbang sendiri — seperti AVL dan pokok merah-hitam — secara otomatis memutar nod selepas penyisipan/penghapusan untuk mengekalkan ketinggian ~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)
| Pokok AVL | Pokok merah-hitam | |
|---|---|---|
| Ketegasan keseimbangan | ketat (seimbang ketinggian) | lebih longgar |
| Carian | lebih pantas (lebih pendek) | sedikit lebih perlahan |
| Sisip/padam | lebih banyak putaran | lebih sedikit putaran |
| Terbaik untuk | beban kerja berat bacaan | beban kerja berat tulis |
| Operasi | Masa |
|---|---|
| cari | O(log n) |
| sisip | O(log n) |
| padam | O(log n) |
Kedua-duanya mengekalkan keseimbangan melalui putaran — penstrukturan semula tempatan O(1) yang mengekalkan susunan BST sambil mengurangkan ketinggian.
Pokok yang seimbang menyokong peta dan set yang tersusun dalam perpustakaan piawai (mis. Java TreeMap, C++ std::map menggunakan pokok merah-hitam), memberikan lelaran tersusun serta operasi logaritmik terjamin.
Ia adalah jawapan apabila anda memerlukan susunan BST dan jaminan prestasi yang keras terhadap masukan yang bermusuhan.