tud. Näide: kaal on sihtpunktide vaheline teepikkus. Kaalutud graafis võib kaal sõltuda suunast. Lühim tee: tee, mille kaarte kogukaal on vähim. Puu (Tree) Puu koosneb lõplikust tippude (sõlmede) hulgast, mis on tühi või mille üks tipp juur 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.
Sobivad seega eelistusjärjekorra realiseerimiseks. 1 Kahendkuhjad 5 Kahendkuhjad 1 Kahendkuhjad 6 Invariant Kahendkuhja (ingl binary heap) puhul nõutakse kuhjatingimust ja et tegu oleks kompaktse kahendpuuga. 1 Kahendkuhjad 7 Kuhjatingimuse rekurrentne määratlus Kahendpuu rahuldab kuhjatingimust, kui kas ta on tühi või juure kirje võti on maksimaalne üle kogu puu (pöördkuhja puhul minimaalne), ja mõlemad harud rahuldavad kuhjatingimust. 1 Kahendkuhjad 8 Ülekanduvus alampuudele Kahendkuhja iga alampuu on kahendkuhi. 1 Kahendkuhjad 9 Esitus Eeldame, et
#include
#include
2 võimalust – massiiv (kaks indeksit – algus & lõpp; algusesse lisatakse,
lõpust eemaldatakse; kui lõpp
jõudnud 7.4.2 Dünaamiline ehk kasutades ahelat • Kasulik ja vajalik, et viitasid oleks kaks, mis viitaks ahela esimesele ja viimasele sõlmele. Nõnda on lisamine kiira ja mugav. • Põhjus on järjekorra eripäras, sest ligi on vaja pääseda nii järjekoora algusele kui ka lõpule. • Järjekorda on kasulikum hoida nö tagurpidi, sest nii saab palju mugavamalt elementi eemaldada. 8. Puu. Üldine puu. Kahendpuu. Järjestatud (orienteeritud) ja järjestamata (orienteerimata) puu. Puuga seotud erinevad mõisted. Puu ülesmärkimine sulgavaldisena ja Dewey kümnendesitusena. Puu läbimise järjekorrad (pre-, post- ja inorder). Puu realiseerimine arvutis. 8.1 Puu. Üldine puu • Graaf on mittelineaarne struktuur, mille abil saab modelleerida objektide hulgas paari-kaupa esinevaid suhteid ja seoseid. • Puu on graafi erivorm.
Viit vektorile ning see viitab omakorda tütardele. Viidad tütardele on ühes vektoris, kui üks tütar tuleb juurde, siis tuleb seda vektorit pikendada. Ei ole kõige parem lahendus. Parem lahendus. Teha tipp selliselt, et seal on viit kirjele. Tütarde puhul on viit ainult kõige vasakpoolsemale tütrele ning temast vahetult paremale asuvale õele. Sellisel juhul on viitade arv tipus täpselt kolm ja see arv pole muutuv. Kui joonistame need viidad veidi teisiti, siis saame kahendpuu. Seega oleme teisendanud paljuharulise puu kahendpuuks. Selle vahega, et viidad on veidi erinevad. Äkki paneks viidad hoopis tütrelt emale, mitte vastupidi? Palju vähem viitasid tuleks ju. A-l ei ole ematippu, seetõttu on indeks 0. Näites vektor indeksitega. Selline lahendus töötab ainult siis, kui tegemist on järjestamata puuga, sets siit enam ei saa välja lugeda, mis järjekorras õed on. Kui efektiivsed puud kui struktuurid on
Merkle autentimispuud Lineaarse linkimissüsteemi puuduste vähendamiseks esitati 1992 aastal idee jagada ajatempliteenuse osutaja tegevus ajaliselt tsükliteks, mille lõpus väljastatakse nn koond-ajatempel. Mingis tsüklis välja antud ajatempli linkimisteave sõltub samas tsüklis eelnevalt väljastatud ajatemplitest ning eelneva tsükli koondajatemplist. Mingi tsükli jooksul väljastatud dokumendid paigutatakse mõtteliselt kahendpuu harudesse. Kahendpuu igast tipust T väljub ülimalt kaks suunatud kaart: vasak ja parem kaar. Puu tippudele arvutatakse märgendid nn Merkle´i autentimispuu skeemi järgi. Koond-ajatemplite märkimisväärseim puudus on võimaus võrrelda ajaliselt ühe tsükli jooksul antud ajatempleid. Selle vähendamiseks tuleb vähendada tsükli ajalist kestust, mis toob kaasa ka tsükli jooksul välja antavate ajatemplite arvu vähenemise ja seega ka selle meetodi efektiivsuse vähenemise. Binaarsed linkimisskeemid
Merkle autentimispuud Lineaarse linkimissüsteemi puuduste vähendamiseks esitati 1992 aastal idee jagada ajatempliteenuse osutaja tegevus ajaliselt tsükliteks, mille lõpus väljastatakse nn koond-ajatempel. Mingis tsüklis välja antud ajatempli linkimisteave sõltub samas tsüklis eelnevalt väljastatud ajatemplitest ning eelneva tsükli koondajatemplist. Mingi tsükli jooksul väljastatud dokumendid paigutatakse mõtteliselt kahendpuu harudesse. Kahendpuu igast tipust T väljub ülimalt kaks suunatud kaart: vasak ja parem kaar. Puu tippudele arvutatakse märgendid nn Merkle´i autentimispuu skeemi järgi. Koond-ajatemplite märkimisväärseim puudus on võimaus võrrelda ajaliselt ühe tsükli jooksul antud ajatempleid. Selle vähendamiseks tuleb vähendada tsükli ajalist kestust, mis toob kaasa ka tsükli jooksul välja antavate ajatemplite arvu vähenemise ja seega ka selle meetodi efektiivsuse vähenemise. Binaarsed linkimisskeemid
from vertex A. Leia allpool kolm järjestust, mis vastavad selle graafi tippude laiuti läbimise strateegiale alates tipust A. ABDECF ADBCEF ABDCEF Find the post-order sequence of nodes of the following tree and write it as a string without spaces. Leia selle puu tippude lõppjärjestus ning esita see ilma tühikuteta sõnena. Vastus: GHDEIFBJCA Find the in-order sequence of nodes of the following tree and write it as a string without spaces. Leia selle kahendpuu tippude keskjärjestus ning esita see ilma tühikuteta sõnena. Vastus: DBEAFC Find the reverse polish notation (RPN) of the following expression and write it as a string where elements are separated by one space exactly. Leia selle avaldise pööratud poola kuju ning esita see sõnena, milles avaldise elemendid on eraldatud täpselt ühe tühikuga: 4 /(5-3) + 2*6 Vastus: 4 5 3 - / 2 6 * + Progemine: Leia suurima laste arvuga tipu laste arv Answer v = Answer
goto otsi; } sisestatud->p=failist; goto tsyk; } ots: remove(argv[1]);//kirjutab puu faili mf=fopen(argv[1],"wb"); kirjuta(juur); fflush(mf); fclose(mf); p: printf("nkasvavas reas:n");//prindib välja järjestatult labiay(juur); printf("nkahanevas reas:n"); labiya(juur); lopp: return(1); } Praktikum 7 ( 19.10.2009) Ülesanne 1 · Programmeerida sisse" kahendpuu. Kirjutada (järjekorras) funktsioonid: · Puu trükk eesjärjekorras (preorder): trüki märgend (või võti). · Puu trükk eesjärjekorras (preorder): trüki: tipu aadress, nimi, viidad alluvatele. · Puu kirjutamine kettale (küsitud nimega). · Puu lugemine kettalt (küsitud nimega) ja trükk. · Puu läbimine (ja trükk) ees-, kesk- ja lõppjärjekorras. Puu ise on selline: A B c
15. KV-grammatikate normaalkujud. Chomsky normaalkuju: KV-grammatika G = (,N,P,S) öeldakse olevat Chomsky normaalkujul, kui see sisldab produktsioone järgnevatel kujudel: A BC (kõik on mitteterminaalid) A b (b on terminaal, a mitteterminaal) S (S on lähtesümbol, mis ei esine ühegi produktsiooni paremas pooles) Iga KV grammatika evib Chomsky normaalkuju. Chomsky normaalkuju korral on sõna tuletuspuuks kahendpuu. Greibachi normaalkuju: -vaba KV grammatika on Graibachi normaakujul, kui kõik produktsioonid (va S ) on kujul A a, kus a on terminaal ja on mitteterminaal Mitteterminaali nimetatakse rekursiivseks, kui A =>+ A. Kui = , siis vasakrekursiivne. Iga KV keel on genereeritav mitte-vasakrekursiivse grammatikaga. Teisendamine Greibachi normaalkujule: · Vasakrekursiooni elimineerimine (redutseeritud grammatika sisendiks) · Grammatika viimine greibachi normaalkujule Näide:
annaabi.ee 
