Puu (tietorakenne)

Yksinkertainen järjestämätön puu. Esimerkiksi solmulla, jonka arvo on 7, on kaksi lasta, arvoiltaan 2 ja 6, sekä yksi vanhempi, arvoltaan 2.

Puu on tietorakennetyyppi, joka koostuu puurakenteen muodostavista hierarkisesti toisiinsa linkitetyistä solmuista. Solmut tyypillisesti järjestetään puiksi. Solmu edustaa yhden tietorakenteen tietoa, esimerkiksi arvon, ehdon tai mahdollisesti toimii toisena itsenäisenä tietorakenteena. Puurakenteen korkein solmu edustaa kaikkia alempia lapsisolmuja. Puut mahdollistavat nopean tiedonhaun ja lisäävät suorituskykyä. Peräkkäin järjestetyssä taulukossa joudutaan pahimmillaan käymään koko taulukko läpi, eli sen etsintäaika on lineaarinen suhteessa taulukon kokoon. Binäärihakupuu on matalampi ja sen etsintäaika on logaritminen. Parhaan tehokkuuden saavuttamiseksi puu on tasapainoitettava, jotta se on mahdollisimman matala.

Tyypillisesti tietojenkäsittelytieteessä käytetään binääripuita, joissa solmulla voi olla enintään kaksi lapsisolmua. Näiden sovelluksia ovat binäärinen hakupuu tai tehokkaampi tasapainotettu punamusta puu.

Puu voidaan toteuttaa osoittimien avulla taulukon avulla.

Sovelluskohteita

Puiden käyttökohteita ovat hakurakenteiden lisäksi esimerkiksi:

Tiedostojärjestelmä muodostaa hakemistopuun, jossa on sisäisiä hakemistoja ja niissä tiedostoja.

Jäsentämisessä luodaan kielestä jäsennyspuu.

Verkkosivut kuvataan Document Object Modelin mukaan, jossa verkkosivu on itseasiassa puu, jossa on sisäkkäisiä olioita.

Tiedonpakkauksessa Huffmanin koodaus luo tiedosta optimaalisen Huffman-puun.

3D-grafiikassa käytetään mm. quadtree ja octree-algoritmeja. BSP-puu on eräs tapa tallentaa kulloinkin näkyvissä olevat pinnat.

Merkintäkielet

Puiden ja solmujen käyttö on yleistä web-kehityksessä. Ne muodostavat suuren osan verkkosivujen ja sovellusten rakenteesta. Ohjelmoinnissa XML:ää käytetään tietokoneiden ja ohjelmoijien tiedonvälitykseen. Tämän takia XML:ää käytetään yhteisten viestintäprotokollien luomiseen esimerkiksi ohjelmien väliseen viestintään ja se toimii pohjana nykyään käytettävien web-merkintäkielten, kuten XHTML:n kehityksessä.

Vaikka HTML ja CSS ovat ohjelmoijan näkökulmasta samankaltaisia, niitä käytetään eri tarkoituksiin. HTML:ää käytetään useimmiten ohjelmoinnissa verkkosivun tekstin kehitykseen ja CSS:ää verkkosivujen muotoiluun. XML, HTML ja XHTML tarjoavat kielen ja ilmaisun, mutta DOM toimii kääntäjänä. DOM toimii ohjelmointirajapintana, jota voi käyttää esimerkiksi verkkosivun rakenteen ja sisällön dynaamiseen muokkaamiseen. JavaScript toimii tärkeässä roolissa verkkosivukehityksessä. Sen ja DOM:in avulla voi muokata verkkosivun rakennetta koodilla. Tämä on tärkeä osa nykyajan verkkosivuja ja näiden toimivuus yhdessä mahdollistaa dynaamisen toiminnan ja interaktiivisuuden verkkosivuilla.

Käyttökohteita

• keot
• hakupuut
• merkkijonojen käsittely, esim. haku:
  • trie, myös alkuosapuu, prefiksipuu
  • loppuosapuu, myös suffiksipuu