self-balancing binary search tree (tsz. self-balancing binary search trees)
Minden beszúrás vagy törlés után a fa újrastrukturálja magát, hogy megtartsa a „kiegyensúlyozottság” feltételét.
Ennek eredményeként minden alapművelet (keresés, beszúrás, törlés) O(log n) időben végezhető el — garantáltan.
| Típus | Leírás |
|---|---|
| AVL-fa | Minden csomópontra a bal és jobb ág magasságkülönbsége legfeljebb 1 |
| Red-Black Tree | Minden csomópont színezett (piros/fekete), és szigorú színezési szabályokkal tartja a kiegyensúlyozottságot |
| Splay Tree | Minden keresés után az érintett csúcsot előre mozgatja (self-adjusting BST) |
| Treap | Bináris keresőfa + heap kombináció (véletlen prioritás) |
| Scapegoat Tree | Amortizált kiegyensúlyozás, teljes újraépítéssel néha |
| Jellemző | AVL Tree | Red-Black Tree |
|---|---|---|
| Kiegyensúlyozottság | Szoros | Lazább |
| Gyorsabb keresés | ✅ | ❌ |
| Gyorsabb beszúrás/törlés | ❌ (több rotáció) | ✅ (kevesebb rotáció) |
| Használat | In-memory indexek | STL map/set, OS szintek |
| Művelet | AVL / RB Tree idő | Leírás |
|---|---|---|
insert(x)
|
O(log n) | Beszúrás + kiegyensúlyozás |
delete(x)
|
O(log n) | Törlés + kiegyensúlyozás |
search(x)
|
O(log n) | BST szabály szerint |
min()/max()
|
O(log n) | Bal vagy jobb ág mentén |
Tegyük fel, beszúrunk egymás után: 10, 20, 30
10
\
20
\
30
➡ Magasság nő, kiegyensúlyozatlan (jobbág dominancia)
20
/ \
10 30
👉 Fa visszanyerte logaritmikus szerkezetét
Egy sima BST:
A beszúrás sorrendjétől függően lineáris fává válhat (O(n)).
Egy AVL vagy Red-Black Tree garantálja, hogy:
magasság ≤ c × log₂(n)
| Tulajdonság | Self-balancing BST |
|---|---|
| Alapműveletek | O(log n) időben futnak
|
| Kiegyensúlyozás | Automatikusan történik |
| Leggyakoribb típusok | AVL, Red-Black, Splay, Treap |
| Használat | Map, Set, indexelés, keresés |
| Előny | Stabil teljesítmény minden esetben |