Puurakenne on yksi tapa esittää hierarkkinen rakenne graafisesti.
Sitä kutsutaan puurakenteeksi, koska graafi näyttää käänteiseltä puulta . Samasta syystä he sanovat, että juurisolmu (juuri) on ylhäällä ja lehdet alareunassa.
Graafiteoriassa puu on yhdistetty asyklinen graafi ( suuntaamattomille graafille) tai yhdistetty asyklinen graafi, jossa korkeintaan yhdessä solmussa ei ole sisääntulevia reunoja ja muissa solmuissa on täsmälleen yksi sisääntuleva solmu (suunnatuille graafiille).
Asyklistä suunnattua graafia, jossa ei ole tiukkaa linkitysehtoa, kutsutaan verkoksi, useiden puiden yhdistämätöntä graafia kutsutaan metsäksi .
Heterogeeniset semanttiset verkot koostuvat joukosta puumaisia rakenteita .
Jokainen lehtipuu sisältää elementin, jolla ei ole yläosaa . Tätä elementtiä kutsutaan "juureksi" tai "juurisolmuksi" . Sitä voidaan pitää ensimmäisenä (tai aloitussolmuna).
Päinvastoin ei yleensä pidä paikkaansa: äärettömillä puurakenteilla voi olla tai ei ole juurisolmuja.
Elementtejä yhdistäviä viivoja kutsutaan "haaroiksi" ja itse elementtejä solmuiksi . Solmuja, joilla ei ole lapsia, kutsutaan "lehtisolmuiksi" tai "lehdiksi".
Solmujen välisten linkkien nimet on nimetty perhesuhteiden periaatteen mukaisesti.
Lännessä tietojenkäsittelytieteen alalla käytetään pääosin vain maskuliinisten perheenjäsenten nimiä; venäjäksi nimeämään solmua, joka liittyy suoraan pääsolmuun ja on hierarkiassa alempana, kutsutaan usein "lapseksi". ".
Kielitieteessä (esim. englanniksi) päinvastoin käytetään naispuolisten perheenjäsenten nimiä. Tämä osoittaa paluuta yhteiseen nimeämiskäytäntöön, jota sponsoroivat kuuluisan amerikkalaisen kielitieteilijän Noam Chomskyn opiskelijat . Tästä huolimatta tietojenkäsittelytieteessä neutraalit nimet "vanhempi" ja "lapsi" korvataan usein sanoilla "isä" ja "poika", lisäksi termiä "setä" käytetään yhtä aktiivisesti viittaamaan muihin solmuihin, jotka ovat samalla tasolla vanhempien kanssa.
Yllä olevassa esimerkissä "ensyklopedia" on "tieteen" ja "kulttuurin" vanhempi, jotka ovat vastaavasti sen "lapsia". "Taide" ja "käsityö" ovat veljiä suhteessa toisiinsa ja lapset "kulttuuriin".
Puurakenteita käytetään näyttämään kaikenlaista taksonomian alan tietoa , kuten sukupuuta , fylogeneettistä puuta , kielen kielioppirakennetta (esim. englanniksi hyvä esimerkki on kaava S → NP VP, mikä tarkoittaa, että lause (lause) on substantiivilause (substantiivilause) ja verbiryhmä (verbilause), tapa järjestää loogisesti sivuston verkkosivuja ja niin edelleen.
Puurakenteessa voi olla yksi ja vain yksi polku pisteestä toiseen pisteeseen.
Puurakenteita käytetään laajalti tietojenkäsittelytieteessä (katso Tree (tietorakenne) ja viestintä (tekniikka) ).
Puurakenteen solmujen välillä voi olla erilaisia semanttisia suhteita .
Todellisissa tietosanakirjoissa ( Wikipedia ) kaikki tällaiset DS:t esiintyvät vastakkainasetteluina, jos niiden esitysjärjestelmää ei ole mietitty erikseen ja kokonaisuutena.
Wikipedian artikkelien temaattisesti homogeenisten ryhmien rakenteessa käytetään erilaisia linkkejä . Aluksi tunnistetaan osiot, jotka eroavat esineiden esineiden ilmestymisajasta (Eloton luonto, Villieläin, Ihmiskunta, Teknosfääri), sitten käytetään osien sisäisiä rakennetasojen välisiä linkkejä, homogeenisten esineiden välisiä linkkejä (sukulajit), viimeinen hierarkiassa käytetään ryhmän artikkelien määrää.
On monia tapoja esittää puurakenteita graafisesti. Useimmissa tapauksissa ne perustuvat useiden perustyylien erilaisiin muunnelmiin tai yhdistelmiin:
Joidenkin perusmenetelmien kuvaukset löytyvät osoitteesta:
| Puu (tietorakenne) | |
|---|---|
| Binääripuut | |
| Itsetasapainottavat binaaripuut |
|
| B-puut | |
| etuliite puita |
|
Avaruuden binaarinen osiointi | |
| Ei-binääripuut |
|
| Avaruuden hajottaminen |
|
| Muut puut |
|
| Algoritmit | |