Az informatikában a fabejárás (vagy fakeresés, fában keresés) egyfajta gráfbejárás, és arra a folyamatra utal, hogy feldolgozzuk (ellenőrizzük és/vagy módosítjuk) egy fa adatszerkezet minden egyes csúcsát (csomópontját) pontosan egyszer. Az ilyen algoritmusokat a csúcsok bejárásának sorrendje szerint osztályozzuk. A következő algoritmusok bináris fához készültek, de általánosíthatók más fákhoz is.
Típusai A láncolt listáktól, egydimenziós tömböktől és más lineáris adatszerkezetektől eltérően, amelyeknél a bejárás konvencionálisan lineáris sorrendben megy végbe, a fánál a bejárás többféleképpen történhet. Lehetséges mélységi, vagy szélességi bejárás. Mélységi bejárásra három általános módszer létezik: in-order (gyökérközepű) pre-order (gyökérkezdő), post-order (gyökérvégző). Ezeken az alapvető bejárásokon kívül számos más, összetett vagy kevert séma is létezik. Ilyenek például a korlátozott mélységű keresések, mint az iteratív, mélyülő mélységi keresés. Az utóbbi, a szélességi keresés végtelen fák bejárására is használatos, lásd lejjebb.
Adatszerkezetetek fabejáráshoz A fa bejárása során az összes csúcs feldolgozása valamilyen módszer szerint kerül sorra. Mivel egy adott csúcsból egynél több más csúcs is elérhető (nem lineáris adatszerkezet), így szekvenciális (nem párhuzamos) bejárást feltételezve néhány csúcs feldolgozását el kell halasztani - valamilyen módon tárolni kell a későbbi feldolgozáshoz. Ez gyakran verem (LIFO) vagy sor (FIFO) segítségével történik. Mivel a fa öndefiniáló (rekurzívan definiálható) adatszerkezet, a bejárás érthető módon megvalósítható rekurzióval (mag-rekurzió segítségével). Ebben az esetben a későbbiekben feldolgozandó csúcsok implicit módon tárolódnak a hívásveremben.
Mélységi keresés könnyen megvalósítható verem segítségével, akár rekurzív módon is (hívásveremmel), míg a szélességi keresés sor segítségével végezhető el. bélyegkép|281x281px|Egy példa mélységi bejárásra:pre-order - gyökérkezdő (piros):F, B, A, D, C, E, G, I, H;in-order - gyökérközepű (sárga):A, B, C, D, E, F, G, H, I;post-order - gyökérvégző (zöld):A, C, E, D, B, H, I, G, F.
Mélységi keresés bináris fában A következő kereséseket mélységi keresésnek (depth-first search, DFS) nevezzük, mivel a keresőfát a lehető legtovább mélyítjük minden egyes csúcsnál a következő testvércsúcs feldolgozása előtt. Bináris fa esetében a keresést minden egyes csúcshoz való hozzáférésként értelmezve az algoritmus a következő:http://www.cise.ufl.edu/~sahni/cop3530/slides/lec216.pdf
A bináris fa bejárásának általános rekurzív algoritmusa a következő: Ugrás egy szinttel lejjebb az N csúcshoz (N a rekurzió argumentuma). Ha N létezik (nem üres), a következő három művelet végrehajtása a megfelelő sorrendben:(L)N bal részfájának rekurzív bejárása(R)N jobb részfájának rekurzív bejárása(N)Az aktuális (N) csúcs feldolgozása.Ugrás egy szinttel feljebb N szülő-csúcsához.
A példákban az (L) művelet többnyire (R) előtt kerül végrehajtásra, de (L) előtt szintén lehetséges, lásd (RNL).
Pre-order - gyökérkezdő (NLR)
Az aktuális csúcs adatainak feldolgozása. Bal oldali részfa bejárása a pre-order függvény rekurzív meghívásával. Jobb oldali részfa bejárása a pre-order függvény rekurzív meghívásával.
A pre-order bejárás topologikusan rendezett, mivel a szülő csúcs feldolgozása megtörténik, mielőtt annak bármelyik gyermek csúcsa sorra kerül.
In-order - gyökérközepű (LNR)
Bal oldali részfa bejárása a in-order függvény rekurzív meghívásával. Az aktuális csúcs adatainak feldolgozása. Jobb oldali részfa bejárása a in-order függvény rekurzív meghívásával.
Bináris keresőfában, amelyben a csúcsok úgy vannak rendezve, hogy minden csúcs értéke nagyobb a bal oldali részfában lévő összes értéknél, és kisebb a jobb oldali részfában lévő összes értéknél, az in-order bejárás növekvő sorrendben dolgozza fel a csúcsokat.
Fordított in-order - gyökérközepű (RNL)
Jobb oldali részfa bejárása a fordított in-order függvény rekurzív meghívásával. Az aktuális csúcs adatainak feldolgozása. Bal oldali részfa bejárása a fordított in-order függvény rekurzív meghívásával.
Bináris keresőfában a fordított in-order bejárás csökkenő sorrendben dolgozza fel a csúcsokat.
Post-order - gyökérvégző (LRN)
Bal oldali részfa bejárása a post-order függvény rekurzív meghívásával. Jobb oldali részfa bejárása a post-order függvény rekurzív meghívásával. Az aktuális csúcs adatainak feldolgozása.
A bejárás sorrendjében felsorolt csúcsok listáját a fa kiegyenesítésének (szekvencializációnak) nevezik. A felsorolt bejárási minták egyike sem határozza meg egyértelműen a bejárt fát. Egy – minden csúcs értékében különböző – fa egyértelműen meghatározható az in-order, és (tetszőlegesen) a pre- vagy a post-order kiegyenesítések együttesével. Ezzel szemben A pre- és post-order a fa szerkezetét nem adja meg egyértelműen.
Általános fa Bármely fának a mélységi bejárásához a következő műveleteket kell rekurzív módon végrehajtani minden egyes csúcson:
Pre-order művelet végrehajtása. Minden egyes i (i=1-től a gyermekek számáig): i feldolgozása, ha létezik. In-order művelet végrehajtása. Post-order művelet végrehajtása.
A problémától függően a pre-order, az in-order, vagy a post-order művelet érvénytelen lehet, vagy csak egy adott csúcs feldolgozása szükséges. Ezek a műveletek tehát nem kötelezőek. Ezenkívül a gyakorlatban egynél több pre-order, in-order, vagy post-order műveletre lehet szükség. Például, amikor beszúrás történik egy ternális fába, a csúcsok összehasonlításakor egy pre-order művelet kerül végrehajtásra. Utólag egy post-order műveletre lehet szükség a fa kiegyensúlyozásához.
Szélességi bejárás / szint-sorrend bélyegkép|Szint sorrend: F, B, G, A, D, I, C, E, H A fák bejárhatók szint szerinti sorrendben, ahol minden egyes, az adott szinthez tartozó csúcsot feldolgozunk, mielőtt a következő szintre lépünk. Ezt a módszert szélességi bejárásnak/keresésnek (BFS) nevezik, mivel a keresőfát minden szint esetében a lehető legjobban kiszélesítjük a következő szintre lépés előtt.
Egyéb típusok Vannak olyan fabejárási algoritmusok is, amelyek nem tartoznak sem a mélységi, sem a szélességi kereséshez. Az egyik ilyen algoritmus a Monte Carlo-fakeresés, amely a legígéretesebb lépések elemzésére koncentrál, és a keresési fa kibővítését véletlenszerű mintavételére alapozza.
Alkalmazási lehetőségek bélyegkép|260x260px| Az A * ( B - C ) + ( D + E ) számtani kifejezést reprezentáló fa A pre-order bejárás felhasználható prefix-kifejezés (lengyel forma) elkészítésére kifejezésfákból: a kifejezésfa pre-order bejárásával. Például, az ábrázolt aritmetikai kifejezés fáját pre-order sorrendben bejárva a "+ * A - B C + D E " eredményt kapjuk.
Bináris fa post-order bejárása postfix-kifejezést (fordított lengyel jelölés) generál. A ábrázolt aritmetikai kifejezés fáját post-order sorrendben bejárva az "A B C - * D E + +" eredményt kapjuk; ez utóbbi könnyen átalakítható gépi kóddá, hogy a kifejezést egy verem-géppel ki lehessen értékelni.
Az in-order bejárást nagyon gyakran használják a bináris keresőfáknál, mivel a fában tárolt értékeket a keresőfa összehasonlító algoritmusának megfelelő sorrendben adja vissza.
Csúcsok törlése vagy felszabadítása közben végzett post-order bejárás törölheti vagy felszabadíthatja a teljes fát. Ezáltal a csúcs törlődik gyermekei törlése után.
Bináris fa másolása szintén post-order művelet-sorrendben történik, mivel így a csúcs gyermekére való hivatkozás közvetlenül a gyermek-csúcs rekurzív létrehozása után kap értéket. Ez azt jelenti, hogy a szülő létrehozása nem fejezhető be az összes gyermek létrehozásának befejezése előtt.
Implementációk
Mélységi bejárás
Pre-order preorder(csúcs) ha (csúcs == null) return feldolgoz(csúcs) preorder(csúcs.bal) preorder(csúcs.jobb) iteratívPreorder(csúcs) ha (csúcs == null) return s ← üres verem s.rárak(csúcs) amíg (nem s.Üres()) csúcs ← s.levesz() feldolgoz(csúcs) //a jobb oldali csúcs kerül be először a verembe, így a bal oldali dolgozódik fel elsőként ha csúcs.jobb ≠ null s.rárak(csúcs.jobb) ha csúcs.bal ≠ null s.rárak(csúcs.bal)
In-order inorder(csúcs) ha (csúcs == null) return inorder(csúcs.bal) feldolgoz(csúcs) inorder(csúcs.jobb) iteratívInorder(csúcs) s ← üres verem amíg (nem s.Üres() vagy csúcs ≠ null) ha (csúcs ≠ null) s.rárak(csúcs) csúcs ← csúcs.bal egyébként csúcs ← s.levesz() feldolgoz(csúcs) csúcs ← csúcs.jobb
Post-order postorder(csúcs) ha (csúcs == null) return postorder(csúcs.bal) postorder(csúcs.jobb) feldolgoz(csúcs) iteratívPostorder(csúcs) s ← üres verem utolsóFeldolgozottCsúcs ← null amíg (nem s.Üres() vagy csúcs ≠ null) ha (csúcs ≠ null) s.rárak(csúcs) csúcs ← csúcs.bal egyébként aktuálisCsúcs ← s.levesz() // ha a jobb oldali gyermek létezik és a // bejárás éppen a bal oldali gyermek felől történik ha (aktuálisCsúcs.jobb ≠ null és utolsóCsúcsFeldolgoz ≠ aktuálisCsúcs.jobb) csúcs ← aktuálisCsúcs.jobb egyébként feldolgoz(aktuálisCsúcs) utolsóFeldolgozottCsúcs ← s.levesz() A fenti implementációk mindegyikéhez a fa mélységének megfelelő méretű verem szükséges. (Rekurziónál ez a hívásverem, iteratív algoritmusoknál tetszőleges verem). A rosszul kiegyensúlyozott fák esetében ez számottevő nagyságú lehet. Iteratív implementációknál kikerülhetjük a verem használatát úgy, hogy nyilvántartunk egy szülő csúcsra mutató hivatkozást minden egyes csúcsban, vagy a fűzött fát alkalmazunk (következő bekezdés).
Morris in-order bejárás fűzött fában Fűzött bináris fában minden olyan bal oldali (gyermekre mutató) hivatkozás, amely egyébként null lenne, az in-order sorrend szerinti előző csúcsra mutat (ha létezik), és minden jobb oldali hivatkozás, amely egyébként null lenne, az in-order sorrend szerinti következő csúcsra mutat (ha létezik).
Előnyök:
Futásidő-, és memóriaigényes rekurzió elkerülése. Nem szükséges hívásverem. A csúcsnak van hivatkozása a szülő csúcsára.
Hátrányok:
A fa bonyolultabb. Egy időben csak egy bejárás hajtható végre. Hajlamosabb hibára, amikor egy gyermek csúcs sincs, és mindkét hivatkozás a szülő csúcsra mutat.
A Morris-bejárás egy fűzött fabejárás implementációja in-order sorrendben:
Hivatkozások létrehozása az in-order sorrend szerinti következő csúcsra. Adatok kiírása ezen hivatkozások segítségével. Változtatások visszavonása, az eredeti fa visszaállítása.
Szélességi bejárás Az alábbi egy egyszerű soron alapuló szint-sorrendű bejárás pszeudokódja, ami az adott mélységben a csúcsok maximális számának megfelelő helyet igényel. A mélység legfeljebb a csúcsok száma / 2 lehet. Az ilyen típusú bejárás helytakarékosabban implementálható iteratív mélyülő mélységi bejárás használatával. szintSorrend(gyökér) q ← üres sor q.sorba(gyökér) amíg nem q.Üres() csináld csúcs ← q.sorból() feldolgoz(csúcs) ha csúcs.bal ≠ null akkor q.sorba(csúcs.bal) ha csúcs.jobb ≠ null akkor q.sorba(csúcs.jobb)
Végtelen fák Bár a bejárást általában a véges számú csúcsokkal (és ennélfogva a véges mélységgel és véges elágazási faktorral) végezzük, ezt a végtelen fák esetében is megtehetjük. Ez nagy jelentőséggel bír a funkcionális programozásban (különösen lusta kiértékelésnél), mivel bár a végtelen adatstruktúrák gyakran könnyen meghatározhatók és felhasználhatók, a kiértékelésük végtelen időt igényel. Léteznek véges fák, amelyek túl nagyok az explicit reprezentációhoz, mint például a sakk vagy a go játék fája, így ezeket érdemes végtelenként elemezni.