"andmeteeki" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

o * Sõlme mõlema alampuu kõrguse on võrdsed (0) Algoritmid ja andmestruktuurid 2015 33 13.6.2 Milleks kasutatakse • Kasutakse siis, kui otsimine toimub tihedamini, kui lisamine või kustutamine. • Saab seal kasutada, kus on kõrge turvarisk ning paralleelse koodi tegemisel. • Kasutada kui mõtlemisestrateegiana • Kui teha uut andmeteeki, siis sinna implementeerida 13.7 Puna-must puu 13.7.1 Omadused • Otsimiskahendpuu • Ei ole nii hästi tasakaalus kui AVL-puu, kuid tema hoidmine on vähem töömahukas ja tulemuslikkus pole oluliselt AVL-puust halvem. • Iga puu tipp on värvitud kas punaseks või mustaks. • Tippude lisamisel või kustutamisel tuleb järgida teatud värvide skeemi – nii saab säilitada puu mõistliku seisus • n tipuga PM-puu ei ületa otsimise aeg 2*log(n+1)