2-3 fa
| 2-3 fa | |
| Típus | B-fa |
| Komplexitás (O jelöléssel) | |
| Tárigény | O(n) |
| Beszúrás | O(log n) |
| Keresés | O(log n) |
| Törlés | O(log n) |
A számítógép-tudományban 2-3 fa alatt egy önkiegyensúlyozó keresőfát értünk.
Tulajdonságai
[szerkesztés]A 2-3 fa a B-fák egy változata. Lényeges tulajdonságai:
- A fában tárolt értékeket a levélelemekben tároljuk.
- A fa összes levele azonos magasságban van (azaz a fa mindig tökéletesen kiegyensúlyozott).
- A fa belső csúcsai úgynevezett 2-csúcsok illetve 3-csúcsok.
Egy 2-csúcsban egy értéket tárolunk és két (bal oldali és jobb oldali) él halad ki belőle - a bal oldali részfában az értéknél (kulcsnál) kisebb, a jobb oldali részfában a kulcsnál nagyobb vagy egyenlő értékű levelek vannak.
A 3-csúcsban két értéket tárolunk, illetve három (bal, középső és jobb oldali) él halad ki belőle. A bal oldali részfában a kisebbik kulcsnál kisebb, a jobb oldali részfában a nagyobbik kulcsnál nagyobb vagy egyenlő, a középső részfában pedig a kisebbik kulcsnál nagyobb vagy egyenlő de a nagyobbik kulcsnál kisebb értékű levelek vannak.
A fában "tároltnak" csak azokat az értékeket tekintjük, amelyek valamely levélben megtalálhatóak. A belső csúcsokban tárolt kulcsok megegyezhetnek (a fa felépítésének definíciója alapján) egyes levelekben tárolt értékekkel, de ez nem minden esetben igaz - például egy törlés során visszamaradt érték egy belső csúcsban nem feltétlenül rontja el a 2-3 fa tulajdonságot, viszont mivel maga az érték már nem található meg egy levélben, ezért az a kulcs nem egy tárolt érték.
A fa önkiegyensúlyozó tulajdonsága abból adódik, hogy megköveteljük, hogy minden levél azonos távolságra legyen a gyökértől. Ez a tulajdonság optimális lépésszámot tesz lehetővé kiegyensúlyozott eloszlású keresési értékekkel történő keresések során.
Műveletek
[szerkesztés]
A 2-3 fában a keresőfákban általánosan definiált műveleteket értelmezzük: beszúrás, keresés és törlés.
Keresés
[szerkesztés]A fában a gyökértől elindulva keresünk. Ha jelenleg vizsgált csúcs egy 2-csúcs, akkor ha keresett érték kisebb, mint a csúcs kulcsa, a bal oldali részfában folytatjuk a keresést, egyébként a jobb oldaliban. Amennyiben egy 3-csúcsot vizsgálunk, ha a keresett érték kisebb mint a csúcs kisebbik kulcsa, balra haladunk, egyébként ha kisebb mint a második kulcsa, a középső részfába haladunk tovább, illetve ha egyik se igaz, a jobb oldali részfában folytatjuk a keresést. Ha egy levélhez érünk, és a levél tartalma a keresett kulcs, a fa tartalmazza a kulcsot.
Beszúrás
[szerkesztés]
A fába a beszúrást egy kereséssel kezdjük - amennyiben a kulcs már szerepel a fában, azt nem szúrjuk be.
Ha a fában még nem szerepel a kulcs, akkor először megkeressük annak a helyét, ugyanúgy, mintha egy keresést végeznénk. A levél helyének megkeresése után több esetet különböztetünk meg. A mellékelt ábrákon a beszúrandó levelet szaggatott vonallal jelöltük.
Beszúrás 2-csúcsba
[szerkesztés]Amennyiben a beszúrandó kulcs helyének felmenője egy 2-csúcs, a csúcs kiegészül egy 3-csúccsá. Ennek kulcsait az új levél helyzete határozza meg:
- Ha a beszúrt érték mindkét leszármazott értékénél kisebb, a régi 2-csúcs kulcsa az új csúcs jobb oldali kulcsa lesz, a bal oldali kulcs pedig a régi 2-csúcs bal oldali leszármazottának értéke.
- Ha a beszúrt érték a két leszármazott értéke közé esik, a régi 2-csúcs kulcsa az új csúcs bal vagy jobb oldali kulcsa lesz attól függően, hogy a beszúrt érték a 2-csúcs kulcsától kisebb, avagy nagyobb. Ezek után a bal vagy jobb oldali kulcs(amelyik üresen maradt) pedig a beszúrt érték.
- Ha a beszúrt érték mindkét leszármazott értékénél nagyobb, a régi 2-csúcs kulcsa az új csúcs bal oldali kulcsa lesz, a jobb oldali kulcs pedig a beszúrt érték.
Csúcsvágás
[szerkesztés]Ha a beszúrandó kulcs helyének felmenője egy 3-csúcs, azt nem tudjuk tovább kiegészíteni, így a csúcsvágás módszerét kell alkalmazni. A mellékelt ábrákon a csúcsvágások helyét a piros szaggatott vonalak jelölik. A csúcsvágáshoz megállapítjuk az új levél helyzetét a három, már fában levő levélhez képest. Az így kapott négy levelet két csoportra osztjuk, a két kisebbiket az első csoportba, a két nagyobbikat a másodikba. Így két 2-csúcsot tudunk létrehozni, melyeknek a kulcsa a saját csoportjuk nagyobbik eleme. A második csoport kisebbik eleme a medián - az első kulcs kisebb nála, a második nagyobb, tehát ennek a két leszármazottja lesz a két 2-csúcs. Ez többféleképpen történhet:
- Ha az eredeti 3-csúcs közvetlen felmenője egy 2-csúcs, akkor a 2-csúcs kiegészül 3-csúcssá, és a medián a megfelelő helyre kerül.
- Ha az eredeti 3-csúcs közvetlen felmenője egy 3-csúcs, a csúcsvágást megismételjük úgy, hogy a négy érték melyeket csoportokra osztunk a két 2-csúcs kulcsa, illetve a felmenő két kulcsa.
- Ha a csúcsvágások sorozata egészen a gyökérelemig elér, akkor a gyökérelemből levágott csúcs felmenője lesz a fa új gyökere, ezzel megnövelve a 2-3 fa magasságát.
Törlés
[szerkesztés]Egy levél törlésekor is több esetet különböztethetünk meg, az adatszerkezet tulajdonságaiból adódóan. A törlést is kereséssel indítjuk - ha a kulcs nem található meg a fában, akkor nem tudunk törölni.
Ha a törlésre kijelölt elem közvetlen felmenője egy 3-csúcs, akkor a levelet egyszerűen töröljük és a csúcsot 2-csúccsá alakítjuk, a megfelelő kulcs megtartásával. A bal oldali levél törlése esetén a jobb oldali, a jobb oldali levél törlése esetén a bal oldali kulcsot tartjuk meg. A középső levél törlése esetén mindegy, hogy melyiket.
Ha a törlésre kijelölt elem közvetlen felmenője egy X 2-csúcs, két eset lehetséges:
- Ha X valamelyik szomszédos testvérének (egy csúcs testvére a felmenőjének akármelyik másik gyereke, egy 3-csúcs bal és jobb oldali gyerekei nem szomszédos testvérek) három gyereke van, akkor ezek közül a megfelelő elemet - jobb oldali testvére esetén a bal oldali levelet, bal oldali testvér esetén a jobb oldalit - áthelyezzük X-be.
- Ha X szomszédos testvérei is 2-csúcsok, akkor "beolvasztjuk" valamely szomszédos 2-csúcsba a megmaradt levelet, így létrehozva egy 3-csúcsot. Ekkor a törlés műveletét rekurzívan elvégezzük X felmenőjére is, hiszen csökkent eggyel a leszármazottainak a száma. Az így létrejövő összeolvadások hulláma akár a gyökeret is elérheti, melynek beolvadása esetén a fa magassága is csökken eggyel.
