Stablo žrtvenog jarca

U računarstvu skapegoat tree (ili žrtveni jarac stablo) je binarno stablo pretrage otkriveno od strane Arnea Andersona^[1] i ponovo od strane Igala Galperina i Ronalda L. Rivesta.^[2]. Složenostje u najgorem slucaju O(log n) za pretraživanje i amortizovano vreme umetanja i brisanja od samo O(log n).

Za razliku od većine samobalansirajućih binarnih stabala koji obezbediti najgore vreme od O(log n) za pronalaženje, ovaj tip nema dodatnu memoriju za pre-cvorove, kao kod drugih stabla za pretrazivanje. U čvou se cuva samo kluč i dva pokazivača, na sinove. Čime se ostvaruje ušteda memorijskog prostora do čak 1/3. Ova struktura čini stablo žrtvenog jarca lakšim za implemenetaciju.

Teorija уреди

Binarno stablo pretrage se kaže da je težinski uravnotežen ako polovina čvorova su na levoj strani korena , a polovina na desnoj. α-težina-izbalansiran se stoga definiše kao ispunjavanje sledećih uslova:

size(left) <= α*size(node) size(right) <= α*size(node) -- velicina (levo) <= α*velicina (cvora) velicina (desno) <= α*velicina (cvora)

Gde se veličina mose defenisati rekurzivno kao:

function size(node)

if node = nil
 return 0
else
 return size(node->left) + size(node->right) + 1

end

Gde bi α jednako opsivalo da je povezani list balansiran, gde bi 0,5 odgovoralo skoro popunjenim binarnim stablima. Za balansirano stablo pretrage koje je α-težinski-balansirano mora da bude i α-visinski balansirano.

height(tree) <= log1/α(NodeCount)

Žrtveni jarac nisu garanti da održavaju α-težinski-balansiranje ali su uvek otprilike α-visinski balansirana.

height(scapegoat tree) <= log1/α(NodeCount) + 1

Ovo čine žrtveni jarac stablo sličnim crveno-crnim stablima u tome da su oboje ograničeni s visinom. Oni se u najvišoj meri razlikuju u implementaciji odlućivanja gde ce izvrsiti rotacia (ili rebalasiranje u slucaju žrvenog jarca). Gde crveno-crna stabla dodaju ekstra informaciju u obliku 'boje' da defenise lokacija, žrveni jarac nalazi žrvenog jarca gde nije α-težinski-balansiran da izvrsi rebalansirajuce operacije. Ovo je blisko sa AVL stablima, u tome da aktuelna rotacija zavisi od 'balansa' čvorova, ali determinacija balansa se drastično razlikuje.Pošto AVL stabla provera stanje vrednosti na svakom ubacivanju / brisanju, tipično je podatak čuvan u svakom čvoru; žrtveni-jarac-stabla su u stanju da ga izračunaju samo po potrebi , što je samo kada treba žrtveni jarac da se pronađe . Za razliku od večinje samo balansirajucih stabla,žrtveni jarac stabla su u potpunosti fleksibilni kod njihovog balansiranja.Oni podržavaju bilo kakvu α taj što su 0,5 < α < 1. α visoke vrednosti ima kao rezultat manje balansiranja,čineći ubacivanje brže nego pretrrazivanje i brisanja koji budu sporiji, i obrnoto za α koje uzima malu vrednost. U praktičnoj primeni α moze da se izabere prema tome kakve su frekvencije odgovarajućih operacija.

Operacije уреди

Ubacivanje уреди

Ubacivanje se realizuje sa istim osnovnim idejama kao neuravnotežene binarnom stablu pretrage , međutim uz nekoliko značajnih promena. Kada pronadje željenju tačku umetanja ,dubina novog čvora mora biti zabeležen. Ovo se realizuje putem jednostavnog brojača koji se uvećava tokom svake iteracije dok se ne pronadje,efikasno broji grane između korena i čvora koji se ubacije. Ako ovaj čvor krši α-visina-bilansnu svojstvo (definisan gore), potrebna je rebalans. Za rebalans celo pod stablo ispod cvora žrtvenog jarca ulazi u balansiranje. Žrtveni jarac je definisana kao predak od ubačenog čvora koji nije α-težina-uravnotežen. Uvek ce biti bar jedan takav predak. Rebalans bilo kojih od njih će obnoviti α-visina-uravnoteženo svojstvo.

Jedan način pronalažanje žrtvenog jarca, je da se penjemo od ubačenog čvora natrag do korena stabla, i obeležeti prvi čvor koji nije α-težina-uravnotežen.

Penjane natrag do korena zahteva O(log n) memorijski prostor, obisno alociran na steku ili roditeljske pokazivače. Ovo se zapravo može izbeći ukazujući svakom detetu na svom roditelju kako idete dole, a popraviti u povratku nazad.

Da bi utvrdili da li je čvor povoljan kao žrtveni jarac može da se vratimo na defeniciju:

size(left) <= α*size(node)
size(right) <= α*size(node)

Velika optimizacija se može izvršiti kad se utvrdi da mi već u suštini imamo dve od 3 tražene veličine i moramo da računamo samo poslednju. Razmotranjem sledećeg primera ćemo da demonstriramo ovo. Pod pretpostavkom da se penjemo nazad do korena.

size(parent) = size(node) + size(sibling) + 1

ali kako:

size(inserted node) = 1.

Sličaj postaje trivialan:

size[x+1] = size[x] + size(sibling) + 1

Gde je x = čvor, a x+1 roditelj i jedini poziv koji nam je potreban je poziv size(brata).

Jednom kad je žrtveno jare nadjeno, pod stablo zakačeno na žrtvenog jarca je iznova kreirano da bude balansirano.^[2]. Ovo se može uraditi za O(n) vremena, tako sto ćemo da predjemo preko svih čvorova podstabla, da bi ustanovili njihove vrednostiu sortiranom poretku, i rekruzivno biramo medijanu kao koren podstabla.

Pošto rebalansi uzimaju vremensku složenost od O(n) za najgoru situaciju to je ujedno i vremenska složenost, ali pošto su najgori slucajevi retki amortizovana vremenska slozenost će biti O(log n).

Skica dokaza za troškove umetanja уреди

Nebalansiranost čvora v je apsolutna vrednost razlika u veličini između njegovog levog i desnog čvora minus 1 ili 0, koje god je veće. Drugim rečima:

$I(v)=max(|left(v)-right(v)|-1,0)\$

Odmah posle izgradnje pod stabla v, l(v)=0.

Lema: Pre izgradnje pod stabla cvora v:

$I(v)=\Omega (|v|)\$
( $\Omega \$ is Big O Notation.)

Dokaz leme:

Neka je $v_{0}$ koren odmah posle kreiranja $h(v_{0})=log(|v_{0}|+1)\$ Ako je $\Omega (|v_{0}|)$ degenerisano umetanje (to jest, gde je svaki ubačenog povećava visinu 1), zatim

$I(v)=\Omega (|v_{0}|)\$ ,
$h(v)=h(v_{0})+\Omega (|v_{0}|)\$ i
$log(|v|)\leq log(|v_{0}|+1)+1\$ .

Posto je $I(v)=\Omega (|v|)$ pre ponovnog pravljenja $\Omega (|v|)$ insercije u podstablu sa korenom u $v$ koja nije dovela u obnovi. Svaki od ovih umetanja se mogu izvesti u O (log n). Konačna umetanje koja izaziva troškove $O(|v|)$ Korišćenje ukupnu analize postaje jasno da amortizuju troškovi umetak je $O(logn)$

${\Omega (|v|)O(\log {n})+O(|v|) \over \Omega (|v|)}=O(\log {n})\$

Brisanje уреди

Žrtveni jarac stabla su neobična po tome što je brisanje lakše nego ubacivanje. Da biste omogućili brisanje, žrtveni jarac stabla je potrebno da se sačuva dodatna vrednost sa strukturom podataka stabla. Ovo svojstvo, koju ćemo zvati MaxNodeCount jednostavno predstavlja najvišu postignutu NodeCount. Postavljen je za NodeCount kad god se rebalansira celo stablo, a nakon ubacivanja postavljen je na max(MaxNodeCount, NodeCount).Da bi se izvršilo brisanje, mi jednostavno uklonimo čvor kao što bi u jednostavnom binarnom stablu pretrage, ali ako

NodeCount <= α*MaxNodeCount

onda ćemo rebalans celo stablo oko korena, sećajući da postavimo MaxNodeCount na NodeCount. Ovo daje brisanje za svoj najgori mogući učinak O (n) , ali se amortizuje za O (log n) prosečno vreme.

Skica dokaza za troškove brisanja уреди

Pretpostavimo a zrtveni jarac stablo ima $n$ elemenata i upravo je bilo ponovo kreirano, (drugim recima kompletno binarno stablo je). Najvise $n/2-1$ brisanja se moze obaviti pre nego što se stablo mora nanovo kreirati. Svako ovo brisanje košta $O(\log {n})$ vremena,(vreme da se nadje elemant i obeleži) posle $n/2$ puta ce izazvati da se stablo ponovo izgradi. $O(\log {n})+O(n)$ Korišćenje ukupnu analize postaje jasno da troškove otplate brisanje je $O(\log {n})$ :

${\sum _{1}^{n \over 2}O(\log {n})+O(n) \over {n \over 2}}={{n \over 2}O(\log {n})+O(n) \over {n \over 2}}=O(\log {n})\$

Pretraga уреди

Pretraga nije modifikovan od strane standardnog stable pretrage, i ima najgore vreme od O(log n). Ovo je suprotno Ugaonom stablo koja imaju najgoru sloyenost od O(n).Smanjena memorije za čvorove u odnosu na druge samo-balansirajuće binarnih stabala pretrage može dodatno poboljšati lokalne reference i keša.

Reference уреди

^ Andersson, Arne (1989). „Improving partial rebuilding by using simple balance criteria”. Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms. Springer-Verlag. стр. 393—402. doi:10.1007/3-540-51542-9_33.
^ ^а ^б Galperin, Igal; Rivest, Ronald L. „Scapegoat trees”. Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms: 165—174 year=1993

Vidi još уреди

Spoljašnje veze уреди

[anderson1-1] Andersson, Arne (1989). „Improving partial rebuilding by using simple balance criteria”. Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms. Springer-Verlag. стр. 393—402. doi:10.1007/3-540-51542-9_33.

[galperin_rivest-2] а ^б Galperin, Igal; Rivest, Ronald L. „Scapegoat trees”. Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms: 165—174 year=1993

[1]

[2]