BST rahisi inaweza kuzorota kuwa orodha iliyounganishwa (operesheni za O(n)) ikiwa funguo zikaanzia kwa utaratibu uliobahatisha. BST zilizosawazisha yenyewe — kama AVL na miti ya nyekundu-nyeusi — huzunguka automatiki nodi baada ya uingizaji/kufuta ili kuweka urefu ~log n, ikihakikisha operesheni za .
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Mti wa AVL | Mti wa nyekundu-nyeusi | |
|---|---|---|
| Ukali wa usawaziko | kali (urefu unaosawazishwa) | lolote |
| Utafutaji | haraka (fupi) | kidogo polepole |
| Uingizaji/kufuta | mizunguko mingi | mizunguko machache |
| Bora kwa | mzigo wenye kusoma | mzigo wenye kuandika |
| Operesheni | Wakati |
|---|---|
| utafutaji | O(log n) |
| uingizaji | O(log n) |
| kufuta | O(log n) |
Zote mbili zinahifadhi usawaziko kupitia mizunguko — kujenga upya kwa ndani O(1) ambayo huhifadhi utaratibu wa BST wakati wa kupunguza urefu.
Miti iliyosawazishwa inasaidia ramani na seti zilizoamriwa katika maktaba za kawaida (k.m. Java TreeMap, C++ std::map hutumia miti ya nyekundu-nyeusi), na kutoa marudio yaliyoamuriwa pamoja na operesheni za logarithmic zilizohakikishwa.
Zi ndio jibu wakati unahitaji utaratibu wa BST na dhamana ya juu ya utendaji dhidi ya pembejeo lenye matezo.