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. Tipp mis pole leht on vahetipp. Kahendpuu on täielik kui kõik lehed asuvad samal tasemel ning kõigi vahetippude aste on 2 (ehk üksikud lehed saavad olla ainult madalaimal tasemel).
Programmi aken Analoogiliselt saab arvuti failsüsteemile ligipääsu ka programmi Windows Explorer abil. Selle programmi aknas on vasakpoolsel alal esitatud kogu arvuti failisüsteem kataloogipuuna. Parempoolsel alal näidatakse puus märgistatud (aktiivse) ketta või kataloogi sisu. Kaustapuus on sama taseme asjad ühendatud punktiirjoonega. Punktiirjoonel asuv `+'-märk näitab, et vastavas kataloogis (kettal) asub alamkatalooge. Hiireklõps sellel märgil lülitab sisse kausta alampuu näitamise ning märk muutub `-`-märgi kujuliseks. Hiireklõps `-`-märgil lülitab alampuu näitamise jälle välja. Windows Exploreri kaustapuu juureks on arvuti töölaud (Desktop), mis jaotub: · minu arvuti (My Computer); · prügikast (Recycle Bin); · kohtvõrgu arvutid (Network Neighborhood) kui arvuti on ühendatud võrku, siis siit saate infot teiste võrgus olevate arvutite kohta.
täielik puu (kõigil tasemetel maksimaalne võimalik arv sõlmi & kõik lehed samal tasemel); mets (järjestatud hulk, mis koosneb 0 või mitmest mittelõikuvast puust, kui eemaldada puu juur, saame alampuudest metsa); n-järku puu (puu, mille igal sõlmel pole rohkem kui n järglast). Sulgavaldis – (a (b) (c (d) (e) ) ) Dewey 10ndesitus – 1a; 1.1b; 1.2c; 1.2.1d; 1.2.2e Preorder – juur väljastada (töödelda), läbida vasak alampuu, läbida parem alampuu. Postorder – läbida vasak alampuu, läbida parem alampuu, väljastada (töödelda) juur. Inorder – läbida vasak alampuu, väljastada (töödelda) juur, läbida parem alampuu. Puu realiseerimine arvutis – Eelistatud on dünaamiline realisatsioon, kuna see ei nõua esialgu suur mälumahtu & on loomulikum. Sõlmes on kaks viidavälja (rlink, llink) ja võtmeväli (key). Puu koosneb ühest viidast juurele (root). Tühja viida tähis (none). 9. Graaf
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: vasak järglane, parem järglane, vanem 1
divide and conquer algorithm / jaga ja valitse algoritm Which data structure is on the picture Millise andmestruktuuriga on tegemist binary heap / kahendkuhi Which order of nodes of a binary tree is generated by the following algorithm: 1) process the root node; 2) apply this algorithm to the left subtree; 3) apply this algorithm to the right subtree. Milline tippude järjestus saadakse läbides kahendpuud algoritmiga: 1) töödelda juur; 2) läbida vasak alampuu; 3) läbida parem alampuu. pre-order / eesjärjestus Which property is described as: all keys in left subtree are not greater than the key of the root node and all keys in right subtree are not less than the key of the root node. Millist omadust kirjeldab lause: kõik võtmed vasakus alampuus ei ole suuremad juure võtmest ning kõik võtmed paremas alampuus ei ole väiksemad juure võtmest. property of keys in binary search tree / kahendotsimise puu võtmete omadus Match notations with asymptotic properties
leidub tuletuspuu A[]. Näidata, et see on tarvilik ja piisav ja tingimus sõna aktsepteerimiseks: Tarvilik: Kui string on tuletatav 0 sammuga, siis saame kostrueerida ühest tipust koosneva puu A[A] mis on süntaksipuu, kuna vastav produktsioon on elementaarpuuks. Iga produktsioon on esitatav elementaarpuuna ja iga elementaarpuu on kokku kleebvitav suuremaks puuks. Piisav: Olgu antud ühe tipuga süntaksipuu saame 0-sammulise tuletuse. Iga alampuu esitab terviklikku sõnajupi sünteesi .. igale elementaarpuule on vastavusse seatav produktsioon ja muud polegi vaja. Sõna tuletuspuu: Täielikku süntaksipuud (mittelaiendatavat süntaksipuud mille juureks on lähtesümobl ja lehtedeks ainult terminaalid) ning mille krooniks on string x nimetatakse sõna x tuletuspuuks. Sõna kuulub keelde, kui eksisteerib tuletuspuu, mille krooniks see sõna on. Tuletuspuu on reeglina ka lause semantika näitaja (mitme tuletuspuu korral
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 iga tipu puhul on ajaga O(1) kättesaadav tema ülemus, kui see leidub (lisaks muidugi alluvatele). ajaga O(1) on teostatav viimase taseme viimase tipu likvideeri- mine ja uue tipu lisamine sinna. Kui kahendkuhja esitamiseks kasutada kompaktse kahendpuu esitust massiivina ja kasutada lisaks üht välja kirjete reaalse arvu hoidmiseks,
Võimalikke puid võib vaadelda maastikuna, kus parimad puud paiknevad küngaste tippudes ja halvimad asuvad orgudes. Heuristiline otsing alustab juhusliku puuga, mis võib asetseda orus. Algsel puul paigutatakse oksi ümber, et leida parim puud, mis asub kõige kõrgema künka tipus. 39. Milliseid puu ümberkorraldamise strateegiaid kasutatakse heuristilise otsingu korral? Kirjeldage neid (lähimate naabrite vahetus – nearest neighbor interchange, alampuu pügamine ja taasühendamine – subtree pruning and regrafting, puu kaheks jagamine ja taasühendamine – tree subsection and reconnection, star decomposition). Kõigepealt konstrueeritakse esialgne puu (star decomposition). Tippude järk-järgulise lisamisega liigutakse parima puu suunas. esialgse puu paremaks muutmine: Lähimate naabrite vahetus – vaadeldakse kõiki võimalikke vahetusi lähimas topoloogilises naabruses ja valitakse parim.
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. Analoogiliselt uvjwxjy ∈ L iga j >= 0 korral. Kui valida vwx alampuu juurest kaugeimate korduvate mitteterminaalide järgi, saab alampuu kõrgus olla maksimaalselt n−1, seega |vwx| <= mn−1 < p. 15 Kontekstist sõltuvad keeled ja Turingi masina keeled. Keel L = {anbncn| n > 0} pole kontekstivaba. T: Lemma järgi jagades uvjwxjy ei kuulu keelde L. Kontekstist sõltuv (KS) keel on selline sõnede hulk, mida genereerib kontekstist sõltuv grammatika. KS keeltel on erinevad produktsioonid cB →… ja bB →… sest muutumine sõltub, kas B ees on b või c
DNS serverid (TLD). Need jagunevad veel omaette DNS-ideks (Authorative). Igal teenusepakkujal nt amazon, yahoo on oma nimeserver. Pm kui sa tahad näiteks amazon.com IP aadressi saada, siis klient kõigepealt küsib root serverilt com DNS serveri asukohta, kontakteerub TLD serveriga mis annab authorative serveri IP aadressi ja lõpuks saab amazon.com serveri käest küsida domeeni IPd. Domeen ehk see veebisait ise on DNSi mingi alampuu (#graafi teooria) NS’ide hierarhia - Root server jaguneb nt arpa ja edu serveriks. Edu server jaguneb blabla.edu, puglife.edu jne Com - commercial organisations Edu - Educational institutions Org - nonprofit organisations Lisaks on veel domeenid riikide järgi, ehk kas lõppu tuleb .jp, .ee, .fi jne. Üle maailma on mitu suuremat DNSi, kui meie piirkonna oma ei leia mingit päringut, siis ta küsib endast kõrgemal asuva NSi käest ja tagastab sealt saadud vastuse.
annaabi.ee 
