Ugrás a tartalomhoz

Fabejárás

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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

[szerkesztés]

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ő). [1] 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

[szerkesztés]

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.

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

[szerkesztés]

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ő: [2] [3]

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)

[szerkesztés]
  1. Az aktuális csúcs adatainak feldolgozása.
  2. Bal oldali részfa bejárása a pre-order függvény rekurzív meghívásával.
  3. 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)

[szerkesztés]
  1. Bal oldali részfa bejárása a in-order függvény rekurzív meghívásával.
  2. Az aktuális csúcs adatainak feldolgozása.
  3. 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. [4]

Fordított in-order - gyökérközepű (RNL)

[szerkesztés]
  1. Jobb oldali részfa bejárása a fordított in-order függvény rekurzív meghívásával.
  2. Az aktuális csúcs adatainak feldolgozása.
  3. 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)

[szerkesztés]
  1. Bal oldali részfa bejárása a post-order függvény rekurzív meghívásával.
  2. Jobb oldali részfa bejárása a post-order függvény rekurzív meghívásával.
  3. 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. [5]

Általános fa

[szerkesztés]

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:

  1. Pre-order művelet végrehajtása.
  2. Minden egyes i (i=1-től a gyermekek számáig):
    1. i feldolgozása, ha létezik.
    2. In-order művelet végrehajtása.
  3. 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

[szerkesztés]
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

[szerkesztés]

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

[szerkesztés]
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

[szerkesztés]

Mélységi bejárás

[szerkesztés]

Pre-order

[szerkesztés]
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

[szerkesztés]
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

[szerkesztés]
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

[szerkesztés]

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:

  1. Futásidő-, és memóriaigényes rekurzió elkerülése. Nem szükséges hívásverem.
  2. A csúcsnak van hivatkozása a szülő csúcsára.

Hátrányok:

  1. A fa bonyolultabb.
  2. Egy időben csak egy bejárás hajtható végre.
  3. 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: [6]

  1. Hivatkozások létrehozása az in-order sorrend szerinti következő csúcsra.
  2. Adatok kiírása ezen hivatkozások segítségével.
  3. Változtatások visszavonása, az eredeti fa visszaállítása.

Szélességi bejárás

[szerkeszté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

[szerkesztés]

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.

A bejárás alapvető követelménye, hogy minden csúcs feldolgozásra kerüljön. Végtelen fák esetében az egyszerű algoritmusok ezt gyakran nem teljesítik. Például egy végtelen mélységű bináris fa esetén a mélységi keresés a fa egyik oldalán (konvencionálisan a bal oldalon) halad lefelé, egyetlen levélcsúcsot sem érint (nem is fog), és soha nem dolgozza fel meg a többi csúcsot. Ezzel szemben a szélességi (szint-sorrendű) bejárás gond nélkül bejár (végtelen idő alatt) egy végtelen mélységű bináris, vagy bármilyen véges elágazási faktorral rendelkező fát.

Ezzel szemben, tekintve egy 2 mélységű fát, ahol a gyökér csúcsnak végtelen sok gyermeke van, és ezeknek a gyerekeknek két gyermeke van, a mélységi keresés minden csúcsot feldolgoz, mivel amint egy gyermek csúcs összes gyermek csúcsa feldolgozásra kerül, a következőre gyermek csúcsra lép (feltételezve, hogy a bejárás nem post-order, amely esetben a gyökér csúcs sosem kerül feldolgozásra). A szélességi keresés viszont soha nem fogja elérni az unokákat, mivel a gyermek csúcsok feldolgozásán nem jut túl.

Pontosabb futásidő-analízis végtelen sorszámok segítségével végezhető; Például a fenti 2 mélységű fa szélességi bejárása ω · 2 lépésből áll: ω az első szint, majd még egyszer ω a második szint.

Tehát az egyszerű mélységi vagy szélességi bejárások nem haladnak végig a teljes végtelen fán, és így nem is hatékonyak nagyon nagy fák esetében. A kevert módszerek azonban bármely (megszámlálhatóan) végtelen fát bejárnak, lényegében átlós irányban ("átlós" - mélységi és szélességi kombinációja).

Vegyünk egy végtelen számú elágazással rendelkező, végtelen mélységű fát. A gyökércsúcs jelölése legyen (), a gyermekcsúcsoké (1), (2), …, ezek gyermekeié, (1, 1), (1, 2), …, (2, 1), (2, 2), …, stb. A csúcsok így kölcsönösen egyértelműen megfeleltethetők pozitív egész számokból álló (vagy üres) sorozatoknak. Ezek megszámlálhatók, és sorba rendezhetők elemeik összege, ezen belül lexikográfiai sorrend szerint (véges számú sorozat elem-összege egy adott összeg, így minden bejegyzés elérhető – formálisan: egy adott természetes számnak véges számú (2n – 1, n ≥ 1) kompozíciója létezik). Ez meghatároz egy bejárást: 

 0: ()
1: (1)
2: (1, 1) (2)
3: (1, 1, 1) (1, 2) (2, 1) (3)
4: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

stb.

Ezt értelmezhetjük egy végtelen mélységű bináris fa leképezéseként, melyen szélességi bejárást végezhetünk: cseréljük ki a szülő csúcs „lefelé” menő éleit a második és további gyermek-csúcsainak esetében „jobbra” menő élekre az első gyermektől a másodikig, a másodiktól a harmadikig, stb. Így minden lépésnél indulhatunk lefelé ( (, 1)-et a sorozat végére beszúrva), vagy jobbra (hozzáadva egyet az utolsó számhoz) (kivéve a gyökércsúcsot, ahonnan csak lefelé indulhatunk). A végtelen bináris fa egy csúcsa és egy sorozat így a következőképpen feleltethető meg: a sorozat elemeinek összege mínusz egy megegyezik a csúcs gyökértől való távolságával, és megegyezik a végtelen bináris fában az n - 1 mélységben lévő 2n−1 számú csúccsal (2 a fa bináris tulajdonsága miatt).

Jegyzetek

[szerkesztés]
  1. ↑ Lecture 8, Tree Traversal. (Hozzáférés: 2015. május 2.)
  2. ↑ http://www.cise.ufl.edu/~sahni/cop3530/slides/lec216.pdf
  3. ↑ Preorder Traversal Algorithm. (Hozzáférés: 2015. május 2.)
  4. ↑ Wittman: Tree Traversal (PDF). UCLA Math. [2015. február 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. január 2.)
  5. ↑ Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange. (Hozzáférés: 2015. május 2.)
  6. ↑ Morris (1979). „Traversing binary trees simply and cheaply”. Information Processing Letters 9 (5). DOI:10.1016/0020-0190(79)90068-1. 

Irodalom

[szerkesztés]

Fordítás

[szerkesztés]

Ez a szócikk részben vagy egészben a Tree traversal című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

[szerkesztés]
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Fabejárás&oldid=27224923”