"tasakaalutegurid" - 1 õppematerjal

Algoritmid ja andmestruktuurid konspekt - puud

Eriti eemaldamisega. Vt üht eelmist näidet. Kuidasmoodi saavutada seda, et puu oleks rohkem tasakaalus? Sellisel juhul on võimalik võrduste arv ka ilmselt väiksem ja algoritmid muutuvad kiiremaks. AVL puu ­ peaaegu tasakaalus puu. Igale tipule leitakse nn tasakaalutegur ­ st mõõdetakse ta parempoolse haru kõrgus ning vasakpoolse haru kõrgus ning leitakse nende vahe. Võib olla 0, +1(parempoolne haru 1 võrra kõrgem kui vasak) või -1 AVL puu puhul. Näitel rohelisega kirjas tasakaalutegurid. AVL puud saab teha alati! Hakkame puud ehitama, igal sammul arvutame välja kõikide tippude tasakaalutegurid. Seni, kuni need on on 0,-1 või +1, ei tee me midagi. Kui mõni läheb lubatud piiridest välja, siis hakkame midagi tegema, et tasakaalutegurid uuesti normi viia. Meetod, mida kasut. - puu pööramine ehk rotatsioon. 4 olukorda, kus puu ehitamisel enam pole AVL puu. 2 lihtsamad, 2 keerulised. Lihtsad: AVL puud(2) ­ iga pilt kujutab üht fragmenti. Harude kõrgused on ,,h".