Tango stablo

Tango stablo (енгл. tango tree) je vrsta binarnog stabla pretraživanja kojeg su napravili Erik D. Demaine, Dion Harmon, John Iacono i Mihai Patrascu 2004. godine. To je online binarno pretraživačko stablo koje postiže vremensku složenost $O(\log \log n)$ u konkurentnom odnosu prema odgovarajućem offline algoritmu i koristi samo $O(\log \log n)$ bitova dodatnog prostora memorije po čvoru. Ovo je napredak u odnosu na prethodni najbolji konkurentni odnos koji je bio $O(\log n)$.

Struktura

Tango stablo funkcioniše tako što particioniše binarno pretraživačko stablo u skup poželjnih staza koji su onda smeštena u pomoćna stabla (tako da je tango stablo predstavljeno kao stablo stabala).

Referencno stablo

Da bismo konstruisali tango stablo moramo da simuliramo kompletno binarno pretraživačko stablo koje se zove referencno stablo', koje je u suštini samo klasično binarno pretraživačko stablo koje sadrži sve elemente. Ovo stablo se nikada ne pojavljuje u samoj implementaciji ali je u osnovi narednih delova tango stabla.

Poželjne staze

Prvo za svaki čvor definišemo prioritetno dete koje je neformalno najskorije 'dodirnuto' dete od strane klasične binarne pretrage stabla. Formalnije, posmatramo podsablo T sa korenom k i decom tog korena l (levi) i d (desni). Određujemo da je d prioritetno dete korena k ako je najskorije posećen čvor stabla T u podstablu koje kao koren ima vrednost d, a l će postati prioritetno dete ako to nije slučaj. Primetimo da ako je najskorije posećen čvor stabla T sam koren k, onda l postaje prioritetno dete po definiciji.

Poželjna staza se definiše tako što krenemo od korena i pratimo prioritetnu decu sve dok ne stignemo do lista. Uklanjanjem čvorova na ovom putu particionišemo ostatak stabla u određen broj podstabla i onda rekurentno pravimo poželjnu stazu u svakom od ovih podstabala koje dalje pravi još podstabla.

Pomoćna stabla

Da bismo predstavili poželjnu stazu moramo da sačuvamo njegove čvorove u balansirano binarno stablo pretraživanja, specifičnije crveno-crno stablo. Svaki čvor n koji nije list u poželjnoj stazi S ima neprioritetno dete c koji je koren novog pomoćnog stabla. Spajamo koren ovog drugog pomoćnog stabla (c) sa n u S i ovako povezujemo pomoćna stabla. Takođe uvećavamo pomoćno stablo tako što čuvamo kod svakog čvora minimalnu i maksimalnu dubinu (u referentnom stablu) čvorova podstabla kome je taj čvor koren.

Algoritam

Pretraga

Da bismo pronašli element u tango stablu moramo da simuliramo pretragu referentnog stabla. Počnemo tako što pretražujemo poželjnu stazu koja je povezana sa korenom, što simuliramo tako što pretražujemo pomoćno stablo koje odgovara toj poželjnoj stazi. Ako to pomoćno stablo ne sadrži traženi element pretraga se prekida na roditelju korena podstabla koji sadrži traženi element (to jest, početak druge poželjne staze), tako da jednostavno nastavimo pretragu pomoćnog stabla za tu poželjnu stazu.

Ažuriranje

Da bismo održali strukturu tango stabla (pomoćna stabla koja odgovaraju poželjnim stazama), moramo da ažuriramo stablo svaki put kad se prioritetno dete promeni kao posledica pretraga. Kad se prioritetno dete promeni, gornji deo poželjne staze se 'otkači' od donjeg dela (koji postane zasebna poželjna staza) i prespaja se sa drugom poželjnom stazom (koji postaje novi donji deo). Da bi se ovo radilo efikasno moramo da imamo definisano iseci i spoji operaciju kod naših pomoćnih stabala.

Spoji

Operacija spoji će da spoji dva pomoćna stabla sve dok za njih važi da je gornji čvor jednog od njih u referentnom stablu dete nekog od čvorova na dnu drugog (u suštini da se te dve poželjne staze mogu spojiti). Ovo radi na osnovu operacije ulančati crveno-crnih stabala, koji spaja dva stabla sve dok imaju osobinu da svi elementi jednog su manji od svih elemenata drugog i podeli koji radi obrnuto. U referentnom stablu treba da primetimo da dva čvora u gornjem delu postoje ako i samo ako postoji čvor u donjem delu čija je vrednost između njihovih. Da bismo spojili donji deo sa gornjim moramo da podelimo gornji deo između ta dva čvora i onda da ulančamo ta dva nova pomoćna stabla sa donjim delom i tako dobijemo naše konačno spojeno pomoćno stablo.

Iseci

Operacija iseci će da slomi poželjnu stazu na dva dela kod određenog čvora na gornji deo i na donji deo. Formalnije, izvršiće particionisanje pomoćnog stabla u dva pomoćna stabla takva da jedan sadrži sve čvorove do ili iznad određene dubine referentnog stabla, a drugi će da sadrži sve čvorove ispod. Kao kod spoji treba da primetimo da gornji deo ima dva čvora koja 'okružuju' dornji deo. Zbog toga možemo jednostavno da podelimo ta dva čvora da bismo dobili tri putanje i onda ulančamo dve spoljne putanje tako da dobijemo dve putanje, gornju i donju, što smo i hteli.

Konkurentni odnos

Tango stabla su $O(\log \log n)$-konkurentna jer posao koji odradi optimalan offline binarno pretraživačko stablo je makar linearno u k (ukupan broj menjanja prioritetne dece) i posao koji uradi tango stablo je u najgorem slučaju $(k+1)O(\log \log n)$

Pogledati

• Splay stablo
• Binarno stablo pretrage
• Crveno-crno stabla
• Binarno stablo