Fák átszelése

author
7 minutes, 27 seconds Read

Az összekapcsolt listákkal, egydimenziós tömbökkel és más lineáris adatszerkezetekkel ellentétben, amelyeken lineáris sorrendben haladunk végig, a fák többféleképpen is átszelhetők. Lehet őket mélység-elsőként vagy szélesség-elsőként végigjárni. A mélység szerinti sorrendben történő átjárásuknak három gyakori módja van: sorrendben, elősorrendben és utósorrendben. Ezeken az alapvető átjárási módokon túlmenően különböző összetettebb vagy hibrid sémák is lehetségesek, például a mélységkorlátozott keresés, például az iteratív mélyülő mélység-első keresés. Ez utóbbi, akárcsak a szélesség-első keresés, végtelen fák átjárására is használható, lásd alább.

Adatszerkezetek a fák átjárásáhozSzerkesztés

A fa átjárása magában foglalja az összes csomóponton való iterációt valamilyen módon. Mivel egy adott csomópontból egynél több lehetséges következő csomópont van (nem lineáris adatszerkezetről van szó), ezért – szekvenciális (nem párhuzamos) számítást feltételezve – néhány csomópontot valamilyen módon el kell halasztani-tárolni a későbbi látogatáshoz. Ez gyakran egy verem (LIFO) vagy egy sor (FIFO) segítségével történik. Mivel a fa egy önreferenciális (rekurzívan definiált) adatszerkezet, az átjárás nagyon természetes és egyértelmű módon definiálható rekurzióval vagy – finomabban fogalmazva – magkurzióval; ezekben az esetekben a halasztott csomópontokat implicit módon a hívási veremben tároljuk.

A mélység-első keresés könnyen megvalósítható vermen keresztül, beleértve a rekurzív (a hívási vermen keresztül), míg a szélesség-első keresés könnyen megvalósítható soron keresztül, beleértve a magkurzív keresést is.:45-61

Bináris fa mélység-első kereséseSzerkesztés

Egy bináris fa mélység-első átszelése (pontozott útvonal):

  • Előrendezés (csomóponthoz való hozzáférés a piros ● pozícióban):

    F, B, A, D, C, E, G, I, H;

  • In-order (node access at position green ●):

    A, B, C, D, E, F, G, H, I;

  • Post-order (node access at position blue ●):

    A, C, E, D, B, H, I, G, F.

Ezeket a kereséseket mélységi keresésnek (DFS) nevezzük, mivel a keresési fát minden egyes gyermeken a lehető legmélyebbre mélyítjük, mielőtt a következő testvérre lépnénk. Egy bináris fa esetében ezek minden egyes csomóponton az aktuális csomóponttal kezdődő hozzáférési műveletekként vannak definiálva, amelyek algoritmusa a következő:

A bináris fa bejárásának általános rekurzív mintája a következő:

  1. Megyünk egy szinttel lejjebb az N rekurzív argumentumig. Ha N létezik (nem üres), akkor a következő három műveletet hajtjuk végre egy bizonyos sorrendben: L: rekurzívan végigmegy N bal oldali részfáján. R: N jobb oldali részfájának rekurzív végigjárása. N: Hozzáférés (látogatás) magához az aktuális N csomóponthoz.
  2. Visszatérés egy szinttel feljebb lépve és az N szülő csomópontjához érkezve.

Három módszer (minta) van arra, hogy a parcours (traverzálódás) melyik pozíciójában a csomóponthoz képest (az ábrán: piros, zöld vagy kék) a csomópont látogatása (elérése) történjen. Pontosan egy szín kiválasztása a csomópont pontosan egy látogatását határozza meg az alábbiakban leírtak szerint. A hozzáférés mindhárom színnél ugyanannak a csomópontnak a háromszori látogatását eredményezi, ami az “all-order” szekvencializációt eredményezi:

F-B-A-A-A-A-B-D-C-C-C-C-D-E-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F

Pre-order, NLREdit

  1. Az aktuális csomópont adatrészének elérése (az ábrán: piros pozíció).
  2. A bal oldali részfa bejárása a pre-order függvény rekurzív hívásával.
  3. A jobb oldali részfa bejárása a pre-order függvény rekurzív hívásával.

A pre-order átjárás topológiailag rendezett, mivel egy szülő csomópontot előbb dolgozunk fel, mint bármelyik gyermekcsomópontját.

In-order, LNREdit

  1. A bal oldali részfát az in-order függvény rekurzív hívásával járjuk át.
  2. Elérjük az aktuális csomópont adatrészét (az ábrán: zöld pozíció).
  3. A jobb oldali részfa bejárása az in-order függvény rekurzív hívásával.

Egy bináris keresőfában, amely úgy van rendezve, hogy minden csomópontban a kulcs nagyobb, mint a bal oldali részfa összes kulcsa, és kisebb, mint a jobb oldali részfa összes kulcsa, a sorrendben történő bejárás a kulcsokat növekvő rendezett sorrendben keresi.

Reverse in-order, RNLEdit

  1. A jobb oldali részfa bejárása a reverse in-order függvény rekurzív hívásával.
  2. Az aktuális csomópont adatrészének elérése.
  3. A bal oldali részfa bejárása a reverse in-order függvény rekurzív hívásával.

Bináris keresőfában a fordított sorrendben történő átjárás a kulcsokat csökkenő rendezett sorrendben keresi.

Post-order, LRNEdit

  1. A bal oldali részfát a post-order függvény rekurzív hívásával járja át.
  2. A jobb oldali részfát a post-order függvény rekurzív hívásával járjuk be.
  3. Az aktuális csomópont adatrészéhez (az ábrán: kék pozíció) férünk hozzá.

A traverzálás nyomvonalát a fa szekvencializációjának nevezzük. A traverzális nyomvonal az egyes meglátogatott csomópontok listája. Nincs olyan szekvencializáció, amely a pre-, in- vagy post-order szerint egyedileg írja le a mögöttes fát. Egy különálló elemekkel rendelkező fa esetén akár a pre-order, akár a post-order és a in-order párosítása elegendő a fa egyértelmű leírásához. A pre-order és a post-order azonban némi kétértelműséget hagy a fa szerkezetében.

Generic treeEdit

Hogy bármely fán mélységi kereséssel haladjunk végig, minden egyes csomóponton végezzük el a következő műveleteket:

  1. Ha nincs csomópont, return.
  2. Access (= visit) node (pre-order position).
  3. For each i from 1 to number_of_children – 1 do:
    1. Recursively traverse i-th child.
    2. Elérjük a csomópontot (sorrendbeli pozíció).
  4. Rekurzívan végigjárjuk az utolsó gyermeket.
  5. Elérjük a csomópontot (sorrend utáni pozíció).

Az adott problémától függően a pre-order, post-order, és különösen a (number_of_children – 1) in-order műveletek közül az egyik lehet üres, vagy csak egy adott gyermekhez akarunk hozzáférni, így ezek a műveletek opcionálisak. A gyakorlatban a pre-order, in-order és post-order műveletek közül egynél többre is szükség lehet. Például egy terner fába való beszúráskor az elemek összehasonlításával egy előrendelési műveletet hajtunk végre. Ezt követően szükség lehet egy post-order műveletre a fa újbóli kiegyensúlyozásához.

Breadth-first search, or level orderEdit

Level-order: F, B, G, A, D, I, C, E, H.

Főcikk: Breadth-first search

A fákat szint-sorrendben is bejárhatjuk, amikor egy szint minden csomópontját meglátogatjuk, mielőtt egy alacsonyabb szintre lépnénk. Ezt a keresést nevezzük szélesség-első keresésnek (BFS), mivel a keresési fát minden egyes mélységen a lehető legnagyobb mértékben kiszélesítjük, mielőtt a következő mélységre lépnénk.

Egyéb típusokSzerkesztés

Léteznek olyan faátjárási algoritmusok is, amelyek nem sorolhatók sem a mélység-első kereséshez, sem a szélesség-első kereséshez. Az egyik ilyen algoritmus a Monte Carlo fakeresés, amely a legígéretesebb lépések elemzésére koncentrál, a keresési fa bővítését a keresési tér véletlenszerű mintavételezésére alapozva.

Similar Posts

Vélemény, hozzászólás?

Az e-mail-címet nem tesszük közzé.