Википедија

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

Интерактиван преглед историје
Новија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Pravljenje nove teme
 
Нема описа измене
Ред 1:
'''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==
Ред 10:
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===
Ред 33:
==Pogledati==
* [[Splay stablo]]
* [[Binarno pretraživačko stablo pretrage]]
* [[Crveno-crno stabla]]
* [[Бинарно стабло|Binarno stablo]]
* [[Stabla (struktura podataka)]]
 
==Reference==
Преузето из „https://sr.wikipedia.org/wiki/Tango_stablo”