Puu (andmestruktuur)

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

Puu koosneb tippudest (nodes) ja kaartest, mis on teatud ka servadena (edges), mis ühendavad tippe. Tipud, mis on ühendatud kaarega üleval asuva tipu külge on alamtipud või teatud ka kui lapsed (childs) ja üleval asuv tipp on sel juhul vanem (parent). Kõige ülemine tipp on juurtipp (root). Tippu, millel ei ole lapsi, nimetatakse leheks (leaf). Liikudes tipust järjest üles jõuame juurtippu. Esivanemad on kõik tipud, mis jäävad juurtipu ja vaadeldava juure vahele. 

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.http://opiobjektid.tptlive.ee/B3/ahelloendid_ja_puud.html

 Kahendpuu 
Kahendpuu on selline andmestruktuur, kus igal tipul võib olla mitte ühtegi, üks või kaks alamtippu ja alamtippude 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, mille 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 andmestruktuurina väga olulise graafiga, sest toespuu abil 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.

Viited

Kategooria:Andmestruktuurid