X-brzo drvo
![]() | Ovom članku je potrebna lektura teksta. To podrazumeva ispravku gramatičkih, pravopisnih i interpunkcijskih grešaka ili tona. |
![]() | Ovaj članak je započet ili proširen kroz projekat seminarskih radova. Potrebno je proveriti prevod, pravopis i viki-sintaksu. Kada završite sa proverom, dopišete da nakon |provereno=. |
X-fast tree | |
---|---|
Tip | Trie |
Smišljeno | 1982 |
Smisllio | Dan Willard |
Asymptotic complexity | |
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,[1] 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
[uredi | uredi izvor]![A binary tree with 4 levels. The nodes on each level are: 3: (), 2: (0) and (1), 1: (00) and (10), 0: (001), (100) and (101). The unlabeled node is the root. There are directed edges between the folllowing nodes: ()->(0), ()->(1), (0)->(00), (0)->(001) in blue, (1)->(10), (1)->(101) in blue, (00)->(001) twice, once in blue, (10)->(100), (10)->(101), (001)<->(100), (100)<->(101). The nodes on each level are contained in a box, labeled with LSS(<level>).](http://upload.wikimedia.org/wikipedia/commons/thumb/8/85/Xfast_trie_example.svg/220px-Xfast_trie_example.svg.png)
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 ⌈log2 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
[uredi | uredi izvor]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
[uredi | uredi izvor]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.[2]
Naslednik i predak
[uredi | uredi izvor]D bi pronašli pretka ili naslednika ključa k, prvo tražimo Ak, najnižeg naslednika k. Ovo je čvor čvor u drvetu koji ima najduži slični prefiks sa k. Da bi pronašli Ak, 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 Ak mora da bude na višem nivou i ograničavamo našu pretragu na njih. Ako čvor s tim prefiksom postoji, Ak 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).[1]
Ubacivanje
[uredi | uredi izvor]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) .[3]
Brisanje
[uredi | uredi izvor]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.[3]
Diskusija
[uredi | uredi izvor]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) .[1]
Tehnika kompresije je slična patricia tries može da se koristi da znatno smanji korišćenje prostora x-brzih drveća u praksi.[4]
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.[2]
Reference
[uredi | uredi izvor]- ^ a b v Willard, Dan E. (1983).
- ^ a b Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Howat, John; Morin, Pat (2010), Fast Local Searches and Updates in Bounded Universes (PDF), Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010). str. 261–264
- ^ a b Schulz, André; Christiano, Paul (2010-03-04).
- ^ Kementsietsidis, Anastasios; Wang, Min (2009), Provenance Query Evaluation: What’s so special about it?, Proceedings of the 18th ACM conference on Information and knowledge management. str. 681–690