"korrashoimiseks" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

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 • AVL-puu saamiseks on peale iga sõlme lisamist või kustutamist vaja kontrollida tema tasakaalustatust ja vajaduse korral puu tasakaalu viia. • Igal sõlmel on tasakaalu faktor, mille abil isel iga tipu vasaku ja parema alampuu kõrguse vahet o - Sõlme vasak alampuu on 1 võrra kõrgem (-1) (kriitiline) o + sõlme parem alampuu on 1 võrra kõrgem (+1) (kriitiline)