on välja eraldatud ja ülejäänud tipud moodustavad mittelõikuva alamhulga, millest igaüks on omakorda puu. Puu on sobiv hierarhiliste andmestruktuuride kirjelda- miseks (näiteks Dos kataloogid). Rakendustes on enimlevinud kahendpuu ehk Bi-puu, kuna järjestatud kahendpuu võimaldab kiiret otsingut, lisamist, eemaldamist. Kahendpuu (Binary tree) Kahendpuu on puu, mille igast tipust (sõlmest) lähtub kuni kaks alampuud. 49 8 52 4 19 52 55 21 Alampuu juurt nimetatakse puu juure alluvaks. Alluvateta tippu nimetatakse leheks. Tipp y on tipust x kaugusel k kui leidub tee x= t 0,t1,...tk=y, nii et ti+1 on ti alluv. Puu I- nda taseme tippude kaugus juurest on i.Puu tipu astmeks nimetame selle tipu alluvate arvu
Puuga seotud mõisted. Puude ülesmärkimine sulgavaldisena ja Dewey kümnendesitusena. Puu läbimise järjekorrad (pre-, post- ja inorder). Puu realiseerimine arvutis. Puu – Mittelineaarne andmestruktuur; üks või mitu tippu; teistest erinev tipp ehk juur; teised tipud jagunevad alampuudeks. Üldine puu – mittelineaarne andmestruktuur, mis koosneb tippudest & kaartest. Andmed paigutatakse tippudesse. Kahendpuu – igal tipul max. kaks alampuud; range vahe vasak- ja parempoolsel alampuul. Järjestatud puu – ühe tipu järglaste järjestus on oluline; räägitakse esimesest, teisest, kolmandast pojast. Järjestamata puu – tipu järglaste järjestus ei ole oluline. Mõisted – sõlme järk (kõigi alampuude arv); leht (alampuudeta sõlm); hargnevad sõlmed (ülejäänud sõlmed); tase (sõlmed jagunevad paiknemise järgi, juur on tase 0, juure järglased tase 1); puu kõrgus (mõõdetakse tasemete järgi);
Leida tsüklivaba graafi G = (A,R) tippude selline märgendus f: A N, et aRb => f(a) < f(b) ehk leida lineaarne järjestus hulgal A, mis ühtlasi sisaldaks järjestuse R. Puude esitamine raalis: · intsidentsusmaatriksina · viitstruktuurina · sulgavaldisena (ees-, kesk- ja lõppjärjekorras) avaldis sugudest, komadest ja puu märgenditest · Järjestatud puu T eesjärjekord: avaldis lrep(T), kus o kui T juur on a, mille vahetud alampuud on T 1 .. Tk, siis lrep(T) = a(lrep(T1), .. , lrep(Tk)) o kui a on terminaalne tipp, siis lrep(T) = a Juur jääb vasakule vasakrekursiivne sulgavaldis · Järjestatud puu T keskjärjekord: avaldis mrep(T), kus o kui T juur on a, mille vahetud alampuud on T 1 .. Tk, siis mrep(T) = mrep(T1), a (mrep(T2), .. , mrep(Tk)) o kui a on terminaalne tipp, siis mrep(T) = a Juur jääb keskele
8.4 Puu ülesmärkimine 8.4.1 Sulgavaldisena (a(b) (c(d) (e))) 8.4.2 Dewey kümnendesitusena 1 a; 1.1 b; 1.2 c; 1.2.1 d; 1.2.2 e 8.5 Kahendpuu • On tippude lõplik hulk, mis on tühi või koosneb juurest ja kahest mittelõikuvast alampuust, mida nim vasakuks ja paremaks alampuuks. • Kahendpuu igal sõlme on max kaks alampuud (2-järku puu) • Iga alampuu puhul on vahe, kas ta on vasakpoolne või parempoolne • Võrreldes tavalise puuga, siis kahendpuu puhul peetakse ka tühja alampuud puuks Algoritmid ja andmestruktuurid 2015 16 8.6 Puu läbimise järjekorrad (pre-, post- ja inorder) 8.6.1 Lõppjärjekord (Postorder e. Endorder) Vanema ja tema kahe järglase kohta kehtib järgmine läbimise järjestus:
mõne taksoni asukoht on vaadeldud puudel väga erinev. Esitab alampuu, mis on kõigil vaadeldud puudel. 46. Mida mõõdab puude topoloogiline kaugus? Kuidas leitakse kahe dihhotoomselt haruneva juurimata puu topoloogiline kaugus? (Näide!) Puude topoloogiline kaugus mõõdab kahe puu topoloogiliste erinevuste ulatust. Vaadatakse kõiki sisemisi servasid ja vaadatakse millise katkestamisel saadatakse alampuud, mis teineteisest erinevad. Puule juure leidmine 47. Mis on fülogeneesipuu juur ja kuidas see leitakse (juurimine välisrühma abil ja juure leidmine eeldades molekulaarse kella olemasolu)? Juur on uuritavate taksonite kõige viimane ühine eellane (MRCA). Välisrühma meetod – välisrühm võimaldab tuvastada tunnuse ürgse seisundi. On vaja teada, milline tunnuse alternatiivsetest seisunditest on primitiivne ja milline uus
.. puhul. Lemma: Olgu sõne x tuletuspuu kõrgus KV grammatikas k, siis |x| <= mk, kus m on selle grammatika produktsioonide paremate poolte maksimaalne pikkus. Induktsiooni baas: k=1 korral on sõne x tuletatud produktsiooni S → x abil. (kohe otse, puu kõrgus on 1) Seega |x| <= m = m1 = mk (kuna k=1 ja max m on x pikkus). Induktsiooni samm: Eeldame, et võrratus |x| <= mn kehtib kõigi süntaksipuude korral, mille kõrgus n on väiksem kui k. Tuletuspuus kõrgusega k on puu juurel max m alampuud, mille max kõrgus on k-1. Seega kehtib |x| <= mk−1m = mk . T: Iga KV keele jaoks leidub redutseeritud KV grammatika. Olgu sellise grammatika G mitteterminaalide arv n. Valime konstandiks p = mn, kus m on produktsioonide paremate poolte maksimaalne pikkus. Sõne |z| > p tuletuspuu kõrgus peab siis Lemma põhjal olema vähemalt n+1. Seega leidub tuletuspuus tee, millel mingi mitteterminaal A esineb vähemalt 2 korda: Seega uwy ∈ L ja uv2wx2y ∈ L
annaabi.ee 
