Kartezijansko stablo

Sekvenca brojeva i Kartezijansko stablo izvedeno od njih.

Kartezijansko 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. Kartezijanska stabla se koriste i u problemima binarne pretrage radi definisanja struktura podataka kao što su treap, randomizovano binarno stablo pretrage. Kartezijansko 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

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

1. Kartezijansko 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 Kartezijanska stabla za pod-sekvence levo i desno od vrednosti korena. Prethodno definisane tri osobine jedinstveno definisu Kartezijansko stablo.

Ako se sekvenca sadržanih brojeva ponavlja, Kartezijansko 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

Kartezijansko 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 Kartezijansko 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 Kartezijanskom 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 Kartezijanskog 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 Kartezijanskim 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 Kartezijansko 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 Kartezijanskom stablu već bio pronađen i obrisan. Tako se algoritam sastoji od sledećih koraka:

1. Konstruiši Kartezijansko 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 Kartezijanskog 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

Kartezijanska stabla su predstavljena i imenovana od strane Vuillemin-a (1980). Ime potiče od Kartezijanskog koordinatnog sistema za ravan: U Vuilleminovoj verziji ove strukture, kao u dvo-dimenzionom algoritmu pretraživanja sa opsegom prodiskutovanim gore, Kartezijansko 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 Kartezijansko stablo izvedeno iz sekvence. Ova promena generalizuje geometrična podešavanja da bi dozvolila sekvence ostalih stvari sem sortiranih X-koordinata i dozvolila Kartezijanskim 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).