Puun läpikulku

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. joulukuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Puun läpikulku (tunnetaan myös nimellä puuhaku ) on eräänlainen graafin läpikulku , joka aiheuttaa prosessin, jossa vieraillaan (tarkistetaan ja/tai päivitetään) datapuurakenteen jokaisessa solmussa täsmälleen kerran. Tällaiset läpikäynnit luokitellaan sen järjestyksen mukaan, jossa solmuissa vieraillaan. Artikkelin algoritmit viittaavat binääripuihin , mutta ne voidaan yleistää muihin puihin.

Tyypit

Toisin kuin linkitetyt luettelot , yksiulotteiset taulukot ja muut lineaariset tietorakenteet , jotka kuljetetaan kanonisesti lineaarisessa järjestyksessä, puita voidaan kulkea useilla eri tavoilla. Puut voidaan ohittaa "syvyydestä" tai "leveydestä". On kolme päätapaa ohittaa "syvä"

Tietorakenteet puun läpikulkua varten

Puun läpikulku kulkee iteratiivisesti kaikkien solmujen läpi jonkin algoritmin mukaan. Koska annetusta solmusta on useampi kuin yksi seuraava solmu (tämä ei ole lineaarinen tietorakenne), niin peräkkäisiä (eikä rinnakkaisia) laskelmia oletetaan lykätä, eli tallentaa jollain tavalla myöhempää käyntiä varten. Tämä tehdään usein pinon (LIFO = viimeinen sisään, ensimmäinen ulos) tai jonon (FIFO = ensimmäinen sisään, ensimmäinen ulos) avulla. Koska puu on itseviittaava (itseviittaava, rekursiivisesti määritelty) tietorakenne, läpikulku voidaan määritellä rekursiolla tai hienovaraisemmin korekursiolla luonnollisella ja selkeällä tavalla. Näissä tapauksissa odottavat solmut tallennetaan joko eksplisiittisesti tavalliseen pinoon , implisiittisesti puhelupinoon tai eksplisiittisesti jonoon .

Syvyys-ensimmäinen haku toteutetaan helposti pinon kautta, mukaan lukien toteutus rekursion kautta (puhelupino), kun taas leveyshaku on helppo toteuttaa jonon kautta, mukaan lukien toteutus corecursion kautta.

Syvyys ensimmäinen haku

Näitä hakuja kutsutaan syvyys-ensimmäisiksi hauiksi , koska hakupuu kuljetetaan niin pitkälle kuin mahdollista jokaisen jälkeläisen kohdalla ennen siirtymistä seuraavaan sisarukseen. Binääripuulle ne määritellään operaatioiksi, joilla käsitellään kärkipiste rekursiivisesti jokaisessa solmussa, alkaen juuresta. Ohitusalgoritmi on seuraava [2] [3]

Perusrekursiivinen lähestymistapa (ei-tyhjän) binääripuun läpikulkuun: Aloita solmusta N, toimi seuraavasti:

(L) Siirrä vasen alipuu rekursiivisesti. Tämä vaihe päättyy, kun se osuu jälleen solmuun N.

(R) Siirrä oikeanpuoleinen alipuu rekursiivisesti. Tämä vaihe päättyy, kun se osuu jälleen solmuun N.

(N) Prosessisolmu N itse.

Nämä vaiheet voidaan tehdä missä tahansa järjestyksessä . Jos (L) esiintyy ennen (R), prosessia kutsutaan vasemmalta oikealle kulkemiseksi, muussa tapauksessa oikealta vasemmalle kulkemiseksi. Seuraavat menetelmät näyttävät kuljetuksia vasemmalta oikealle:

Suora ohitus (NLR)
  1. Tarkista, onko nykyinen solmu tyhjä vai tyhjä.
  2. Näytä juuren (tai nykyisen solmun) tietokenttä.
  3. Kulje vasemman alipuun läpi rekursiivisesti kutsumalla suora läpikulkufunktio.
  4. Kuljemme oikean alipuun rekursiivisesti kutsumalla suoran läpikulkufunktion.
Keskitetty läpikulku (LNR)
  1. Tarkista, onko nykyinen solmu tyhjä vai tyhjä.
  2. Kulje vasen alipuu rekursiivisesti kutsumalla keskitettyä läpikulkufunktiota.
  3. Näytä juuren (tai nykyisen solmun) tietokenttä.
  4. Kulje oikeanpuoleinen alipuu rekursiivisesti kutsumalla keskitettyä läpikulkufunktiota.


Binäärihakupuussa keskitetty läpikulku hakee tiedot lajiteltuun järjestykseen. [4] .

Käänteinen ohitus (LRN)
  1. Tarkista, onko nykyinen solmu tyhjä vai tyhjä.
  2. Kuljemme vasemman alipuun rekursiivisesti kutsumalla käänteisen läpikulkufunktion.
  3. Kuljemme oikean alipuun rekursiivisesti kutsumalla käänteisen läpikulkufunktion.
  4. Näytä juuren (tai nykyisen solmun) tietokenttä.

Läpikulkusekvenssiä kutsutaan puusekvenssiksi. Läpikulkusekvenssi on luettelo kaikista vierailluista solmuista. Mikään eteenpäin-, taaksepäin- tai keskitetyistä sekvensoinneista ei kuvaile puuta yksiselitteisesti. Jos puussa on erilliset elementit, eteenpäin- tai taaksepäin kulkeminen yhdessä keskitetyn läpikulun kanssa riittää kuvaamaan puuta yksilöllisesti. Eteenpäin kulkeminen yhdessä taaksepäin kulkemisen kanssa jättää kuitenkin puurakenteeseen epäselvyyttä [5] .

Yleisnäkymän puu

Jos haluat kulkea minkä tahansa puun läpi syvyysensimmäisellä haulla, seuraavat toiminnot suoritetaan rekursiivisesti kullekin solmulle:

  1. Eteenpäin kulkeva toimenpide on meneillään.
  2. Suoritamme jokaiselle i :lle 1:stä lasten määrään:
    1. Vierailemme i :nnen lapsen luona, jos sellainen on olemassa.
    2. Suoritamme keskitetyn toimenpiteen.
  3. Suoritamme käänteisen ajotoiminnon.

Nykyisestä tehtävästä riippuen eteenpäin-, taaksepäin- tai keskitetty läpikulkuoperaatiot voivat olla tyhjiä tai haluat ehkä käydä vain tietyn lapsen luona, joten nämä toiminnot ovat valinnaisia. Käytännössä voidaan tarvita useampi kuin yksi eteenpäin-, taaksepäin- tai keskitetty poikkioperaatio. Esimerkiksi kolmipuuhun lisättäessä eteenpäin kulkeva operaatio suoritetaan vertaamalla elementtejä. Tämän jälkeen voidaan vaatia paluutoimintoa puun tasapainottamiseksi.

Leveys ensimmäinen haku

Puita voidaan myös kulkea tasojärjestyksessä , jolloin käymme jokaisessa solmussa tasolla ennen siirtymistä seuraavalle tasolle. Tällaista hakua kutsutaan leveys -ensihakuksi (BFS).

Muut tyypit

On myös läpikulkualgoritmeja, joita ei luokitella syvyys- tai leveyshakuiksi. Eräs tällainen algoritmi on Monte Carlo -menetelmä , joka keskittyy lupaavimpien liikkeiden analysointiin hakupuun laajenemisen perusteella samalla kun valitaan satunnaisesti hakuavaruus .

Sovellukset

Eteenpäin kulkeminen solmuja ja reunoja kopioitaessa voi tehdä binääripuun täydellisen kopioinnin . Tämän avulla voidaan luoda etuliitelauseke ( Puolalainen notaatio ) -lausekepuista , joille toistetaan lauseke suorassa järjestyksessä.

Keskitettyä läpikulkua käytetään yleisimmin binäärihakupuissa, koska se palauttaa arvot taustalla olevasta joukosta binäärihakupuun määrittelevän vertailufunktion määrittämässä järjestyksessä.

Käänteinen läpikulku solmujen poistamisen tai vapauttamisen yhteydessä voi poistaa tai vapauttaa koko binaaripuun. Läpikulku luo myös binääripuun postfix -esityksen.

Toteutus

Syvyys ensimmäinen haku

Suora ohitus
ennakkotilaus (solmu) if (solmu = null ) paluu vierailu (solmu) ennakkotilaus (solmu.vasen) ennakkotilaus (solmu oikealla) iterativePreorder (node) if (node ​​​​= null ) return s ← tyhjä pino s.push(solmu) while ( ei s.isEmpty()) solmu ← s.pop() vierailu (solmu) //oikea lapsi työnnetään ensin, joten vasen lapsi käsitellään ensin jos (solmu.oikea ≠ null ) s.push(solmu.oikea) jos (solmu.vasen ≠ null ) s.push(solmu.vasen)
Keskitetty läpikulku
inorder (solmu) if (solmu = null ) return järjestys(solmu.vasen) vierailu (solmu) järjestys (solmu oikealla) iterativeInorder (solmu) s ← tyhjä pino while ( ei s.isEmpty() tai node ≠ null ) if (node≠ null ) s.push(solmu) solmu ← node.left muu solmu ← s.pop() vierailu (solmu) solmu ← node.right
Käänteinen ohitus
postorder (solmu) if (solmu = null ) paluu postorder(solmu.vasen) postorder (solmu oikealla) vierailu (solmu) iterativePostorder (solmu) s ← tyhjä pino lastNodeVisited ← null while ( ei s.isEmpty() tai node ≠ null ) if (node≠ null ) s.push(solmu) solmu ← node.left muu peekNode ← s.peek() // jos oikea lapsi on olemassa ja traversal tuli vasemmasta lapsesta, siirry oikealle if (peekNode.right ≠ null ja lastNodeVisited ≠ peekNode.right) solmu ← peekNode.right muu vierailu (peekNode) lastNodeVisited ← s.pop()

Kaikki yllä olevat toteutukset vaativat puun korkeuteen verrannollisen pinon, joka on rekursiivisen toteutuksen kutsupino ja iteratiivisen toteutuksen pääpino. Huonosti tasapainotetussa puussa tämä pino voi olla merkittävä. Iteratiivisessa toteutuksessa voimme päästä eroon pinosta tallentamalla jokainen solmu sen ylätasoon tai käyttämällä puuompeleita (seuraava osa).

Firmware Centered Morris Bypass

Binääripuu ommellaan antamalla jokaiselle vasemmalle lapsiosoittimelle (joka muuten on aina tyhjä = tyhjä) osoitin solmun edeltäjään keskitetyssä järjestyksessä (jos sellainen on olemassa) ja jokaiselle oikealle lapsiosoittimelle (joka muuten on aina tyhjä) osoitin seuraava solmu keskitetyssä järjestyksessä Keskitetty järjestys (jos sellainen on).

Edut:

  1. Vältämme rekursiota, joka käyttää puhelupinoa ja kuluttaa muistia ja aikaa.
  2. Solmu pitää kirjaa vanhemmistaan.

Virheet:

  1. Puu on monimutkaisempi.
  2. Voimme tehdä vain yhden läpikulkuvaiheen kerrallaan.
  3. Suurempi mahdollisuus virheille, kun molemmat lapset puuttuvat ja molemmat solmuosoittimet osoittavat esivanhempia.

Morris walk on keskitetyn kävelyn toteutus laiteohjelmistolla [6] :

  1. Linkit jälkeläisiin luodaan keskitetyssä järjestyksessä.
  2. Tiedot tulostetaan näiden linkkien mukaan.
  3. Muutokset hylätään palatakseen alkuperäiseen puuhun.

Leveys ensimmäinen haku

Alla on pseudokoodi yksinkertaiselle jonopohjaiselle kerros kerrokselta läpikulkua varten. Algoritmi vaatii tilaa, joka on verrannollinen tasojen solmujen enimmäismäärään. Tämä arvo voi saavuttaa puolet kaikista solmuista. Muistitehokkaampi lähestymistapa tämäntyyppiseen läpikulkuun voidaan toteuttaa käyttämällä syvyyshakua iteratiivisella syvennyksellä .

tasojärjestys (juuri) q ← tyhjä jono q.enqueue(juuri) while ( ei q.isEmpty()) solmu ← q.dequeue() vierailu (solmu) jos (solmu.vasen ≠ null ) q.enqueue(node.left) jos (solmu.oikea ≠ null ) q.enqueue(solmu.oikea)

Endless Trees

Läpikulku tehdään yleensä puille, joissa on äärellinen määrä solmuja (siis rajallinen syvyys ja rajallinen haarautumiskerroin ), mutta se voidaan tehdä myös äärettömälle puille. Tällainen läpikulku on kiinnostavaa erityisesti toiminnallisessa ohjelmoinnissa ( laiskalle arvioinnille ), koska äärettömiä tietorakenteita voidaan usein helposti määritellä ja käsitellä, vaikka niitä ei voidakaan (tiukkaa) laskea, koska se vie äärettömästi aikaa. Jotkut äärelliset puut ovat liian suuria esitettäväksi selkeästi, kuten shakin tai go -pelipuu , joten niitä on järkevää käsitellä äärettöminä.

Kuljetuksen päävaatimus on käydä kaikissa solmuissa. Yksinkertaiset algoritmit eivät voi tehdä tätä äärettömille puille. Jos esimerkiksi on olemassa binääripuu, jonka syvyys on ääretön, syvyys-ensimmäinen haku liikkuu puun toisella puolella (yleensä vasenta puolta) eikä koskaan vieraile muissa huipuissa, ja lisäksi keskitetty tai taaksepäin suuntautuva läpikulku ei koskaan tapahdu. vierailla missä tahansa solmussa, koska ei koskaan saavuta lehtiä. Sitä vastoin leveys-ensimmäinen läpikulku (taso tasolta) kulkee äärettömän syvän binääripuun läpi ilman ongelmia, ja lisäksi se kulkee minkä tahansa puun läpi, jolla on rajoitettu haarautumiskerroin.

Toisaalta, kun otetaan huomioon puu, jonka syvyys on 2, jossa juurella on ääretön määrä lapsia ja jokaisella lapsisolmulla on kaksi lasta, syvyysensimmäinen haku vierailee kaikissa solmuissa, koska se ohittaa lapsenlapset (toisen lapset). tasolle), siirtyy seuraavaan solmuun (olettaen, että tämä ei ole taaksepäin tapahtuva läpikulku, joka ei koskaan saavuta juuria). Sitä vastoin leveyshaku ei koskaan pääse lastenlapsiin, koska sen on ensin toistettava kaikki lapset (1. taso).

Ajoajan kehittyneempi analyysi voidaan antaa käyttämällä äärettömiä järjestyslukuja . Esimerkiksi leveysensimmäinen haku puussa, jonka syvyys on 2 (kuten edellä), ottaa ω ·2 askelta - ω ensimmäiselle tasolle ja toisen ω toiselle tasolle.

Siten yksinkertaiset syvyys- ja leveyshaut eivät kulje minkään äärettömän puun läpi ja ovat tehottomia erittäin suurilla puilla. Hybridimenetelmät voivat kuitenkin kulkea minkä tahansa (laskettavan) äärettömän puun läpi pääasiassa diagonaaliargumentin kautta ("diagonaali", pystysuoran ja vaakasuuntaisen yhdistelmä, vastaa syvyyshaun ja leveyshaun yhdistelmää).

Tarkemmin sanottuna, kun otetaan huomioon äärettömästi haarautuva, äärettömän syvyys puu, merkitsemme juuren (), juuren lapset (1), (2), ..., lastenlapset (1, 1), (1, 2), ... , (2, 1), (2 , 2), … ja niin edelleen. Solmut ovat tällöin yksi yhteen vastaavuudessa positiivisten lukujen äärellisten (mahdollisesti tyhjien) sarjojen kanssa, joiden joukko on laskettavissa ja voidaan järjestää ensin elementtien summan mukaan ja sitten leksikografisen järjestyksen mukaan tietyn summan omaavien sekvenssien sisällä. (vain äärellinen määrä sekvenssejä antaa tietyn summan, joten kaikki solmut saavutetaan; muodollisesti ottaen tietyn luonnollisen luvun koostumuksia on äärellinen määrä, nimittäin 2 n − 1 koostumusta). Tämä järjestys määrittää puun läpikulkua. Erityisesti:

0: () yksitoista) 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)

jne..

Tämä voidaan tulkita niin, että äärettömän syvän binääripuu kartoitetaan tämän tyyppiseen puuhun ja käytetään leveyshakua - korvaa yläsolmun toiseen ja sitä seuraaviin lapsiin yhdistävät "alas" reunat "oikeilla" reunoilla ensimmäisestä. lapsi toiseen, toisesta kolmanteen ja niin edelleen. Sitten jokaisessa vaiheessa siirrymme joko alas (lisää (, 1) loppuun) tai siirrymme oikealle (lisää yksi viimeiseen numeroon) (paitsi juuri, josta voi mennä vain alas), joka näyttää suhteen äärettömän binääripuun ja yllä olevan numeroinnin välillä. Syötteiden summa (ilman yhtä) vastaa etäisyyttä juuresta, mikä on yhdenmukainen 2 n − 1 solmun ja syvyyden n − 1 kanssa äärettömässä binääripuussa (2 vastaa binääripuuta).

Muistiinpanot

  1. ↑ Luento 8, Tree Traversal . Haettu 2. toukokuuta 2015. Arkistoitu alkuperäisestä 5. elokuuta 2018.
  2. ↑ Arkistoitu kopio . Haettu 29. toukokuuta 2018. Arkistoitu alkuperäisestä 28. elokuuta 2017.
  3. ↑ Ennakkotilaa läpikulkualgoritmi . Haettu 2. toukokuuta 2015. Arkistoitu alkuperäisestä 11. huhtikuuta 2019.
  4. ↑ Wittman, Todd Tree Traversal (PDF)  (linkki ei saatavilla) . UCLA matematiikka . Haettu 2. tammikuuta 2016. Arkistoitu alkuperäisestä 13. helmikuuta 2015.
  5. ↑ Algoritmit, Mitkä pre-, post- ja in-order-sekvensoinnin yhdistelmät ovat ainutlaatuisia?, Computer Science Stack Exchange . Haettu 2. toukokuuta 2015. Arkistoitu alkuperäisestä 12. helmikuuta 2015.
  6. ↑ Morris, 1979 .

Kirjallisuus

  • Joseph M Morris. Binääripuiden läpikulku yksinkertaisesti ja edullisesti // Tietojenkäsittelykirjeet . - 1979. - T. 9 , no. 5 . - doi : 10.1016/0020-0190(79)90068-1 .
  • Nell Dale, Susan D. Lilly. Pascal Plus -tietorakenteet. – Neljäs painos. - Lexington, MA: DC Heath and Company, 1995.
  • Adam Drozdek. Tietorakenteet ja algoritmit C++:ssa. - Toinen painos. - Brook/Cole. Pacific Grove, Kalifornia, 2001.
  • Kormen, Leyzerson, Rivest, Stein. Luku 22. Perusalgoritmit graafien kanssa työskentelyyn // Algoritmit: rakentaminen ja analyysi . - 2. - M .: Williams, 2005. - S. 609 - 643. - 1296 s.

Linkit

 Kaavion hakualgoritmit
Tietämättömät menetelmät
Tietoon perustuvat menetelmät
Pikanäppäimet
Vähintään ulottuva puu
Muut