X-brzo drvo

X-fast tree
Tip	Trie
Smišljeno	1982
Smisllio	Dan Willard
Asymptotic complexity in big O notation
Prostor	O(n log M)
Pretraživanje	O(log log M)
Ubacivanje	O(log M) amortized
Brisanje	O(log M) amortized

U računarskoj nauci, x-brzo drvo je struktura podataka za čuvanje celih brojeva iz povezanog domena. Podržava upite i predaka i naslednika u vremenu O(log log M), korišćenjem O(n log M) prostora, gde je n broj sačuvanih vrednosti i M maksimalna vrednost u domenu. Strukturu je predložio Dan Willard u 1982, uz komplikovanije y-brzo drvo, kao način da poboljša korišćenje van Emde Boas drveća, zadržavajući O(log log M) vreme upita.

Struktura

An x-fast trie containing the integers 1 (001₂), 4 (100₂) and 5 (101₂). Blue edges indicate descendant pointers.

x-brzo drvo je bitwise trie:  binarno drvo gde svako podrvo čuva vrednosti čije binarne reprezentacije počinju s istim prefiksom. Svaki unutrašnji čvor je označen sa čestim prefiksom vrednosti u njegovom poddrvetu i tipično, levo dete dodaje nulu na kraj prefiksa, dok desno dete dodaje jedinicu. Binarna reprezentacija celih brojeva između 0 i M − 1 koristi ⌈log₂ M⌉ bitova, tako da je visina drveta O(log M).

Sve vrednosti u x-brzom drvetu se čuvaju na listovima. Unutrašnji čvorovi se čuvaju samo ako imaju listove u njihovom poddrvetu. Ako unutrašnji čvor nema levo dete, on čuva pokazivač na najmanji list u svo poddrvetu, koji se zove naslednički pokazivač. Slično, ako nema desno dete, čuva pokazivač na najveći list u svom levom poddrvetu. Svaki list čuva pokazivač na pretka i naslednika, i tako formira dvostruko povezanu listu. Konačno, postoji heš tabela za svaki nivo koja sadrži sve čvorove na tom nivou. Zajedno, ove heš tabele iz level-search strukture (LSS). Da garantuje vremena upita u najgorem slučaju, ove heš tabele bi koristile dinamički savršeno heširanje ili cuckoo hashing.

Totalno zauzimanje prostora je O(n log M), jer svaki element ima put od korena do lista dužine O(log M).

Operacije

Kao van Emde Boas drveća, x-brza drveća podržavaju operacije uređenog associative array. Ovo uključuje uobičajene operacije asocijativnog niza, zajedno sa još dve operacije sređivanja, Successor i Predecessor:

• Find(k): traži vrednost povezan sa datim ključem
• Successor(k): traži ključ/vrednost par sa najmanjim ključem većim ili jednakim datom ključu
• Predecessor(k): traži ključ/vrednost par sa najvećim ključem manjim ili jednakim datom ključu
• Insert(k, v): ubaci dati ključ/vrednost par
• Delete(k): ukloni ključ/vrednost par sa datim ključem

Traženje

Pronađi vrednost povezanu sa ključem k koji je u strukturi podataka može da se izvrši u konstantnom vremenu tražeći k u LSS[0], što je heš tabela na svim listovima.

Naslednik i predak

D bi pronašli pretka ili naslednika ključa k, prvo tražimo A_k, najnižeg naslednika k. Ovo je čvor čvor u drvetu koji ima najduži slični prefiks sa k. Da bi pronašli A_k, izvodimo binarnu pretragu na nivoima. Počinjemo na nivou h/2, gde je h visina drveta. Na svakom nivou, koristimo odgovarajuću heš tabelu u strukturi sa prefiksom k odgovarajuće dužine. Ako čvor s tim prefiksom ne postoji, znamo da A_k mora da bude na višem nivou i ograničavamo našu pretragu na njih. Ako čvor s tim prefiksom postoji, A_k ne može biti na višem nivou, premda ograničavamo pretragu na trenutnim i nižim nivoima.

Kada pronađemo najnižeg naslednika k, znamo da ima listove u nekim od svojih poddrveća (u suprotnom ne bi bili u drvetu) i k bi trebalo da bude u drgom poddrvetu. Premda naslednički pokazivač pokazuje na naslednika ili pretka od k. U zavisnosti od toga koji tražim, možda bi trebalo da preduzmemo jedan korak u povezanoj listi do prethodnog ili sledećeg lista.

S obzirom da drvo ima visinu O(log M), binarna pretraga za najnižeg naslednika uzima vreme od O(log log M). Pose toga, naslednik ili predak mogu da se pronađu u konstantnom vremenu, tako da ukupno vreme upia iznosi O(log log M).

Ubacivanje

Da bismo ubacili ključ/vrednost par (k, v), prvo tražimo pretka i naslednika od k. Onda stvaramo novi list za k, ubacujemo ga u povezanu listu na listove između naslednika i pretka, i dajemo mu pokazivač na v. Dalje, idemo od korena do novog lista, stvarajući neophodne čvorove na putu naniže, ubacujući ih u respektivne heš tabele i ažuriramo nasledničke pokazivače ako je neophodno.

Jer moramo da prođemo kroz čitavu visinu drveta, proces oduzima vreme od O(log M) .

Brisanje

Da bismo obrisali ključ k, tražimo list koristeći heš tabel na listovima. Uklanjamo je iz povezane liste, ali pamtimo ko su bili naslednik i predak. Onda se krećemo od lista do korena drveta, uklanjajući sve čvorove čija su poddrva sadržavala k i ažuriramo nasledničke pokazivače gde je potrebno. Naslednički pokazivači koji su  korišćeni za pokazivanje na k će sada pokazivati ili na naslednika ili na pretka od k, u zavisnosti od poddrveta koje nedostaje.

Kao ubacivanje, ovo uzima O(log M) vremena, jer moramo da prođemo kroz svaki nivo drveta.

Diskusija

Willard je predstavio x-brzo drveće uglavnom kao uvod u y-brzo drveće, koje omogućuje isto vreme upita, koristeći samo O(n) prostora i dozvoljavajući ubacivanja i brisanja u vremenu od O(log log M) .

Tehnika kompresije je slična patricia tries može da se koristi da znatno smanji korišćenje prostora x-brzih drveća u praksi.

Korišćenjem eksponencijalnog pretraživanja pre binarnog po nivoima i slanjem upita ne samo trenutnom prefiksu x, nego takođe njegovom nasledniku x + 1, x-brzo drveće može da odgovori na upite predaka i naslednika u vremenu od O(log log Δ), gde je Δ razlika između vrednosti upita i njegovok pretka i naslednika.

Spoljašnje veze

• Open Data Structure - Chapter 13 - Data Structures for Integers