"puuviit" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

Tüüpilised reeglid i-nda elemendi jaoks on järgmised: 2.1. Vasak laps – 2*i 2.2. Parem laps – 2*i +1 2.3. Vanem – i/2 (täisarvuline jagamine) 8.7.2 Dünaamiliselt ahelana • Dün. realisatsioon on eelistatud, sest ei nõua esialgset suurt mälu eraldamist ja on ka loomulikum. • 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