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. f and g are functions. Leia vastavus tähistuste ja tähenduste vahel, f ja g on funktsioonid, mille asümptootilist käitumist võrreldakse. f~(g) f grows faster than g / f kasvab kiiremini kui g f~o(g) f grows slower than g / f kasvab aeglasemalt kui g
Kustutamine – algab otsimisest, kui vastav tipp on leitud, siis on 3 võimalust. 1) kui tipul pole lapsi, võib kustutada 2) kui tipul üks laps, siis pannakse see kustutatava tipu asemele 3) kui tipul mõlemad lapsed, siis otsitakse ta asemele talle suuruselt järgnev tipp x, mille alampuu on tühi, füüsiliselt eemaldatakse tipp x ning tipus x olnud andmed kirjutatakse kustutatava tipu asemele. Suuruselt järgmine tipp pesas peaks paikneva kustutatava tipu paremas alampuus vasakul. AVL-puu – optimaalses seisundis puu hoidmine. Vajab täiendavat mälu, garanteerib logaritmilise otsimisaja. Peale iga sõlme lisamist või kustutamist on vaja kontrollida tema tasakaalustatust ja vajaduse korral puu tasakaalustamiseks sõlmi ümber paigutada. Iga sõlmega seotakse tasakaalu faktor, mille abil iseloomustatakse iga tipu vasaku ja parema alampuu kõrgust vahet
Algoritmid ja andmestruktuurid 2015 31 13.2 Andmete (tipu) lisamine • Alustada puu juurest ja võrrelda iga tipu võtmeväärtust lisatava elemendi väärtusega • Kui uue tipu võti on väiksem, siis liigutakse vasakusse alampuusse • Kui uue tipu võti on suurem, siis liigutakse paremasse alampuusse • Nõnda toimitakse iga tipu juures • Kui alampuus edasi minna ei saa, sest see puu on tühi, ongi uuele elemendile koht leitud. • Keerukus: O (log n) 13.3 Otsimine • Alustades puu juurest ning liigutakse vastavalt otsitava võtme väärtusele vasakusse või paremasse alampuusse kuni võti leitakse või kuni jõutakse leheni. • Leidmise korral tagastakse tipu aadress (tsükkel katkestatakse), kui ei leita, sii Nil. • Min leidmisel liigutakse juurest seni vasakule kui saab. Viimases kättesaadavas tipus ongi
annaabi.ee 
