SHPORA.net :: PDA

[ Back ]

AVL (Adelson-Velski, Landis) puu on kahendotsimise puu, mille korral:



1. Vasak ja parem alampuu on AVL-puud ning nende kõrgused erinevad ülimalt ühe võrra.

2. Tühi puu on AVL-puu.



Otsimine puud ei muuda ja on korraldatud samuti, nagu kahendotsimise puus.



Lisamine ja eemaldamine tuleb defineerida nii, et AVL-puu omadus säiliks, s.t. alampuude kõrguste vahe ei tohi olla suurem kui 1.



Pööre.Alampuude I ja III kõrgused enne pööret erinevad 2 võrra, omadus a≤b säilib.





Seda joonist võiks vaadata ka peegelpildis.





Topeltpööre. Alampuude I ja III kõrgused enne pööret erinevad 2 võrra, omadus a≤c≤b säilib.



Ka seda joonist võib vaadata peegelpildis.