AVL stablo

Izvor: Wikipedija
Skoči na: orijentacija, traži

AVL-stablo je struktura podataka koja se koristi u računarstvu. Radi se o balansiranom binarnom stablu pretrage, koje jamči da se operacije umetanja, traženja i brisanja elemenata iz stabla i u najgorem slučaju mogu sprovesti u broju koraka koji odgovara logaritmu broja elemenata u stablu, O(log n). Motiv za korištenje binarnih stabala upravo je brza pretraga stabla, ali kod uobičajenog, nebalansiranog binarnog stabla može doći 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 (G.M. Adelson-Velskii i E.M. Landis) koji su opisali ovu strukturu 1962. u radu Algoritam za organiziranje podataka (An algorithm for the organization of information).

Definicija AVL-stabla glasi:

AVL-stablo je binarno stablo pretrage kod kojeg apsolutna razlika visina lijevog i desnog podstabla svakog elementa nije veća od jedan.

Balansiranje[uredi VE | uredi]

Balansiranost AVL-stabla se održava tako što se nakon svakog umetanja ili brisanja provjerava da li je došlo do gubitka balansiranosti na nekom dijelu stabla. Ukoliko je došlo do debalansa, identificira se kritični čvor, odnosno korijen 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.