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,
dynamic programming algorithm / dünaamilise kavandamise algoritm Eight queens problem and knapsack problem are examples of Lippude paigutamine malelauale, samuti seljakotiülesanne on exhaustive search algorithm / ammendava otsingu algoritm Quicksort and merge sort are examples of Järjestamise kiirmeetod, samuti ühildamismeetod on 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
1) alusta esimesest elemendist 2) otsi sorteerimata osast vähim arv 3) vaheta leitud arv sorteeritud osale järgneva arvuga 4) vii järg edasi 5) korda tegevust, kuni massiiv on läbitud. Keerukus O(n2). Tugev külg – tulemusi võib juba sorteerimise käigus väljastada. Nõrk külg – sorteerimise kiirus ei sõltu massiivi varasemast sorteeritusest. Tööd tehakse alati samapalju. Sorteerimine kuhjaga – kahendkuhi (kahendpuu kujuline andmestruktuur, realiseeritakse massiivi abil). Kuhjas olevad elemendid teatud reegli abil järjestatud, vastavalt kuhja omadusele. Iga tipp on üks element kuhjas. Puu juur on kõige suurem element indeksiga 1. Keerukus O(n log n). Tugev külg – ei vaja lisamälu. Nõrk külg – sorteeritud massiiv hakkab tekkima massiivi lõpust. Meetodi kirjeldus: arvudemassiivist moodustatakse väärtuste ümberpaigutamise teel kuhi ning sorteeritakse vastava algoritmiga.
Prev A B A B C C F 8. samm Node A* B* C* D* E* F* G* H* Label 0 2 4 4 14 7 8 12 Prev A B A B C C F Lühim tee A-st H-sse: H > F > C >B > A 12 = 5 + 3 + 2 + 2 Algoritmid ja andmestruktuurid 2015 25 10. Kahendkuhi - mis teda iseloomustab, kuidas realiseeritakse, milliste ülesannete jaoks Selline kahendpuud, kus peaksid olemad täidetud järgmised tingimused: 1. Igas tipus olev väärtus ei tohi olla väiksem kui selle tipu järglastel 2. Lehtede sügavus ei tohi erineda rohkem kui 1 taseme võrra 3. Viimane tase täitub vasakult paremale • Andmestruktuur on tavaliselt realiseeritud massiivina ja puu juur on element indeksiga 1, edasi tulevad juure järglased 2 ja 3 jne
annaabi.ee 
