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

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

Egy 2-3 fa

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

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

Beszúrás, ha az új levél felmenője 2-csúcs

Beszúrás, ha az új levél felmenője 3-csúcs, melynek felmenője 2-csúcs

Többszörös csúcsvágás, egészen az első 2-csúcsig vagy a gyökérig.

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

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

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

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.