Back

ⓘ Fuziono stablo




                                     

ⓘ Fuziono stablo

Fuziono stablo predstavlja stablo koje implementira asocijativni niz nad w -bitnim celim brojevima. Коristi O prostora i izvršava pretragu u O) vremenu, koje je asimptotski brže od tradicionalnog binarnog stabla, i u stvari bolje od van Emde Boas stable gde je w veće. To postiže brzinu eksploatacije pojedinih operacija koje imaju konstantno vreme koje je potrebno u mašinskom jeziku. Fuziono stablo su osmislili Michael Fredman and Dan Willard.

Nekoliko naprednih stvari je uradeno od kad su Fredman i Vilard osmislili algoritam 1990. 1999. prikazano je kako se može implementirati fuziono stablo preko AC 0 modela, u čijoj implementaciji više nije potrebno konstantno vreme. Dinamička verzija fuzionog stabla koja koristi heš tabele je predložena 1996 koja je Olog w n složenosti. Druga dinamička verzija koja je predložena 2007. koristi eksponencijalno stablo čija je složenost u najgorem slučaju Olog w n + log u po operaciji, gde je u veličina najvećeg ključa. Ostaje otvoreno pitanje da li će dinamička fuzija moći da postigne složenost od Olog w n po operaciji.

Skiciranje je metod koji podrazumeva da svaki w-bitni ključ u čvoru sadrži k ključeva koji su kompresovani na samo k-1 bita. Svaki ključ x može se posmatrati kao deo binarnog stabla visine w koji počinje korenom i završava se listom koji odgovara x. Da bi se razlikovala dva dela, dovoljno je pogledati u njihove tačke grananja prvi bit gde se dva ključa razlikuju. Svi k delovi zajedno imaju k-1 tački grananja, zato je potrebno najviše k-1 bita da bi se razlikovali bilo koji od k ključeva.

Važna uloga skiciranja je da čuva red ključeva. To je, sketchx < sketchy za bilo koja sva ključa gde je x

                                     
  • података или друге алгоритме за обраду листа. Дан Стаут Њорен алгоритам Фузионо стабло Прескакање листа Уређивање Donald Knuth. The Art of Computer Programming
  • je formirati kompresovano digitalno stablo od ključeva u linearnom vremenu, a deca svakog čvora digitalnog stabla mogu se sortirati rekurzivno koristeći
  • је О 2m 2 где је m број битова у вредности приоритета. Алгоритам Фузионог стабла eng. Fusion tree algorithm осмишљеног од стране Мајкл Фредмана Michael