self-balancing binary search tree
Főnév
self-balancing binary search tree (tsz. self-balancing binary search trees)
- (informatika) A self-balancing binary search tree (magyarul: önkiegyensúlyozó bináris keresőfa) olyan bináris keresőfa (BST), amely automatikusan biztosítja, hogy a fa magassága logaritmikusan növekedjen az elemek számával. Ez azért fontos, mert a sima BST könnyen eltorzulhat láncszerűvé, és akkor minden művelet O(n) időre lassul le.
🧠 Alapgondolat
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.
📚 Ismertebb önkiegyensúlyozó BST-típusok
| 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 |
🛠️ AVL vs Red-Black Tree összehasonlítás
| 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űveletek
| 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 |
🔄 Példa: AVL-fa beszúrás
Tegyük fel, beszúrunk egymás után: 10, 20, 30
Normál BST:
10
\
20
\
30
➡ Magasság nő, kiegyensúlyozatlan (jobbág dominancia)
AVL automatikus rotáció után:
20
/ \
10 30
👉 Fa visszanyerte logaritmikus szerkezetét
📈 Miért fontos az önkiegyensúlyozás?
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)
✅ Összefoglalás
| 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 |
- self-balancing binary search tree - Szótár.net (en-hu)
- self-balancing binary search tree - Sztaki (en-hu)
- self-balancing binary search tree - Merriam–Webster
- self-balancing binary search tree - Cambridge
- self-balancing binary search tree - WordNet
- self-balancing binary search tree - Яндекс (en-ru)
- self-balancing binary search tree - Google (en-hu)
- self-balancing binary search tree - Wikidata
- self-balancing binary search tree - Wikipédia (angol)