Algoritmid ja andmestruktuurid konspekt - puud
Sellepärast on ka sellised mõisted nagu keskmine palk täiesti mõttetud, kuna see ei näita midagi,
kuna kõrvalekaldumised on väga suured.
Puu modifitseerimisel kipub puu tasakaal kaduma, puu välja venima. 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
annaabi.ee 
