AVL-stablo
AVL-stablo je struktura podataka koja se koristi u računarstvu. Radi se o balansiranom binarnom stablu pretrage, koje garantuje da operacije umetanja, traženja i brisanja elemenata iz stabla i u najgorem slučaju mogu da se sprovedu u broju koraka koji odgovara logaritmu broja elemenata u stablu, O(log n). Motiv za korišćenje binarnih stabala upravo jeste brza pretraga stabla, ali kod uobičajenog, nebalansiranog binarnog stabla može da dođe do debalansa (neka grana stabla se značajnije izduži), i onda pretraga koja ide kroz tu granu nema logaritamsku, već linearnu složenost.
AVL-stablo je dobilo ime po izumiteljima, Adelson-Velskom i Lendisu, koji su opisali ovu strukturu 1962. u radu Algoritam za organizovanje podataka.
Definicija
urediAVL-stablo je binarno stablo pretrage kod koga apsolutna razlika visina levog i desnog podstabla svakog elementa nije veća od jedan.[1]
Balansiranje
urediBalansiranost AVL-stabla se održava tako što se nakon svakog umetanja ili brisanja proverava da li je došlo do gubitka balansiranosti na nekom delu stabla. Ukoliko je došlo do debalansa, identifikuje se kritični čvor, to jest koren najmanjeg podstabla koje ne zadovoljava definiciju AVL-stabla. Ovo podstablo se zatim balansira vršenjem odgovarajućih rotacija elemenata, tako da se povrati balansiranost podstabla.
