Dekartovo stablo

Из Википедије, слободне енциклопедије
Sekvenca brojeva i Dekartovo stablo izvedeno od njih.

Dekartovo stablo је binarno stablo izvedeno od niza brojeva. Može se jedinstveno definisati po osobinama da je hip-organizovano i da simetrična (in-order) šetnja stabla vraća prvobitnu sekvencu brojeva. Ovu strukturu podataka uveo je Vuillemin (1980) u sklopu rada sa strukturama podataka koje se koriste radi pretraživanja u geometrijskim problemima. Dekartova stabla se koriste i u problemima binarne pretrage radi definisanja struktura podataka kao što su treap, randomizovano binarno stablo pretrage. Dekartovo stablo za sekvence može biti konstruisano u linearnom vremenu korišćenjem algoritma zasnovanog na steku za nalaženje svih najbližih malih vrednosti u sekvenci vrednosti.

Definicija[уреди]

Dekartovo stablo za sekvence različitih brojeva može biti jednoznačno definisano poštujući sledeće karakteristike:

  1. Dekartovo stablo za sekvence ima jedan čvor za svaki broj u sekvenci. Svaki čvor je povezan sa jedinstvenom vrednošću.
  2. Simetrična (in-order) šetnja stabla vraća kao rezultat prvobitnu sekvencu brojeva. Levo pod-drvo se sastoji od vrednosti pre nego vrednost samog korena u sekvenci, dok se desno pod-stablo sastoji od vrednosti koje se nalaze nakon korena i sličan redosled se sastoji na svakom donjem čvoru stabla.
  3. Stablo ima hip-osobinu: otac svakog čvora (sem korena) ima manju vrednost nego vrednost samog čvora.

Prateći osobinu hipa, koren stabla mora imati vrednost najmanjeg broja u sekvenci brojeva. Iz ovog stava, stablo može biti definisano rekurentno: koren je najmanja vrednost sekvence, leva i desna pod-stabla su Dekartova stabla za pod-sekvence levo i desno od vrednosti korena. Prethodno definisane tri osobine jedinstveno definisu Dekartovo stablo.

Ako se sekvenca sadržanih brojeva ponavlja, Dekartovo stablo moze biti definisano pomoću utvrđivanja doslednog pravila za narušavanje-veza (na primer, određivanjem da se prvi od dva ista elementa smatra manjim od dva) pre nego što se primene prethodna pravila.

Efikasna konstrukcija[уреди]

Prvi metod[уреди]

Dekartovo stablo može biti konstruisano u linearnom vremenu od ulazne sekvence. Jedan metod je da jednostavno procesiramo vrednosti sekvence u levo-ka-desnom poretku, održavajući Dekartovo stablo od čvora koje smo procesirali, u strukturi koja nam dozvoljava nagore i nadole šetnje po stablu. Da bi procesirali svaku novu vrednost X, počnemo od čvora koji predstavlja vrednost pre X-a u sekvenci i pratimo put od ovog čvora do korena stabla dok ne nađemo vrednost Y koja je manja od vrednosti X-a.

Ovaj čvor Y je otac čvora X, i prethodno desno dete Y-a postaje novo levo dete X-a. Ukupno vreme za ovu proceduru je linearno, zato što vreme potrošeno za traženje oca Y-a od svakog novog čvora X može biti naplaćeno od strane broja čvorova koja su obrisana sa desnog dela put u stablu.

Drugi metod[уреди]

Alternativa ovog metoda je takođe algoritam zasnovan u linearnom vremenu koji je baziran na "sve najbliže manje vrednosti" problemu. U ulaznoj sekvenci, može se definisati levi komšija od vrednosti X-a da bude vrednost koja se pojavljuje pre samog X-a, manja je od X-a i bliža je X-u nego bilo koja druga manja vrednost. Desni komšija je definisan simetrično. Sekvenca levih komšija može biti nađena korišćenjem algoritma koji održava stek koji sadrži pod-sekvencu ulaza. Za svaku novu sekvencijalnu vrednost X, sa steka se skida vrednost sve dok on nije prazan ili dok je njegov top element manji od X-a i onda se X stavlja na stek. Levi komšija X-a je top element kada je X stavljen na stek. Sekvenca desnih komšija može biti nađena korišćenjem istog algoritma na obrnutu sekvencu. Otac X-a u Dekartovom stablu je ili levi komšija X-a ili desni komšija X-a, koji god postoji i ima veću vrednost. Leve i desne komšije mogu takođe biti konstruktovane efikasno korišćenjem paralelnih algoritama, tako da se ova formula može koristiti za pravljenje efikasnih paralelnih algoritama za konstrukciju Dekartovog stabla.

Korišćenje sortiranja[уреди]

Parovi uzastopnih sekvencnih vrednosti (prikazani kao debele crvene grane) koje drže sekvencnu vrednost 'X' (tamno-plava tačka). Cena sadržavanja 'X'-a u sortiranom redosledu kao rezultat Levcopoulos & Petersson algoritma je proporcionalna logaritmu od broja ovih parova.

Levcopoulos & Petersson (1989) su opisali algoritam za sortiranje baziran na Dekartovim stablima. Oni su opisali algoritam baziran na stablu sa najvećom vrednošću u korenu, ali se može modifikovati sa lakoćom da podržava i Dekartovo stablo sa pretpostavkom da je najmanja vrednost u korenu. Modifikovana verzija je opisana ispod.

Levcopoulos & Petersson algoritam može biti posmatran kao verzija selection sorta ili hip sorta koja održava prioritet reda sa kandidatom minima, i da u svakom koraku traži i briše najmanje vrednosti u ovom redu, pomerajući vrednosti na kraju izlaznog niza. U njihovom algoritmu, prioritet reda se sastoji samo od elemenata čiji je otac u Dekartovom stablu već bio pronađen i obrisan. Tako se algoritam sastoji od sledećih koraka:

  1. Konstruiši Dekartovo stablo za ulaznu sekvencu.
  2. Inicijalizuj red sa prioritetom, inicijalno da sadrži samo koren stabla.
  3. Dok red sa prioritetom nije prazan:
    • Nađi i obriši najmanju vrednost X u redu sa prioritetom.
    • Dodaj X na izlaznu sekvencu.
    • Dodaj sina Dekartovog stabla od X-a u red sa prioritetom.

Kako su Levcopoulos & Petersson pokazali, za ulazne sekvence koje su već skoro sortirane, veličina reda sa prioritetom će ostati mala što će dozvoliti ovom metodu da iskoristi prednost skoro sortiranog ulaza i da se izvrši brže. Specifično, složenost najgoreg mogućeg scenarija ovog algoritma je O(n log k), gde je K prosek svih vrednosti X u sekvenci od broja konstruisanih parova sekvencnih vrednosti koje drže vrednost X.

Istorija[уреди]

Dekartova stabla su predstavljena i imenovana od strane Vuillemin-a (1980). Ime potiče od Dekartovog koordinatnog sistema za ravan: U Vuilleminovoj verziji ove strukture, kao u dvo-dimenzionom algoritmu pretraživanja sa opsegom prodiskutovanim gore, Dekartovo stablo za set tački ima sortiran redosled tačaka po njihovim X-koordinatama kao njegova simetrična šetnja po stablu i ima svojstvo hipa prema Y-koordinatama tačaka. Gabow, Bentley & Tarjan (1984) i jos neki autori su pratili ovu definiciju u kojoj je Dekartovo stablo izvedeno iz sekvence. Ova promena generalizuje geometrična podešavanja da bi dozvolila sekvence ostalih stvari sem sortiranih X-koordinata i dozvolila Dekartovim stablima da budu primenjena na probleme koje nema geometričnu suštinu.

Reference[уреди]

  • Vuillemin, J. (1980). "A unifying look at data structures", Commun. ACM(New York, NY, USA: ACM).