Puu (tietorakenne)

Puu on yksi tietojenkäsittelytieteen  laajimmin käytetyistä tietorakenteista , joka emuloi puurakennetta yhdistettyjen solmujen joukkona. Se on yhdistetty graafi , joka ei sisällä syklejä. Useimmat lähteet lisäävät myös ehdon, että graafin reunoja ei saa suunnata. Näiden kolmen rajoituksen lisäksi joissakin lähteissä sanotaan, että graafin reunoja ei saa painottaa.

Määritelmät

• Juurisolmu  on puun ylin solmu (esimerkissä solmu 8).
• Juuri  on tarkkailijan pyynnöstä yksi kärkeistä.

• Lehti , lehti tai lehtisolmu - solmu , jolla ei ole lapsia (solmut 1, 4, 7, 13).

• Sisäinen solmu  on mikä tahansa puun solmu , jolla on lapsia ja joka ei siten ole lehtisolmu (3, 6, 10, 14).

Puun sanotaan olevan suunnattu , jos mikään reuna ei mene juureen.

• Täysi ketjutettu avain  on tietueen tunniste, joka muodostetaan ketjuttamalla kaikki päätietueiden (ryhmien) instanssien avaimet.

Solmut

Solmu on ilmentymä jommastakummasta kahdesta graafisen elementin tyypistä, joka vastaa jonkin kiinteän luonteisen objektia. Solmu voi sisältää arvon, tilan tai esityksen yksittäisestä tietorakenteesta tai itse puusta. Jokaisella puusolmulla on nolla tai useampi alisolmu , jotka ovat alempana puussa (sopimuksen mukaan puut "kasvavat" alas, eivät ylös, kuten todelliset puut tekevät). Solmua, jolla on lapsi, kutsutaan sen lapsen pääsolmuksi (tai edeltäjäsolmuksi tai vanhemmaksi solmuksi). Jokaisella solmulla on enintään yksi vanhempi. Solmun korkeus on laskevan polun enimmäispituus kyseisestä solmusta alimpaan solmuun (reunasolmuun), jota kutsutaan lehdeksi . Juurisolmun korkeus on yhtä suuri kuin koko puun korkeus. Solmun sisäkkäisyyssyvyys on yhtä suuri kuin polun pituus juurisolmuun.

Juurisolmut

Solmua, jolla ei ole esi-isiä (ylimpänä), kutsutaan juurisolmuksi . Tämä on solmu, josta useimmat puun toiminnot alkavat (vaikka jotkin algoritmit alkavat "lehdistä" ja toimivat, kunnes ne saavuttavat juuren). Kaikkiin muihin solmuihin pääsee siirtymällä juurisolmusta reunoja (tai linkkejä) pitkin (muodollisen määritelmän mukaan jokaisen tällaisen polun on oltava yksilöllinen). Kaavioissa se on yleensä kuvattu aivan yläosassa. Joissakin puissa, kuten kasoissa , juurisolmulla on erityisiä ominaisuuksia. Jokaista puusolmua voidaan pitää siitä solmusta "kasvavan" alipuun juurisolmuna.

Alipuut

Alipuu  on osa puumaista tietorakennetta, joka voidaan esittää erillisenä puuna. Mikä tahansa puun T solmu yhdessä kaikkien sen jälkeläisten solmujen kanssa on puun T alipuu . Jokaisella alipuun solmulla on joko oltava polku kyseisen alipuun juurisolmuun tai itse solmun on oltava juurisolmu. Toisin sanoen alipuu liittyy juurisolmuun kokonaisen puun avulla, ja alipuun suhde kaikkiin muihin solmuihin määritellään vastaavan alipuun käsitteen kautta (analogisesti termin "vastaava osajoukko " kanssa).

Puiden järjestäminen

Puita on kahta päätyyppiä. Rekursiivisessa puussa tai järjestämättömässä puussa vain itse puun rakenteella on merkitystä, ottamatta huomioon kunkin solmun lasten järjestystä. Puuta, jossa järjestys on annettu (esimerkiksi jokaiselle jälkeläiseen johtavalle reunalle on määritetty eri luonnollinen numero ), kutsutaan puuksi nimetyillä reunoilla tai järjestetyksi puuksi , jonka tietorakenne on annettu ennen nimeämistä, jota kutsutaan järjestetyksi puutietorakenteeksi . .

Järjestätyt puut ovat puurakenteista yleisimpiä. Binäärihakupuu  on eräänlainen järjestetty puu.

Puiden esitys

Puita voidaan esittää monella eri tavalla. Yleisin esitys kuvaa solmut tietueina, jotka sijaitsevat dynaamisesti allokoidussa muistissa ja osoittavat niiden jälkeläisiä, esivanhempia (tai molempia) tai taulukon elementteinä , jotka on linkitetty toisiinsa niiden sijainnin määrittämillä suhteilla (esimerkiksi binäärikeko ). ) .

Puut kaavioina

Graafiteoriassa puu  on yhdistetty asyklinen graafi . Juurettu puu on graafi, jonka juureksi on valittu kärkipiste . Tässä tapauksessa mitkä tahansa kaksi kärkeä, jotka on yhdistetty reunalla, perivät emo-lapsi-suhteen. Yksinomaan puista muodostuvaa irrotettua kuvaajaa kutsutaan metsäksi .

Ratkaisut

Puuelementtien vaiheittaista luettelointia kantasolmujen ja jälkeläisten solmujen välisten linkkien varrella kutsutaan puun läpikulkuksi . Usein toiminto voidaan suorittaa viemällä osoitin yksittäisten solmujen yli. Läpikulkua, jossa jokainen esi-isolmu etsitään ennen sen jälkeläisiä, kutsutaan ennalta määrätyksi läpikäymiseksi tai suorassa järjestyksessä kulkemiseksi (ennakkotilauskävely), ja kun katsotaan ensin jälkeläisiä ja sitten esi-isiä, niin läpikulkua kutsutaan postiksi . -järjestetty läpikulku tai läpikulku käänteisessä järjestyksessä (post-order walk). On myös symmetrinen traversal , joka vierailee ensin vasemmassa alipuussa, sitten solmussa ja sitten oikeassa alipuussa, ja leveysläpikulku , joka vierailee solmuissa taso tasolta (puun N:s taso on joukko solmuja, joiden korkeus on N ). Jokainen taso kulkee vasemmalta oikealle.

Yleiset toiminnot

• uuden elementin lisääminen tiettyyn kohtaan;
• alipuun lisäys;
• puun oksan lisääminen (kutsutaan oksaksi );
• löytää minkä tahansa solmun juurielementti;
• kahden kärjen pienimmän yhteisen esi-isän löytäminen ;
• puun kaikkien elementtien luettelointi;
• puun oksan elementtien luettelointi;
• etsi isomorfinen alipuu;
• elementtihaku;
• puun oksan poistaminen (kutsutaan karsimiseksi );
• alipuun poistaminen;
• elementin poistaminen.

Yleinen sovellus

• tietohierarkian hallinta ;
• tiedonhaun yksinkertaistaminen (katso puun läpikulku );
• lajiteltujen tietoluetteloiden hallinta ;
• aritmeettisten lausekkeiden jäsentäminen ( englanniksi  parsing ), ohjelman optimointi ;
• teknologiana digitaalisten kuvien järjestämiseksi erilaisten visuaalisten tehosteiden saamiseksi ;
• monivaiheisen päätöksenteon muoto (katso bisnesshakki ).

Katso myös

• Avaruuden binaarinen osiointi
• Kasa (tietorakenne)
• Puu (graafiteoria)
• Puu (joukkoteoria)
• puun rakenne
• etuliite puu
• eksponentiaalinen puu

• binäärinen puu

• AA puu
• AVL puu
• Puna-musta puu
• laajeneva puu
• puu sakkoilla

• B-puu ( 2-3-puu , B+-puut , B* -puu , UB-puu )
• DSW-algoritmi
• tanssiva puu
• sivustatuli
• sekoitettu puu
• k-ulotteinen puu
• oktreen
• quadtree
• R-puu (tietorakenne)
• Päällystyspuu
• Jäännöspuu
• segmenttipuu
• Passilista
• T-puu
• T-pyramidi
• huippupuu
• van Emde Boas -puu
• Ommeltu binääripuu
• Luettelo tietorakenteista (puista)

Muistiinpanot

Kirjallisuus

• Donald E. Knuth . Luku 2.3. Puut // Ohjelmoinnin taito = The Art of Computer Programming. - 3. painos - M .: Williams , 2002. - T. 1. Perusalgoritmit. – 720 s. — ISBN 5-8459-0080-8 (venäjä) ISBN 0-201-89683-4 (englanniksi).
• Thomas Cormen , Charles Leiserson , Ronald Rivest , Clifford Stein . Johdatus algoritmeihin. - 2. painos. - MIT Press, McGraw-Hill, 2001. - ISBN 0-262-03293-7 .
  • Kohta 10.4: Esittää juurtuneita puita, s. 214-217.
  • Luvut 12-14 (Binaarihakupuut, puna-mustat puut, tietorakenteiden lisääminen), s. 253-320.

Linkit

• Binääripuiden läpikulku
• Punamustat puut