Fuziono stablo
Fuziono stablo predstavlja stablo koje implementira asocijativni niz nad w-bitnim celim brojevima. Коristi O(n) prostora i izvršava pretragu u O(logw n)) 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 urađeno od kad su Fredman i Vilard osmislili algoritam 1990. 1999. prikazano je kako se može implementirati fuziono stablo preko AC0 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 O(logw n) složenosti. Druga dinamička verzija koja je predložena 2007. koristi eksponencijalno stablo čija je složenost u najgorem slučaju O(logw n + log 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 O(logwn) po operaciji.

Каko radi 
Fuziono stablo je u osnovi B-stablo sa izdvajanjem faktora w1/5 (bilo koji mali eksponent dolzi u obzir), koji daje složenost O(logw n). Da bismo postigli željenju radnu verziju za ispravke i upite, fuzionim stablom moramo omogućiti da pretrazivanje čvora podrazumeva više od w1/5 ključeva u konstantnom vremenu. Ovo se može uraditi “sabijanjem” ključeva tako da se svi mogu snaći na mašinskom jeziku, što zauzvrat omogućava da se sabijanje radi paralelno. Ostatak ovog članka će opisati operacije u statičkom Fuzionom stablu, u kom su podržani samo upiti.

Skiciranje 
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, sketch(x) < sketch(y) za bilo koja sva ključa gde je x<y.

Približna skica 
Ako je zapis kompresovanih bita b1 < b2 < ··· < br, onda je kompresovanje ključa xw-1···x1x0 r-bitnog celog broja . 
Sa standardnim operacijama kakve se koriste u C jeziku, teško je direktno izračunati kompresovanje ključa u konstantnom vremenu. Umseto toga, kompresovani bitovi mogu biti zapakovani u opsegu veličine od najviše r4 , koristeći bitovsko AND i množenje. Bitovsko AND služi da ukloni sve nekompresovane bitove iz ključa, dok množenje pomera kompresovane bitove u mali niz. Kao i „savršena“ skica, skica čuva približan raspored ključeva.
Za neke reči je potrebno utvrditi tačan broj umnožavanja konstanti. Svaki kompresovani bit na lokaciji bi će množenjem biti pomeren na bi + mi preko m = . Za približno skiciranje moramo se držati sledećih pravila:
 bi + mj su različiti za svaki par (i, j). To nam garantuje da kompresovani bitovi neće biti oštećeni prilikom množenja.
 bi + mj je strogo rastuća funkcija od i. To znači da je redosled kompresovanih bitova očuvan.
 (br + mr) - (b1 - m1) ≤ r4. To znači da su kompresovani bitovi zapakovani u opsegu veličine od r4.
Induktivni argument pokazuje kako mi može biti konstruisan. Neka je m1 = w − b1. Pretpostavimo da 1 < t ≤ r i da su 'm1, m2... mt već izabrani. Onda se izabere najmanji ceo broj mt koji zadovoljava osobine (1) i (2). Osobina (1) zahteva da mt ≠ bi − bj + ml za sve 1 ≤ i, j ≤ r i 1 ≤ l ≤ t-1. Prema tome, postoji manje od tr2 ≤ r3 koji mt mora da zadovoljava. Kad je mt izabran da bude minimum,(bt + mt) ≤ (bt-1 + mt-1) + r3. Ovo objašnjava osobinu (3).

Približan zapis se izračunava na sledeći način:
1. Maskiraju se svi kompresovani i bitovi koji su konjugovani .
2. Množenjem ključ će biti predodređen za konstantu m. Ova operacija u stvari zahteva dve mašinske reči , ali ovo i dalje može biti urađeno u konstantnom vremenu.
3. Maskira se sve, osim pomerenih kompresovanih bitova. Oni se sada smeštaju u susedni blok od najviše r4 < w4/5 bita. 
U nastavku ovog članka, kompresovanje će označavati približno skiciranje.

Paralelno poređenje 
Cilj kompresije je da sabijanjem dozvoli da svi ključevi budu smešteni u jednu w-bitnu reč. Onda će sabijanje čvora biti sledeći niz znakova: 1sketch(x1)1sketch(x2)...1sketch(xk) .
Možemo videti da sketch funkcija koristi tačno b ≤ r4 bita. Zatim, svaki blok koristi 1 + b ≤ w4/5 bita, a od k ≤ w1/5 , ukupan broj bitova u čvoru je najviše w. Ukratko: za niz s i ne negativni broj m, sm označava ulančavanje niza s m puta. Ako je t takođe niz, st označava niz od t do s. Skiciranje čvora omogućava nam da pretrazujemo ključ za bilo koji b-bitni ceo broj y. Neka je z = (0y)k može biti izračunato i u konstantnom vremenu (množenje u konstantom (0b1)k). Napomenimo da je 1sketch(xi) - 0y uvek pozitivno, ali čuva vodeću skicu 1 iff sketch(xi) ≥ y. Mi na taj način možemo izračunati najmanji index i tako da sketch(xi) ≥ y podrazumeva 
 Oduzimanjem z iz čvora
 Uzeti razlike bitovskog „I“ i konstante (10b)k. Ovo briše sve osim vodećeg bita svakog bloka.
 Naći najvažniji bit rezultata.
 Izračunati i, koristeći činjenicu da je vodeći bit i-tog bloka imamindex i(b+1).

Dekompresovanje 
Za proizvoljan upit, paralelna komparacija izračunava indeks i prema sledećoj formuli 
sketch(xi-1) ≤ sketch(q) ≤ sketch(xi).
Nažalost, šema funkcije ne čuva kopiju ključeva tako da nije neophodno da xi-1 ≤ q ≤ xi. Šta je tačno u tome, od svih ključeva, bilo xi-1 or xi imaju najduži zajednički prefiks sa q. To je zato što bilo koji ključ y sa dužim prefiskom istim sa q, takođe ima više zajedničkih kompresovanih bitova sa q, i sketch(q) je mnogo sličniji sketch(xj). 
Najduži zajednički prefiks između dva w-bitna cela broja a i b mogu biti izračunati u konstantnom vremenu, tako što se traži najznačajniji bit diskjunkcije od a i b. Ovo se može upotrebiti kao maska za sve bite sem za zajedničke prefiksne bitove.
Napomenimo da p tačno definiše gde se q grananje završava.Ako je sledeći bit od q 0, onda se naslednik od q nalazi u p1 podstablu, i ako je sledeći bit od q 1, onda se predak od q nalazi u p0 podstablu. Ovo prati sledeći algoritam:
 Koristi se paralelna komparacija da se nađe sledeći indeks i tako da važi sketchsketch(xi-1) ≤ sketch(q) ≤ sketch(xi).
 Izračunava se najduzi zajednički prefiks od p i q, bilo xi-1 ili xi (uzima se duži od ova dva).
 Neka je l-1 dužina najdužeg zajedničkog prefiksa sa p.
 Ako je l-ti bit od q jednak 0, onda je e = p10w-l. Koristiti paralelnu komaparaciju da se nađe naslednik od sketch(e). To je u stvari predak od q.
 Ko je l-ti bit od q jednak 1, onda e = p01w-l.Koristi se komparacija da se nađe predak od sketch(e). To je u stvari naslednik od q.
 Kada jednom nađemo pretka ili naslednika od q, tačna pozicija q u grupi ključeva je određena.

Reference 

 MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)
 MIT CS 6.897: Advanced Data Structures: Lecture 5, More fusion trees; self-organizing data structures, move-to-front, static optimality, Prof. Erik Demaine (Spring 2003)
 MIT CS 6.851: Advanced Data Structures: Lecture 13, Fusion Tree notes, Prof. Erik Demaine (Spring 2007)
 MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)

Асоцијативни низови
Стабла (структуре података)
Fuziono stablo predstavlja stablo koje implementira asocijativni niz nad w-bitnim celim brojevima . Коristi O( n ) prostora i izvršava pretragu u O( logw n ) ) 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 urađeno od kad su Fredman i Vilard osmislili algoritam prikazano je kako se može implementirati fuziono stablo preko AC0 modela , u čijoj implementaciji više nije potrebno konstantno vreme . Dinamička verzija fuzionog stabla koja koristi heš tabele je predloženakoja je O( logw n ) složenosti . Druga dinamička verzija koja je predložena koristi eksponencijalno stablo čija je složenost u najgorem slučaju O( logw n + log 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 O( logwn ) po operaciji . Каko radi Fuziono stablo je u osnovi B-stablo sa izdvajanjem faktora w1 /5 ( bilo koji mali eksponent dolzi u obzir ) , koji daje složenost O( logw n ) . Da bismo postigli željenju radnu verziju za ispravke i upite , fuzionim stablom moramo omogućiti da pretrazivanje čvora podrazumeva više od w1 /5 ključeva u konstantnom vremenu . Ovo se može uraditi “ sabijanjem ” ključeva tako da se svi mogu snaći na mašinskom jeziku , što zauzvrat omogućava da se sabijanje radi paralelno . Ostatak ovog članka će opisati operacije u statičkom Fuzionom stablu , u kom su podržani samo upiti . Skiciranje 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 , sketch( x ) < sketch( y ) za bilo koja sva ključa gde je x<y . Približna skica Ako je zapis kompresovanih bita b1 < b2 < · · · < br , onda je kompresovanje ključa xw-1 · · ·x1x0 r-bitnog celog broja \ . Sa standardnim operacijama kakve se koriste u C jeziku , teško je direktno izračunati kompresovanje ključa u konstantnom vremenu . Umseto toga , kompresovani bitovi mogu biti zapakovani u opsegu veličine od najviše r4 , koristeći bitovsko AND i množenje . Bitovsko AND služi da ukloni sve nekompresovane bitove iz ključa , dok množenje pomera kompresovane bitove u mali niz . Kao i „ savršena “ skica , skica čuva približan raspored ključeva . Za neke reči je potrebno utvrditi tačan broj umnožavanja konstanti . Svaki kompresovani bit na lokaciji bi će množenjem biti pomeren na bi + mi preko m = \ . Za približno skiciranje moramo se držati sledećih pravila : bi + mj su različiti za svaki par ( i , j ) . To nam garantuje da kompresovani bitovi neće biti oštećeni prilikom množenja. bi + mj je strogo rastuća funkcija od i . To znači da je redosled kompresovanih bitova očuvan. ( br + mr ) - ( b1 - m1 ) ≤ r4 . To znači da su kompresovani bitovi zapakovani u opsegu veličine od r4. Induktivni argument pokazuje kako mi može biti konstruisan . Neka je m1 = w − b1. Pretpostavimo da< t ≤ r i da su 'm1 , m2... mt već izabrani . Onda se izabere najmanji ceo broj mt koji zadovoljava osobinei Osobinazahteva da mt ≠ bi − bj + ml za sve≤ i , j ≤ r i≤ l ≤ t-1 . Prema tome , postoji manje od tr2 ≤ r3 koji mt mora da zadovoljava . Kad je mt izabran da bude minimum,( bt + mt ) ≤ ( bt-1 + mt-1 ) + r3. Ovo objašnjava osobinu Približan zapis se izračunava na sledeći način : 1. Maskiraju se svi kompresovani i bitovi koji su konjugovani \. 2. Množenjem ključ će biti predodređen za konstantu m . Ova operacija u stvari zahteva dve mašinske reči , ali ovo i dalje može biti urađeno u konstantnom vremenu. 3. Maskira se sve , osim pomerenih kompresovanih bitova . Oni se sada smeštaju u susedni blok od najviše r4 < w4 /5 bita . U nastavku ovog članka , kompresovanje će označavati približno skiciranje . Paralelno poređenje Cilj kompresije je da sabijanjem dozvoli da svi ključevi budu smešteni u jednu w-bitnu reč . Onda će sabijanje čvora biti sledeći niz znakova:ketch( x1) 1sketch( x2) ...1sketch( xk ) \ . Možemo videti da sketch funkcija koristi tačno b ≤ r4 bita . Zatim , svaki blok koristi+ b ≤ w4 /5 bita , a od k ≤ w1 /5 , ukupan broj bitova u čvoru je najviše w . Ukratko : za niz s i ne negativni broj m , sm označava ulančavanje niza s m puta . Ako je t takođe niz , st označava niz od t do s . Skiciranje čvora omogućava nam da pretrazujemo ključ za bilo koji b-bitni ceo broj y . Neka je z = )k može biti izračunato i u konstantnom vremenu ( množenje u konstantom1 )k ) . Napomenimo da jeketch( xi ) - uvek pozitivno , ali čuva vodeću skicuiff sketch( xi ) ≥ y . Mi na taj način možemo izračunati najmanji index i tako da sketch( xi ) ≥ y podrazumeva Oduzimanjem z iz čvora Uzeti razlike bitovskog „ I “ i konstante )k . Ovo briše sve osim vodećeg bita svakog bloka . Naći najvažniji bit rezultata . Izračunati i , koristeći činjenicu da je vodeći bit i-tog bloka imamindex i( b+1 ) . Dekompresovanje Za proizvoljan upit , paralelna komparacija izračunava indeks i prema sledećoj formuli sketch( xi-1 ) ≤ sketch( q ) ≤ sketch( xi ) . Nažalost , šema funkcije ne čuva kopiju ključeva tako da nije neophodno da xi-1 ≤ q ≤ xi . Šta je tačno u tome , od svih ključeva , bilo xi-1 or xi imaju najduži zajednički prefiks sa q . To je zato što bilo koji ključ y sa dužim prefiskom istim sa q , takođe ima više zajedničkih kompresovanih bitova sa q , i sketch( q ) je mnogo sličniji sketch( xj ) . Najduži zajednički prefiks između dva w-bitna cela broja a i b mogu biti izračunati u konstantnom vremenu , tako što se traži najznačajniji bit diskjunkcije od a i b . Ovo se može upotrebiti kao maska za sve bite sem za zajedničke prefiksne bitove . Napomenimo da p tačno definiše gde se q grananje završava .Ako je sledeći bit od q onda se naslednik od q nalazi u p1 podstablu , i ako je sledeći bit od q onda se predak od q nalazi u p0 podstablu . Ovo prati sledeći algoritam : Koristi se paralelna komparacija da se nađe sledeći indeks i tako da važi sketchsketch( xi-1 ) ≤ sketch( q ) ≤ sketch( xi ) . Izračunava se najduzi zajednički prefiks od p i q , bilo xi-1 ili xi ( uzima se duži od ova dva ) . Neka je l-1 dužina najdužeg zajedničkog prefiksa sa p . Ako je l-ti bit od q jednak onda je e = p10w-l . Koristiti paralelnu komaparaciju da se nađe naslednik od sketch( e ) . To je u stvari predak od q . Ko je l-ti bit od q jednak onda e = p01w-l.Koristi se komparacija da se nađe predak od sketch( e ) . To je u stvari naslednik od q . Kada jednom nađemo pretka ili naslednika od q , tačna pozicija q u grupi ključeva je određena . Reference MIT CS897 : Advanced Data Structures : Lecture Fusion Trees , Prof . Erik Demaine ( Spring MIT CS897 : Advanced Data Structures : Lecture More fusion trees ; self-organizing data structures , move-to-front , static optimality , Prof . Erik Demaine ( Spring MIT CS851 : Advanced Data Structures : Lecture Fusion Tree notes , Prof . Erik Demaine ( Spring MIT CS851 : Advanced Data Structures : Lecture Fusion Tree notes , Prof . Erik Demaine ( Spring Асоцијативни низови Стабла ( структуре података )