Puiden läpikäynti

Toisin kuin linkitetyt listat, yksiulotteiset matriisit ja muut lineaariset tietorakenteet, jotka läpikäydään kanonisesti lineaarisessa järjestyksessä, puita voidaan läpikäydä usealla eri tavalla. Ne voidaan läpikäydä syvyysjärjestyksessä tai leveysjärjestyksessä. Syvyysjärjestyksessä on kolme yleistä tapaa: in-order, pre-order ja post-order. Näiden perusjärjestysten lisäksi on mahdollista käyttää erilaisia monimutkaisempia tai hybridejä järjestelmiä, kuten syvyysrajattuja hakuja, kuten iteratiivista syventävää syvyys-ensimmäistä hakua. Jälkimmäistä, samoin kuin leveys-ensimmäistä hakua, voidaan käyttää myös äärettömien puiden läpikäymiseen, ks. alla.

Tietorakenteet puun läpikäymistä vartenMuokkaa

Puun läpikäymiseen kuuluu kaikkien solmujen läpikäyminen iteroimalla ne jollain tavalla. Koska tietystä solmusta on useampi kuin yksi mahdollinen seuraava solmu (se ei ole lineaarinen tietorakenne), niin olettaen peräkkäistä laskentaa (ei rinnakkaista), joitakin solmuja on lykättävä-varastoitava jollain tavalla myöhempää vierailua varten. Tämä tapahtuu usein pinon (LIFO) tai jonon (FIFO) avulla. Koska puu on itseensä viittaava (rekursiivisesti määritelty) tietorakenne, sen läpikäynti voidaan määritellä rekursiolla tai hienovaraisemmin ydinkurssiolla hyvin luonnollisella ja selkeällä tavalla; näissä tapauksissa lykätyt solmut tallennetaan implisiittisesti kutsupinoon.

Syvyys-ensimmäinen haku on helppo toteuttaa pinon kautta, myös rekursiivisesti (kutsupinon kautta), kun taas laajuus-ensimmäinen haku on helppo toteuttaa jonon kautta, myös ydinkursiivisesti.:45-61

Binääripuun syvyysetsintäEdit

Binääripuun syvyysetsintä (katkoviivainen polku):

• Esijärjestys (solmun haku positiossa punainen ●):

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

• Sisäjärjestys (solmuun pääsy kohdassa vihreä ●):

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

• Jälkijärjestys (solmuun pääsy kohdassa sininen ●):

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

Näistä hauista käytetään nimitystä syvyyshaku (depth-first search, DFS), koska hakupuuta syvennetään mahdollisimman paljon jokaisessa lapsessa ennen kuin siirrytään seuraavaan sisarukseen. Binääripuulle ne määritellään pääsyoperaatioina jokaisessa solmussa alkaen nykyisestä solmusta, jonka algoritmi on seuraava:

Yleinen rekursiivinen malli binääripuun läpikäymiseen on seuraava:

1. Mene yhden tason alaspäin rekursiiviseen argumenttiin N. Jos N on olemassa (on ei-tyhjä) suorita seuraavat kolme operaatiota tietyssä järjestyksessä: L: Kierrä rekursiivisesti N:n vasen alipuu. R: Kierretään rekursiivisesti N:n oikea alipuu. N: Käytetään (vieraillaan) itse nykyisessä solmussa N.
2. Paluu menemällä yhden tason ylöspäin ja saapumalla N:n vanhemmalle solmulle.

On kolme tapaa (mallia), millä parcoursin (traversaalin) sijainnilla solmuun nähden (kuvassa: punainen, vihreä tai sininen) solmun vierailu (access) tapahtuu. Täsmälleen yhden värin valinta määrittää täsmälleen yhden vierailun solmuun jäljempänä kuvatulla tavalla. Pääsy kaikilla kolmella värillä johtaa saman solmun kolminkertaiseen käyntiin, jolloin saadaan ”all-order”-järjestys:

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

Pre-order, NLREdit

1. Käytiin nykyisen solmun dataosaan (kuvassa: paikka punainen).
2. Kierretään vasen alipuu kutsumalla rekursiivisesti preorder-funktiota.
3. Kierretään oikea alipuu kutsumalla rekursiivisesti preorder-funktiota.

Esijärjestyksen mukainen läpikäynti on topologisesti lajiteltu, koska vanhempisolmua käsitellään ennen kuin mitään sen lapsisolmua käsitellään.

In-order, LNREdit

1. Läpikäytä vasen alipuu kutsumalla rekursiivisesti in-order-funktiota.
2. Käytetään nykyisen solmun dataosaa (kuvassa: sijainti vihreä).
3. Kierretään oikea alipuu kutsumalla rekursiivisesti in-order-funktiota.

Binäärisessä hakupuussa, joka on järjestetty siten, että jokaisessa solmussa avain on suurempi kuin kaikki sen vasemman alipuun avaimet ja pienempi kuin kaikki sen oikean alipuun avaimet, in-order traversal hakee avaimet nousevassa lajittelujärjestyksessä.

Reverse in-order, RNLEdit

1. Kiertää oikean alipuun rekursiivisesti kutsumalla käänteisen järjestyksen funktiota.
2. Käyttää nykyisen solmun dataosaa.
3. Kiertää vasemman alipuun rekursiivisesti kutsumalla käänteisen järjestyksen funktiota.

Binäärisessä hakupuussa käänteinen in-order traversal hakee avaimet laskevassa lajittelujärjestyksessä.

Post-order, LRNEdit

1. Kierrä vasen alipuu kutsumalla rekursiivisesti post-order-funktiota.
2. Kierretään oikeanpuoleinen alipuu kutsumalla rekursiivisesti post-order-funktiota.
3. Päästään käsiksi nykyisen solmun dataosaan (kuvassa: sijainti sininen).

Kierron jälkeä kutsutaan puun sekvensoinniksi. Traversaalijälki on luettelo jokaisesta käydystä solmusta. Mikään esi-, sisä- tai jälkijärjestyksen mukainen järjestys ei kuvaa taustalla olevaa puuta yksiselitteisesti. Kun kyseessä on puu, jossa on erillisiä elementtejä, joko pre-order tai post-order yhdessä in-orderin kanssa riittää kuvaamaan puun yksiselitteisesti. Pre-järjestys post-järjestyksen kanssa jättää kuitenkin jonkin verran epäselvyyttä puun rakenteeseen.

Generic treeEdit

Kävelläksesi minkä tahansa puun läpi syvyyssuuntaisella haulla, suorita seuraavat operaatiot jokaisessa solmussa:

1. Jos solmua ei ole, palaa.
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. Käyrä solmuun (järjestyksen sisäinen sijainti).
4. Käyrä rekursiivisesti läpi viimeinen lapsi.
5. Käyrä solmuun (järjestyksen jälkeinen sijainti).

Käsillä olevasta ongelmasta riippuen esijärjestys, jälkijärjestys ja erityisesti jokin (number_of_children – 1) in-order-operaatioista voi olla mitätön, tai halutaan pääsy vain tiettyyn lapseen, joten nämä operaatiot ovat valinnaisia. Käytännössä voidaan myös tarvita useampi kuin yksi pre-order-, in-order- ja post-order-operaatioista. Kun esimerkiksi lisätään kolminkertaiseen puuhun, järjestystä edeltävä operaatio suoritetaan vertailemalla kohteita. Jälkijärjestysoperaatiota saatetaan tarvita jälkikäteen puun tasapainottamiseksi uudelleen.

Breadth-first search, or level orderEdit

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

Puita voidaan käydä läpi myös tasojärjestyksessä, jolloin käydään jokaisessa tason solmussa ennen kuin siirrytään alemmalle tasolle. Tätä hakua kutsutaan nimellä breadth-first search (BFS), koska hakupuuta laajennetaan mahdollisimman paljon jokaisella syvyydellä ennen seuraavalle syvyydelle siirtymistä.

Muita tyyppejäEdit

On olemassa myös puiden läpikäyntialgoritmeja, joita ei luokitella syvyyssuuntaiseksi eikä leveyssuuntaiseksi hauksi. Yksi tällainen algoritmi on Monte Carlo -puunhaku, joka keskittyy lupaavimpien siirtojen analysointiin ja perustaa hakupuun laajentamisen satunnaisotantaan hakuavaruudesta.