"lineaarnimistu" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

 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. Tippe võiks olla vähemalt 256. 13.6 AVL-puu 13.6.1 Omadused ja kuidas töötab • Otsimiskahendpuu • Töö tema korrashoimiseks on suur ja algoritm keeruline