"ostimiskahendpuust" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

13.4 Kustutamine Kustutamine algab otsimisest 1. Lapsed puuduvad, võime tipu lihsalt ära kustutada 2. Kui tipul üks laps, siis see paigutakse kustutava tipu asemele Algoritmid ja andmestruktuurid 2015 32  3. Kui mõlemad lapsed on olemas 1) 2) 3) 4) 13.5 Keerukusklassid • Üldiselt on ostimiskahendpuust otsimine logarimilise keerukusega tegevus (puu tasemed max täidetud). • Halvim variant: kui võtmed on järjestatud, siis on otsimise keerukus lineaarne, sest saadakse sisuliselt lineaarnimistu. • Tasakaalustatud puu – iga alampuu jaoks vasaku ja parema alampuu kõrguste vahe pole suuurem kui üks • Tasakaalustatud kahendpuu tagab log aja nii võtme järgi otsimiseks, elemendi lisamiseks kui ka elemendi eemaldamiseks