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.^[1]^[2]

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.^[3]

Č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".^[4]

Reference

^ Stout, Quentin F.; Warren, Bette L. (1986). „Tree rebalancing in optimal space and time” (PDF). CACM. 29 (9): 902—908. doi:10.1145/6592.6599.
^ Day, A. Colin (1976). „Balancing a Binary Tree”. Comput. J. 19 (4): 360—361. doi:10.1093/comjnl/19.4.360 .
^ Rolfe, Timothy J. (2002). „One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm”. SIGCSE Bulletin. ACM SIGCSE. 34 (4): 85—88. doi:10.1145/820127.820173. Архивирано из оригинала 13. 12. 2012. г. Приступљено 06. 02. 2017.
^ Drozdek, Adam (1996). Data Structures and Algorithms in C++. PWS Publishing Co. стр. 173–175. ISBN 0-534-94974-6.

[sw-1] Stout, Quentin F.; Warren, Bette L. (1986). „Tree rebalancing in optimal space and time” (PDF). CACM. 29 (9): 902—908. doi:10.1145/6592.6599.

[2] Day, A. Colin (1976). „Balancing a Binary Tree”. Comput. J. 19 (4): 360—361. doi:10.1093/comjnl/19.4.360 .

[rolfe-3] Rolfe, Timothy J. (2002). „One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm”. SIGCSE Bulletin. ACM SIGCSE. 34 (4): 85—88. doi:10.1145/820127.820173. Архивирано из оригинала 13. 12. 2012. г. Приступљено 06. 02. 2017.

[4] Drozdek, Adam (1996). Data Structures and Algorithms in C++. PWS Publishing Co. стр. 173–175. ISBN 0-534-94974-6.

[1]

[2]

[3]

[4]