Dej-Stout-Varen algoritam

Из Википедије, слободне енциклопедије

Dej-Stout-Varen (DSV) algoritam, je metoda za efikasno balansiranje binarne pretrage stabla - tj., smanjivanje njihove visine na O(logn) čvorova, gde je n ukupan broj čvorova. Za razliku od samobalansirajućeg binarnog stabla, ovo ne radi postepeno posle svake operacije, već periodično, tako da cena moze biti amortizovana preko više operacija. Algoritam je dizajnirao Kventin F. Stout i Bete Varen 1986 u radu "Tree Rebalancing in Optimal Time and Space", baziran na radu Kolina Dai iz 1976.

Algoritam zahteva linearno vreme (O(n)) i u mestu je. Originalni algoritam se generiše kao kompaktno stablo: svi nivoi stabla su potpuno puni osim možda poslednjih (najnižih). Stout/Varen modifikacija generiše potpuno binarno stablo, naime ono u kome su najniže grane popunjene s leva na desno. Ovo je korisna transformacija za izvođenje ako se zna da nece biti vise unosa u stablo.

Članak koji je napisao Timoti J. Rolfe 2002 je skoro vratio pažnju na DSV algoritam posle dugo vremena; imenovanje je iz dela naslova "6.7.1: DSV Algoritam" u delu Adama Drozdeka "Data Strukture i Algoritmi u C++". Rolfe citira dve glavne prednosti: "u okolnostima koje generisu celo binarno stablo na početku obrade, praćeno pronalaženjem pristupa za ostatak obrade" i "pedagogški u procesu data strukture gde jedan napreduje iz binarne pretrage stabla u samopodešavajuće stablo, pošto daje prvo izlaganje za rotacije unutar binarne pretrage stabla"