Puu (andmestruktuur)

Kahendpuu näidis

Puu on infotehnoloogias hierarhiline andmestruktuur, kus andmed on paigutatud puukujuliselt.

Puu koosneb tippudest (nodes) ja kaartest (edges), mis ühendavad tippe (viited). Tipud, mis on ühendatud kaarega üleval asuva tipu külge on lapsed (childs) ja üleval asuv tipp on sel juhul vanem (parent). Kõige ülemine tipp on juur (root). Tippu, millel ei ole lapsi, nimetatakse leheks (leaf). Liikudes tipust vanemasse, sealt vanemasse jne jõuame juurde. Esivanemad on kõik tipud, mis jäävad tipu ja vaadeldava juures vahepeale.

Puu kõrgus (tree height) on pikim tee lehest juureni. Järjestatud puu korral on defineeritud juur ja otse juurega ühendatud tipud on esimese taseme tipud (first level nodes, juure lapsed), esimese taseme tippudega otse ühendatud tipud on teise taseme tipud (esimese taseme tippude lapsed) jne ning laste järjekord vasakut paremale on oluline. Mets on vähemalt kahest puust koosnev puude kogum.

Kahendpuu

Kahendpuu on selline puu, kus iga vanema võib olla mitte ühtegi, üks või kaks last ja laste järjekord on oluline. Kahend-otsingupuu (binary search tree) on kahendpuu, mis on järjestatud. Tipust vasakul on alati väiksem suurus ja tipust paremal suurem suurus.

Sellisest puust otsides võrreldakse otsitavat väärtust juurega, kui otsitav väärtus võrdub juure väärtusega, siis väärtus eksisteerib, kui aga juure väärtus ei võrdu otsitavaga, siis võrreldakse väärtust edasi, vastavalt kas vasaku või parema tippude hulgast kuni jõutakse leheni. Kui otsitav väärtus on võrdne mõne tipu väärtusega, siis on otsitav element olemas, kui aga ei leidu võrdset väärtust, siis otsitavat elementi ei ole. Selline otsimise viis on kordi kiirem kui oleks näiteks ahelloendi või massiivi läbivaatamine.

Puud graafiteoorias

Graafi nimetatakse puuks, kui ta on sidus ja ei sisalda tsükleid. Mets on graaf, mile kõik komponendid on puud. Puu rippuvad tipud on lehed ja ülejäänud on sisetipud.

Sidusa graafi toespuuks nimetatakse sellist alamgraafi, mis sisaldab kõiki tippe ja on puu. Tegu on andmestrutuurina väga olulise graafiga, sest toesuspuu albil saame rakendada mitmeid algoritme nagu Primi algoritm ja Kruskali algoritm. Nende abil saab leida lühimat teed läbides kõik antud punktid teel.

Kaalutud puu on puu, mille igale servale on antud kaal, puude kaalustamine on kasulik, kuna see aitab juba eelpool mainitud kahte algoritmi rakendada, kuid ka näiteks Dijkstra algoritmi, mis aitab leida lihtsalt lühima tee ühest graafi tipust teise.