Egy egyszerű BST leépülhet egy linkelt listává (O(n) műveletek), ha a kulcsok rendezett sorrendben érkeznek. Az önmagukat kiegyensúlyozó BST-k — mint az AVL és a vörös-fekete fák — automatikusan forgatják a csomópontokat beszúrás/törlés után, hogy a magasság ~log n maradjon, garantálva az műveleteket.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL fa | Vörös-fekete fa | |
|---|---|---|
| Kiegyensúlyozottság szigora | szigorú (magasság-kiegyensúlyozott) | lazább |
| Keresés | gyorsabb (rövidebb) | kicsit lassabb |
| Beszúrás/törlés | több forgatás | kevesebb forgatás |
| Legjobb ehhez | olvasás-intenzív terhelés | írás-intenzív terhelés |
| Műveletek | Idő |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
Mindkettő az forgatások révén tartja az egyensúlyt — helyi O(1) átszervezések, amelyek megőrzik a BST rendezést és csökkentik a magasságot.
Az egyensúlyozott fák támogatják a rendezett térképeket és halmazokat a standard könyvtárakban (például a Java TreeMap, C++ std::map vörös-fekete fákat használnak), biztosítva a rendezett iterációt és garantált logaritmikus műveleteket.
Ezek a válasz, amikor szükséged van a BST rendezésére és egy kemény teljesítmény-garanciára az ellenfél bemenetekkel szemben.