Ett vanligt BST kan degenerera till en länkad lista (O(n) operationer) om nycklar anländer i sorterad ordning. Själv-balanserande BST:er — som AVL och röd-svarta träd — roterar automatiskt noder efter infogningar/borttagningar för att hålla höjden ~log n, vilket garanterar operationer.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL-träd | Röd-svart träd | |
|---|---|---|
| Balanseringsstricthet | strikt (höjdbalanserat) | löst |
| Sökningar | snabbare (kortare) | något långsammare |
| Infogning/borttagning | fler rotationer | färre rotationer |
| Bäst för | läsintensiva arbetsbelastningar | skrivintensiva arbetsbelastningar |
| Operation | Tid |
|---|---|
| sökning | O(log n) |
| infogning | O(log n) |
| borttagning | O(log n) |
Båda upprätthåller balans via rotationer — lokala O(1) omstruktureringar som bevarar BST-ordningen samtidigt som höjden minskas.
Balanserade träd stödjer ordnade kartor och mängder i standardbibliotek (t.ex. Java TreeMap, C++ std::map använder röd-svarta träd), vilket ger sorterad iteration plus garanterade logaritmiska operationer.
De är svaret när du behöver ett BST:s ordning och en hårt prestandagaranti mot fientlig inmatning.