Ommeltu binääripuu on muunnos binääripuusta, joka mahdollistaa nopean läpikäynnin – kun ommeltu puun solmu osoittaa, seuraava (ja/tai edellinen) solmu löytyy helposti järjestyksessä .
Binääripuita, mukaan lukien (mutta ei rajoittuen) binäärihakupuut ja niiden muunnelmat, voidaan käyttää useiden elementtien tallentamiseen tietyssä järjestyksessä. Esimerkiksi binäärihakupuu olettaa, että tietoelementit on järjestetty jollain tavalla, ja säilyttää järjestyksen, kun ne lisätään ja poistetaan. Eräs hyödyllinen operaatio tällaisessa puussa on traversal eli puun elementtien vierailu siinä järjestyksessä, jossa ne muistetaan (joka vastaa solmujen järjestystä binäärihakupuun tapauksessa).
Yksinkertainen rekursiivinen läpikulkualgoritmi, joka vierailee binaarihakupuun jokaisessa solmussa, on seuraava. Oletetaan , että t on osoitin solmuun tai nolla . "Visit" t voi tarkoittaa mitä tahansa toimintoa tämän solmun t tai sille määrätyn sisällön kanssa.
Läpikulkualgoritmi( t ):
Tämän algoritmin ongelmana on, että rekursiosta johtuen algoritmi käyttää pinotilaa suhteessa puun korkeuteen. Jos puu on huonosti tasapainotettu, tämä arvo saavuttaa O (log n ) n elementin puulle . Pahimmassa tapauksessa, kun puu on ketjun muotoinen, puun korkeus on n , joten algoritmi vaatii O ( n ) pinotilaa .
Vuonna 1968 Donald Knuth kysyi, oliko olemassa ei-rekursiivista keskitettyä läpikulkualgoritmia, joka ei käyttänyt pinoa ja jätti puun ennalleen. Yksi ratkaisu tähän ongelmaan on puiden ompeleminen, jonka James H. Morris esitteli vuonna 1979 [1] [2] .
Ommeltu puu määritellään seuraavasti:
"Binääripuu ommellaan määrittämällä kaikki oikeat lapsiosoittimet, jotka normaalisti olisivat nollaosoittimia, osoittimille solmun seuraavaan solmuun ( jos sellaisia on) ja kaikki vasemmanpuoleiset lapsiosoittimet, jotka normaalisti olisivat nollaosoittimia, osoittimille edellisiin solmuihin. tilauksessa" [3] .
On myös mahdollista löytää solmun emo nidotusta binääripuusta ilman, että käytetään nimenomaista osoitinta pää- tai pinoon, vaikka se on hitaampaa. Tämä on hyödyllistä, kun pino on rajoitettu tai kun yläosoittimien pino ei ole käytettävissä (emoosoittimen löytämiseksi syvyys -ensin hakua käyttämällä ).
Jos haluat nähdä, kuinka tämä on mahdollista, harkitse solmua k , jolla on oikea lapsi r . Tällöin solmun vasemman osoittimen r on oltava joko lapsi tai osoitin takaisin kohtaan k . Siinä tapauksessa, että r :llä on vasen lapsi, vasemmalla lapsella on oltava oma vasen lapsi tai osoitin takaisin kohtaan k , ja niin edelleen kaikille myöhemmille vasemmalle lapsille. Näin ollen käymällä läpi vasemman osoittimien ketjun r :stä peräkkäin , löydämme lopulta ommelosoittimen takaisin kohtaan k . Tilanne on symmetrinen, kun q on p :n vasen lapsi , jolloin voimme jäljittää solmun q oikeat lapset, jolloin saadaan laiteohjelmistoosoitin p :hen .
Python- kielellä :
def vanhempi ( solmu ): jos solmu on solmu . puu . juuri : return Ei mitään muuta : x = solmu y = solmu while True : jos on_säie ( y ): p = y . oikein , jos p on Ei mitään tai p . vasen ei ole solmu : p = x , mutta ei ole lanka ( p . vasen ): p = p . vasen p = p . vasen paluu p elif on_säie ( x ): p = x . vasemmalle , jos p on Ei mitään tai p . oikea ei ole solmu : p = y , mutta ei ole lanka ( p . oikea ): p = p . oikea p = p . oikea paluu p x = x . vasen y = y . oikeinLaiteohjelmisto on linkit tietyn solmun edelliseen ja seuraavaan solmuun keskitetyn läpikäynnin mukaisesti.
Jos ommeltu puujärjestys on ABCDEFGHI, D-solmu tulee ennen E-solmua ja F seuraa E-solmua.
Yritetään muodostaa ommeltu puu tavallisesta binääripuusta
Yllä olevan puun keskitetty poikkipiste on DBAE C. Eli vastaava ommeltu binääripuu näyttäisi tältä
M-ommeltu binääripuu, jossa on n solmua, on n*m (n-1) nollalinkkiä.
Ei-rekursiivisena läpikulkumenetelmänä menetelmän tulee olla iteratiivinen proseduuri, kaikkien solmujen läpikulkuvaiheiden on oltava silmukassa, jotta samaa voidaan soveltaa kaikkiin puun solmuihin. Oletamme jälleen keskitetyn puun kulkemisen. Sitten minkä tahansa solmun kohdalla ohitamme ensin vasemman alipuun (jos se on olemassa ja jos emme ole kulkeneet sitä aiemmin). Sitten vierailemme (eli tulostamme tapauksessamme solmujen arvon) itse solmussa ja vasta sitten kuljemme oikean alipuun läpi (jos se on olemassa). Jos oikeaa puuta ei ole, tarkista ommeltu linkki ja tee ommeltu kärkipiste tarkasteltavaksi nykyiseksi solmuksi. Katso esimerkki alla.
Vaihe 1: Tarkista nykyisen solmun kohdalla, onko siellä vasemmalla oleva lapsi, joka ei ole vierailijoiden luettelossa. Jos sellainen on, siirry vaiheeseen 2, muussa tapauksessa siirry vaiheeseen 3.
Vaihe 2: Aseta vasen lapsi vierailtujen solmujen luetteloon ja tee siitä nykyinen solmu. Jatketaan vaiheeseen 6.
Vaihe 3: Tulosta solmu ja jos solmulla on oikea lapsi, siirry vaiheeseen 4, muussa tapauksessa siirry vaiheeseen 5.
Vaihe 4: Tee oikeasta lapsesta nykyinen solmu.
Vaihe 5: Jos laiteohjelmistosolmu on olemassa, tee siitä nykyinen solmu.
Vaihe 6: Jos kaikki solmut on tulostettu, poistu, muussa tapauksessa siirry vaiheeseen 1.
| Lista | ||||
|---|---|---|---|---|
| vaihe 1 | A :lla on vasen lapsi eli B , jossa ei ole vielä käynyt, joten laitamme B :n "vierailtujen solmujen luetteloomme" ja B :stä tulee nykyinen solmu. | B | ||
| vaihe-2 | B :llä on myös vasen lapsi D , joka ei ole vierailtujen solmujen luettelossa. Laitamme D :n vierailijoiden luetteloon ja päivitämme sen. | BD | ||
| vaihe-3 | Solmulla D ei ole vasenta lasta, joten tulostetaan D ja sitten tarkistetaan oikea lapsi. D :llä ei ole oikeaa lasta, joten katsomme linkin linkin. Solmulla on laiteohjelmisto solmulle B , joten tee B :stä nykyinen. | BD | D | |
| vaihe-4 | B :llä on vasen lapsi, mutta sen luona on jo käyty. Joten tulostamme B , sitten tarkistamme oikean lapsen, mutta sellaista ei ole, joten ommeltu solmu (eli A ) tehdään nykyiseksi. | BD | D.B. | |
| vaihe-5 | A :lla on vasen lapsi B , mutta siellä on jo käyty, joten tulostamme A:n ja tarkistamme oikean lapsen. Solmulla A on oikea lapsi C , eikä se ole vierailtujen solmujen luettelossa, joten lisäämme sen tähän luetteloon ja teemme siitä ajan tasalla. | bdc | DBA | |
| vaihe-6 | C :n vasen lapsi on solmu E , eikä tässä solmussa ole vielä vieraillut, joten lisää solmu E luetteloon ja tee siitä ajan tasalla. | B D C E | D B A | |
| vaihe-7 | vihdoin….. | D B A E C |