Puu (tietorakenne)

Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan.

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.