Dekartovo drvo
U kompjuterskoj nauci, Dekartovo drvo (Dekartovo stablo, treap) i binarno pretraživačko drvo na slučajan način su dve usko povezane forme binarnog pretraživačkog drveta kao strukture podataka koja održava dinamički skup uređenih ključeva i omogućava binarno pretraživanje među ključevima. Nakon svakog umetanja ili brisanja ključa, oblik drveta je nasumično promenljiv sa istom raspodelom verovatnoće kao kod slučanog binarnog stabla; a naročito je velika verovatnoća da je njegova visina proporcionalna logaritmu broja ključeva, tako da je vremenska složenost operacija pretraživanja, umetanja ili brisanja jednaka logaritamskoj.
| Dekartovo drvo | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tip | Randomizovano stablo binarne pretrage | ||||||||||||||||||||
| Vremenska kompleksnost u velikoj O notaciji | |||||||||||||||||||||
| |||||||||||||||||||||
Opis
уреди
Dekartovo drvo su prvi put opisali Cecilija Aragon i Rejmond Sidel 1989. godine.[1][2] To je Kartezijansko stablo[3] u kojem je svakom ključu dat (nasumično izabran) brojčani prioritet. Kao i kod svih binarno pretračivackih stabala, redosled obilaska čvorova je isti kao i sortirani poredak ključeva. Struktura stabla je određena zahtevom da ono ima uređen hip: tj. prioritetni broj za bilo kojeg čvora koji nije list mora biti veći ili jednak prioritetnim brojevima njegovih potomaka. Stoga, kao što je to generalno slučaj kod Kartezijanskih stabala, korenski čvor ima maksimalni prioritet, a njeno levo i desno potstablo se formiraju na isti način iz podsekvenci sa sortiranim redosledom levo i desno od tog čvora.
Ekvivalentan način opisivanja Dekartovog drveta je da ono može biti formirano umetanjem čvorova sledeći opadajući redosled prioriteta u binarno pretraživačko drvo bez ikakvog uravnotežavanja. Dakle, ukoliko su prioriteti nezavisni slučajni brojevi (iz distribucije dovoljno velikog prostora mogućih prioriteta kako bi se osiguralo da je veoma mala verovatnoća da dva čvora imaju isti prioritet) onda je Dekartovo stablo ima istu distribuciju verovatnoće kao i randomno binarno stablo, što je pretraživačko stablo formirano umetanjem čvorova bez uravnotežavanja u slučajno randomno izabranom redosledu umetanja. Pošto je za randomno binarno pretraživačko drvo poznato da ima ima logaritamsku visinu sa visokom verovatnoćom, isto važi i za Dekartova stabla.
Aragon i Seidel takođe sugerišu na dodeljivanje većih prioriteta na češće pristupne čvorove, na primer procesom koji, na svakom pristupu stablu, izabere slučajan broj pa zameni prioritet čvora tim brojem, ako mu je prioritet veći od prethodnog. Ova modifikacija bi izazvala da stablo izgubi svoj nasumični oblik; umesto toga, češće pristupani čvorovi će verovatno biti blizu korena stabla, izazivajući da njhovo pretraživanje bude brže.
Blelloch i Reid-Miller[4] opisuju aplikaciju Dekartovog drveta za probleme održavanja skupa stavki i obavljanje operacija skupa unije, skupa preseka, i skupa razlike, korišćenjem Dekartovog drveta za prikaz svakog skupa. Naor and Nissim[5] opisuju primenu u održavanju autorizacije certifikata u kriptosistemima s javnim ključem.
Operacije
уредиKonkretno, Dekartovo stablo podržava sledeće operacije:
- Da biste potražili zadatu vrednost, primenjuje se standardni algoritam za binarnu pretragu u binarnom stablu pretrage, ignorišući prioritete.
- Da biste umetnuli novi ključ X u Dekartovo stablo, treba generisati slučajni prioritet Y za X. Binarnom pretragom za X u stablu kreiramo novi čvor na poziciji lista, gde binarnom pretragom određujemo da čvor za X treba da postoji. Zatim, dok X nije koren stabla i ima veći prioritetni broj od svog roditelja Z, obavljamo rotaciju stabla koja obrće roditelj-dete odnos za X i Z.
- Da biste izbrisali čvor X iz Dekartovog stabla, ako je X list stabla, jednostvno ga ukloniti. Ako X ima jedno dete Z, tada X ukloniti sa stabla tako da Z bude roditelj X (ili napraviti da je Z koren stabla, ako je X imao roditelja). Konačno, ako X ima dvoje dece, tada on menja svoju poziciju u stablu sa položajem njegovog neposrednog naslednika Z u sortiranom redosledu, što će eventualno dovesti do nekog od prethodnih slučajeva. U ovom poslednjem slučaju, tokom zamene može doći do narušavanja Hipa, te će onda možda morati da se vrše neke dodatne rotacije kako bi se vratilo u Hip stanje stabla.
- Da biste podelili Dekartovo stablo na dva manja Dekartov stabla, na one manje i one veće od ključa X, X ubacite u Dekartovo stablo sa maksimalnim prioritetom - većim prioritetom od bilo kog čvora u Dekartovom stablu. Nakon ovog umetanja, X će biti koren Dekartovog stabla, sve vrednosti manje od X će se naći u levom podstablu, a sve vrednosti veće od X će se naći u desnom podstablu. Ova operacija košta koliko i jedno ubacivanje u Dekartovo stablo.
- Spajanje dva Dekartova stabla koje su proizvod prethodne podele, možemo slobodno da pretpostavimo da je najveća vrednost jednog podstabl manja od najmanje vrednosti drugog. Ubacite vrednost X, tako da ona bude veca od ove maksimalne vrednosti jednog stabla i manja od minimalne vrednosti drugog, i dodelite mu minimalni prioritet. Nakon ubacivanja biće čvor list, pa može lako biti obrisan. Rezultat je jedno Dekartovo stablo spojen od dva originalna stabla. Ovo je praktično "vraćanje" odvajanja, a košta isto.
Binarno pretraživačko drvo na slučajan način
уредиBinarno pretraživačko drvo na slučajan način, predstavljeno od strane Martíneza i Roura odmah nakon rada Aragona i Seidela na Dekartovim stablima,[6] skladišti iste čvorove, sa istom nasumičnom raspodelom oblika stabla, ali zadržava drugačije informacije u okviru čvorova stabla u cilju održavanja svoje sučajne strukture.
Umesto skladištenja nasumičnih prioriteta na svakom čvoru, Binarno pretraživačko drvo na slučajan način skladišti mali ceo broj u svakom čvoru, a to je broj njegovih potomaka (računajući i sebe kao jedan); ovi brojevi se mogu održavati tokom operacije rotacije stabla u sa konstantnim dodatnim vremenom za svaku operaciju rotacije. Kada treba da ubacimo ključ X u stablo koje već sadrži n čvorova, algoritam umetanja bira sa verovatnćom 1/(n + 1) da postavi X kao nov koren stabla, a inače se poziva postupak za umetanje rekurzivno u levo ili desno podstablo (u zavisnosti da li je njegov ključ manji ili veći od trenutnog korena). Brojevi potomaka se koriste u algoritmu za izračunavanje potrebne verovatnoće kod slučajnog izbora u svakom koraku. Postavljanje X u koren stabla se može vršiti bilo kao kod Dekartovog stabla, stavljajući ga na list, a zatim okretanjem na gore, ili po alternativnom algoritmu koji su opisali Martínez i Roura koji deli podstablo na dva dela, koji se kasnije koriste kao levi i desni potomak novog čvora.
Postupak brisanja kod binarno pretraživačkog stabla na slučajan način koristi istu informaciju za čvorove kao i procedura umetanja, a kako on čini deo od O(log n) nasumičnih odluka kako bi se spojila dva podstabla u opadajućem poredku levog i desnog potomka izbrisanog čvora u stablu. Ako su levo i desno podstablo koje želimo da obrišemo prazni, tada je operacija spajanja trivijalna; inače je, levi ili desni potomak izbrisanog čvora izabran kao novi koren podstabla sa verovatnoćom proporcionalnoj njegovom broju potomaka, pa se operacija spajanja nastavlja rekurzivno.
Poređenje
уредиInformacija koja je uskladištena u čvorovima u binarno pretraživačkom stablu na slučajan način je jednostavnija nego u Dekartovom stablu (mali ceo broj, a ne visoke preciznosti slučajnih brojeva), ali zahteva veći broj poziva generatora slučajnog broja (koji ima O(log n) poziva po operaciji umetanja ili brisanja, umesto samo jednog poziva po umetanju) i postupak ubacivanja je malo komplikovaniji zbog potrebe da se ažurira broj potomaka za svaki čvor. Manja tehnička razlika je ta što, u Dekartovom stablu, postoji mala verovatnoća sudara (da va ključa imaju isti prioritet), a u oba slučaja će biti statističke razlike između pravog generatora slučajnih brojeva i generator pseudo-slučajnih brojeva koji se obično koriste na digitalnim računarima. Međutim, u svakom slučaju je razlika između teorijskog modela savršenih slučajnih izbora koji se koriste za dizajn algoritama i mogućnosti stvarnih generatora slučajnih brojeva su zanemarljivo male.
Iako Dekartovo stablo i binarno pretraživačko stablo na slučajan način oba imaju istu nasumičnu raspodelu oblika stabla nakon svakog ažuriranja, istorija, izmena stabala koje se obavljaju kod ove dve strukture podataka nakon niza operacia umetanja ili brisanja, može biti različita. Na primer, u Dekartovom stablu, ako se tri broja 1,2 i 3 umetnu u redosledu 1,3,2, azatim se broj 2 izbriše, preostala dva čvora će imati istu roditelj-potomak odnos kao i pre umetanja srednjeg broja. U binarno pretraživačkom stablu na slučajan način, stablo nakon brisanja je pođednako verovatno da će biti jedan od dva moguća stabla na osnovu njegova dva čvora, nezavisno od toga kako je stablo izgledalo pre ubacivanja srednjeg broja.
Reference
уреди- ^ Aragon, Cecilia R.; Seidel, Raimund (1989), „Randomized Search Trees”, Proc. 30th Symp. Foundations of Computer Science (FOCS 1989) (PDF), Washington, D.C.: IEEE Computer Society Press, стр. 540—545, ISBN 0-8186-1982-1, doi:10.1109/SFCS.1989.63531
- ^ Seidel, Raimund; Aragon, Cecilia R. (1996), „Randomized Search Trees”, Algorithmica, 16 (4/5): 464—497, doi:10.1007/BF01940876
- ^ Vuillemin, Jean (1980), „A unifying look at data structures”, Commun. ACM, New York, NY, USA: ACM, 23 (4): 229—239, doi:10.1145/358841.358852
- ^ Blelloch, Guy E.; Reid-Miller, Margaret (1998), „Fast set operations using treaps”, Proc. 10th ACM Symp. Parallel Algorithms and Architectures (SPAA 1998), New York, NY, USA: ACM, стр. 16—26, ISBN 978-0-89791-989-0, doi:10.1145/277651.277660
- ^ Naor, M.; Nissim, K. (2000), „Certificate revocation and certificate update”, IEEE Journal on Selected Areas in Communications, 18 (4): 561—570, doi:10.1109/49.839932
- ^ Martínez, Conrado; Roura, Salvador (1997), „Randomized binary search trees”, Journal of the ACM, 45 (2): 288—323, doi:10.1145/274787.274812
Spoljašnje veze
уреди
- Collection of treap references and info by Cecilia Aragon
- Open Data Structures - Section 7.2 - Treap: A Randomized Binary Search Tree
- Treap Applet Архивирано на сајту Wayback Machine (4. март 2015) by Kubo Kovac
- Animated treap
- A high performance key-value store based on treap by Junyi Sun
- Pure Python and Cython in-memory treap and duptreap
- Treaps in C#. By Roy Clemmons
- Pure Go in-memory, immutable treaps
- Pure Go persistent treap key-value storage library