Tango stablo — разлика између измена

2 бајта додата ,  пре 7 година
нема резимеа измене
(Pravljenje nove teme)
 
'''Tango stablo''' (engl. tango tree) je vrsta [[Binarno stablo pretraživanjapretrage | binarnog stabla pretraživanja]] kojeg su napravili [[Erik D. Demaine]], Dion Harmon, John Iacono i [[Mihai Patrascu]] 2004. godine. To je [[online algoritmi|online]] binarno pretraživačko stablo koje postiže vremensku složenost <math>O(\log \log n)</math> u konkurentnom odnosu prema odgovarajućem [[offline algoritmi|offline]] algoritmu i koristi samo <math>O(\log \log n)</math> bitova dodatnog prostora memorije po čvoru. Ovo je napredak u odnosu na prethodni najbolji konkurentni odnos koji je bio <math>O(\log n)</math>.
 
==Struktura==
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 [[rekurzijaRekurzija|rekurentno]] pravimo poželjnu stazu u svakom od ovih podstabala koje dalje pravi još podstabla.
 
===Pomoćna stabla===
==Pogledati==
* [[Splay stablo]]
* [[Binarno pretraživačko stablo pretrage]]
* [[Crveno-crno stabla]]
* [[Бинарно стабло|Binarno stablo]]
* [[Stabla (struktura podataka)]]
 
==Reference==
4

измене