"otsimispuud" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

• Puu iga sõlm sisaldab lisaks infole kahte viita: LLINK ja RLINK • Puuga on seotud ka nn puuviit ROOT • Kui puu on tühi: T = NULL, vastasel juhul on ROOT väärtuseks on puu juure aadress • Kui mingi sõlme üks alampuudest on tühi, siis kirjutakse vastavasse viidaväljasse tühja viida tähis NULL/nil 8.8 Puude kasutamine Kasutatakse arvuti mälus andmestruktuurina: • Avaldised jt keele osad süntaksipuuna. • Erinevad otsimispuud otsimise kiirendamiseks (kahendotsimispuu) • Kahenkuhi kiireks elementid paigutamiseks ja kättesaamiseks • Ka otsustamispuud, koodipuud jne 9. Graaf. Graafiga seotud mõisted. Suunatud ja suunamata graaf. Atsükliline graaf. Kaalutud graaf. Graafi ülesjoonistamine ja realiseerimine arvutis. Graafi algoritmid: topoloogiline sorteerimine, sügavuti otsimine, laiuti otsimine, lühim tee kaalutud graafis e Dijkstra algoritm): algoritmi kirjeldus koos väikese näitega