Ahelloendid ja puud

Kaasajal kasutatakse tihti andmete hoidmiseks loendeid (list). Kui iga listi liige viitab järgmisele, siis on tegemist ahelloendiga, ahelloendi lõppu märgib tühiliige (null). Ahelloend, kus iga liige viitab järgmisele nimetatakse ühesuunaliseks loendiks, ahelloend, kus iga liige viitab eelmisele ja järgmisele nimetatakse kahesuunaliseks loendiks. Ahelloend, kus puudub esimene ja viimane liige ning iga liige viitab järgmisele nimetatakse ringloendiks. Ahelloendi pikkus on loendi liikmete arv. Loendi esimene liige on pea (head) ja ühejäänud liikmed saba (tail).

Pinu (stack) on ahelloend, kus viimasena lisatud liige loetakse välja esimesena ( LIFO – Last In First Out).

Järjekord (queue) on ahelloend, kus esimesena lisatud liige loetakse välja esimesena ( FIFO – First In First Out)

Lisalugemist: wikipedia.org

Puu on andmestruktuur, kus andmed on paigutatud puukujuliselt, koosneb tippudest (nodes) ja kaartest (edges), mis ühendab tippe (viited). Tipud, mis on ühendatud kaarega üleval asuva tipu külge on lapsed (childs) ja üleval asuv tipp on sellisel juhul vanem (parent). Kõige ülemine tipp on juur (root). Tippu, millel ei ole lapsi, nimetatakse leheks (leaf).



img25_8

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.

Lisalugemist: wikipedia.org

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.

img28_8

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.

Lisalugemist: wikipeida.org

B-puu (B tree )on otsingupuu, milles iga tipu tütarde arv asub vahemikus (t-1) kuni (2t-1) , kus t on suvaline konstant

Lisalugemist: wikipedia.org

B*-puu  on B-puu, kus tippude täituvus hoitakse 2/3 juures, täites kaks tütartippu võtmete ümberjaotamise teel ja tükeldades nad seejärel kolmeks tipuks.