BST biasa bisa turun akibat degenerate dadi linked list (operasi O(n)) yen kunci tiba kanthi urutan sing sort. BST sing self-balancing — kaya AVL lan wit abang-ireng — kanthi otomatis rotasi node sawise insert/delete kanggo nggawe tinggi ~log n, njamin operasi O(log n).
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Wit AVL | Wit abang-ireng | |
|---|---|---|
| Ketat keseimbangan | ketat (tinggi-seimbang) | luwih kendor |
| Pencarian | luwih cepet (luwih pendek) | rada alon |
| Sisip/hapus | luwih akeh rotasi | luwih sithik rotasi |
| Paling apik kanggo | beban kroso-intens | beban tulis-intens |
| Operasi | Wektu |
|---|---|
| pangeling | O(log n) |
| sisip | O(log n) |
| hapus | O(log n) |
Rorone nyiyak keseimbangan liwat rotasi — penataan lokal O(1) sing njaga urutan BST nalika ngurangi tinggi.
Wit seimbang ndukung peta lan set sing terurut ing pustaka standar (contone Java TreeMap, C++ std::map nggunakake wit abang-ireng), menehi iterasi terurut lan operasi logaritmik terjamin.
Iku jawaban nalika butuh urutan BST lan jaminan kinerja keras marang masu sing meruwat.