"otsimiskahendpuule" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

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) • Võtmega tipu otsimine, samuti vähima ja suurima elemendi leidmine sarnaselt tavalisele otsimiskahendpuule (keerukus O(log n)) • Must kõrgus – mustade tippude arv puu juurest leheni. Puu must kõrgus on iga lehe suhtes ühesugune 13.7.2 Kuidas töötab Reeglid: • Iga sõlm peab olema kas punane või must • Lehtede NIL-viidad (e tühjad alampuud) on mustad • Igal punasel sõlmel peab olema must vanem • Iga tee, mis läheb puu juurest mõnda lehte, sisaldab sama arvu musti sõlmi Algoritmid ja andmestruktuurid 2015