Interval stabla

U računarstvu, interval stabla je uređeno stablo strukture podataka koje sadrži intervale. Preciznije, dozvoljava da efikasno nađe sve intervale koji se preklapaju sa bilo kojim datim intervalima ili tačkama. Često se koristi za uokvireno ispitivanje, na primer, da bi našli sve puteve na kompjuterizovanoj mapi unutar pravougaonog nevezanog prozora, ili da bi našli sve vidljive elemente unutar trodimenzionalne scene. Slična struktura podataka je segmentno stablo.

Trivijalno rešenje je posetiti svaki interval i testirati da li preseca datu tačku ili interval, što zahteva Θ(n) vremena, gde je n broj intervaala u skupu. Kako se pitanje može vratiti na sve intervale, na primer ako ispitan je veliki interval koji preseca sve intervale unutar skupa, ovo je asimptotski optimalno; kako god, možemo i bolje imajući u vidu izlazno-osetljive algoritme, gde je dužina trajanja izražena u terminu m, broj intervala proizveden ispitivanjem. Interval stabla je dinamičan, drugim rečima, on dozvoljavaju umetanje i brisanje intervala. On sadrže vreme ispitivanja O(log n) dok je predprocesorsko vreme da kostruiše strukturu podataka O(n log n) (ali prostorno je O(n)).

Naivni pristup

U prostom slučaju, intervali se ne prepliću i mogu biti umetnuti u prosto binarno stablo pretrage i ispitani u O(log n) vremenu. Kako god, sa proizvoljnim preplitanjem intervala, ne postoji šansa porediti dva intervala za umetanje u stablo pošto je uređivanje sortirano početnim tačkama ili krajnjim tačkama koje mogu biti drugačije. Naivni pristup može biti da se naprave dva paralelna stabla, jedno uređeno početnim tačkama, drugo krajnjim tačkama svakog intervala. Ovo dozvoljava odbacivanje pola stabla u O(log n) vremenu, ali rezultat mora biti spajanje, koje zahteva O(n) vreme. Ovo nam daje ispitanost u O(n + log n) = O(n), što nije bolje od primitivne-sile.

Interval stabla rešava ovaj problem. Ovaj članak opisuje dva alternativna dizajna za interval stabala, zavani centralizovan interval stabla i povećano stablo.

Centralizovan interval stabla

Upiti zahtevaju O(log n + m) vremena, sa n totalnim brojem intervala i m brojem prijavljenih rezultata. Konstrukcija zahteva O(n log n) vremena, i skladištenje O(n) prostora.

Konstrukcija

Dat je set od n intervala na brojnoj liniji, a mi želimo da konstruišemo strukturu podataka tako da možemo efikasno da vratimo sve preklapajuće intervale ili tačke.

Počinjemo uzimanjem celog dometa svih intervala i delimo ga na pola u x_centru (u praksi, x_centar bi trebalo da je biran da sačuva stablo relativno balansiranim). Ovo daje 3 seta intervala, oni skroz levo od x_centra koje zovemo S_levo, oni skroz desno od x_centra koje zovemo S_desno, i oni koji se preklapaju u x_centar koje zovemo S_centar.

Intervali u S_levo i S_desno su rekurzivno podeljeni na isti način sve dok ne bude više intervala levo.

Intervali u S_centru koji preklapaju centralnu tačku su sačuvani u odvojenoj strukturi podataka povezani sa čvorom z intervalu stabla. Ova struktura podataka se satoji od dve liste, jedna sadrži sve intervale sortirane početnim tačkama, druga sve intervale sortirane krajnjim tačkama.

Rezultat je trečestepeno stablo sa svakim čvvorom sortiranim:

• Centralnom tačkom
• Tačkom do čvora koji sadrži sve intervale levo od centralne tačke
• Tačkom do čvora koji sadrži sve intervale desno od centralne tačke
• Sve intervale koji preklapaju centralnu tačku sortiranu početnim tačkama
• Sve intervale koji preklapaju centralnu tačku sortiranu krajnjim tačkama

Ukrštanje

Dato strukturom podataka kostruisanom u pasusu iznad, dobijamo upite koji se sadrže od domena i tačaka, i vraća sve domene u originalnu kolekciju ulaznih preklapanja.

Sa intervalom

Prvo, možemo da smanjimo slučaj gde je interval R dat kao ulaz sličnom slučaju kao što je data za ulaz jedna tačka. Prvo nađemo sve domene sa početnim ili krajnjim tačkama unutar ulaznog intervala R koristeći odvojeno konstruisana stabla. U jedno-dimenzionalnom slučaju, možemo da koristimo jednostavno stablo koje sadrži sve početne i krajnje tačke intervala, svaku sa pokazivačem koji odgovara svom intervalu.

Binarna pretraga u O(log n) vremenu za početak i kraj R otkriva minimum i maksimum tačaka. Svaka tačka u ovom domenu referencira interval koji se preklapa sa našim domenom i ubacuje se u listu rezultata. Mora se obratiti pažnja na dupliranje, kako interval može da počne i da se završi unutar R. Ovo može biti urađeno koristeći binarni fleg za svaki interval da bi označili da li jeste ili nije ubačen u rezultat.

Intervali koji nisu uključeni su oni koji preklapaju R koji nemaju krajnje tačke unutar R, drugim rečima, intervali koji ga zatvaraju. Da bi našli ove, biramo bilo koje tačke unutar R i koristimo algoritam ispod da nađemo sve intervale koji se ukrštaju u toj tački (ponovo, pazeći na dupliranje).

Sa tačkama

Zadatak je da nađemo sve intervale u stablu koji preklapaju datu tačku x. Drvo je propraćeno sa sličnim rekurzivnim algoritmom kao što bi bilo koršćeno obilaženje tradicionalnog binarnog stabla, ali sa dodatnim dozvoljavanjem preklapanja itervala u "centru" tačke svakog čvora.

Za svaki čvor stabla, x se poredi sa x_centrom, središna tačka se koristi u konstrukciji čvora iznad. Ako x je manja od x_center, krajnja leva grupa intervala, S_levo, se uzimaju u obzir. Ako x je veće od x_centra, krajnji desni intervali, S_desno, se uzimaju u obzir.

Kako je svaki čvor obrađen dok mi obilazimo stablo od korena do lista, domen u njemu je S_cenatr obrađen. Ako x je manje od x_centra, znamo da svi intervali u S_centru se završavaju posle x, i da takođe ne mogu da se preklapaju u x_centru. Tako da, treba da nađemo samo one intervale u S_centru koji počinju pre x. Možemo da konsultujemo listu od S_centra koju smo već napravili. S obzirom da ovde brinemo samo o početnim intervalima, možemo da konsultujemo listu sortiranu od početka. I da nađemo najbliži broj ne veći od x u ovoj listi. Svi domeni od početka liste do nađene tačke preklapanja x zato što počinju od x i završavaju se posle x. Možemo jednostavno da počnemo da enumerišemo intervale u listi dok krajnja vrednost ne pređe x.

Isto tako, ako x je veće od x_centra, znamo da svi intervali u S_centru moraju da počnu pre x, nalazimo intervale koji se završavaju posle x koristeći listu sortiranu krajnjim intervalima.

Ako x tačno odgovara x_centru, svi intervali u S_centru mogu biti dodati u rezultate bez daljeg obrađivanja i obilazak stabla može prestati.

Više dimenzije

Interval stabla strukture podataka može biti generalizovan na više dimenzije N sa identičnim ispitivanjem i kostrukcionim vremenom i O(n log n) prostorom.

Prvo, prostorno stablo dimenzije N je napravljeno tako da dozvoljava efikasan povraćaj svih intervala sa početnim i krajnjim tačkama unutar regiona upita R. Kada su odgovarajući dometi nađeni, jedino što je ostalo su dometi koji ograđuju domet u nekoj dimenziji. Da bismo našli ova preklapanja, N interval stabla je kreiran, i jedan otac presecajući R je upit za svaki. Na primer, u dve dimenzije, dno kvadrata R bio bi ispitan protiv intervala stabla konstrukcije za horizontalnog oca. Isto tako, bio bi ispitan protiv intervala stabla konstrukcije za vertikalnog oca.

Svakom intervalu stabla takođe treba dopuna za više dimenzije. Kod svakog čvora u obilaženju stabla, x je poređeno sa S_centrom da bi našli preklapanja. Umesto dve sortirane liste tačaka kao što je korišćeno u jedno-dimenzionalnim slučajevima, domen stabla je konstruisan. Ovo mogućava efikasan povratak svih tačaka u S_centru koji preklapa region R.

Brisanje

Ako posle brisanja intervala iz stabla, čvor koji sadrži taj interval više ne, onda može biti obrisan iz stabla. Ovo je mnogo složenije nego brisanje kod normalnog binarnog stabla.

Interval može da preklapa centralnu tačku nekoliko čvorova u stablu. Pošto svaki čvor sadrži interval koji je preklapa, sa svim intervalima skroz levo od centra tačke u levom podstablu, slično i za desno pod stablo, prati da svaki interval je sortiran u čvoru najbližem korenu iz grupe čvorova kome je centralna tačka preklapanje.

Normalno brisanje u binarnom stabu uključuje unapređivanje čvora dalje od korena do pozicije obrisanog čvora. Kao rezultat ovog unapređenja, neki čvorovi koji su bili iznad unapređenog čvora postaće njegovi potomci; neophodno je tražiti ove čvorove za intervale koji takođe preklapaju unapređen čvor, i pomera te intervale u unapređeni čvor. kao posledica, ovo može rezultovati praznim čvorom, koji mora biti obrisan, prateći isti algoritam.

Balansiranje

Iste problem koji prati brisanje takođe utiče na rotiranje; rotiranje mora sačuvati invarijante u kojima su intervali skladišteni što je bliže moguće korenu.

Povećano stablo

Još jedan način da se prezentuju intervali je da se opišu u Cormen et al. 2001, Section 14.3: Interval trees. str. 311-317.

I umetanje i brisanje zahteva O(log n) vremena, sa n totalnim brojem intervala.

Koristeći jednostavno uređeno stablo, na primer, binarno stablo pretrage ili samobalansirajuće binarno stablo pretrage, gde je stablo uređeno sa 'slabom' vrednošću intervala, i sa dodatnom anotacijom je dodato svakom čvoru zabeležavanje maksimalne vrednosti podstabla. Ovaj atribut je jednostavan za održavanje samo sa O(h) koraka tokom svakog dodatnog ili uklonjenog čvora, gde h je visina dodatog ili ukonjenog čvora u stablu, unapređujući sve pretke čvora odozdo na gore. Dodatno, rotacija stabla korišćena tokom umetanja brisanja može da zahteva dorađivanje visoke vrednost zadešenih čvorova.

Sad, poznato je da dva intervala A i B se preklapaju samo kad oba A.manje ≤ B.veće i A.veće ≥ B.manje. Kada pretražujemo stablo za čvorove koji se preklapaju sa datim intervalima, mozete odma preskočiti:

• svi čvorovi desno od čvorova čija je donja vrednost prošla kraj datog intervala.
• svi čvorovi koji imaju svoj maksimalnu 'visoku' vredost ispod početka datog intervala.

Totalni red može biti definisan na intervalima uređujuči ih prvo prema njihovoj 'niskoj' vrednosti i konačni i njihovoj „visokoj” vrednosti. Ovo uređivanje može biti korišćeno da spreči dupliranje intervala od umetanja u stablo u O(log n) vremenu, umesto O(k + log n) vreme potrebo za pronalaženje duplikata ako k intervali preklapaju novi interval.

Java Primer: Dodavanje novih intervala u stablo

Ključ svakog čvora je sam interval i vrednost svakog čvora je krajnja tačka intervala:

 public void add(Interval i) {
     put(i, i.getEnd());
 }

Java Primer: Pretraga tački ili intervala u stablu

Da bi tražili intervale, petamo po stablu, izostavljajući one grane koje ne mogu da sadrže ono što se traži. Jednostavan način je da se traži tačka:

 // Нађи све интервале који садрже "p", почећи од
 // чвора "n" и додајући подударајуће интервале у листу "result"
 public void search(IntervalNode n, Point p, List<Interval> result) {
     // Don't search nodes that don't exist
     if (n == null)
         return;
 
     // Ако p је десно од најдешњије тачке било ког интервала
     // у овом чвору и свој деци, неће бити подударања.
     if (p.compareTo(n.getValue()) > 0)
         return;
 
     // Претражи десну децу
     if (n.getLeft() != null)
         search(IntervalNode (n.getLeft()), p, result);
 
     // Провери овај чвор
     if (n.getKey().contains(p))
         result.add(n.getKey());
 
     // Ако p је лево од почетка интервала,
     // онда не може бити ни у једној деци десно.
     if (p.compareTo(n.getKey().getStart()) < 0)
         return;
 
     // Иначе, претражи десну децу
     if (n.getRight() != null)
         search(IntervalNode (n.getRight()), p, result);
 }

Kod za traženje intervala je potpuno isti samo ima proveru u sredini:

 // Провери овај чвор
 if (n.getKey().overlapsWith(i))
     result.add (n.getKey());

overlapsWith() je definisano kao:

 public boolean overlapsWith(Interval other) {
     return start.compareTo(other.getEnd()) <= 0 &&
            end.compareTo(other.getStart()) >= 0;
 }

Veće dimenzije

Ovo može biti produženo na veće dimenzije kružeći kroz dimenzije svakog nivoa stabla. Na primer, za dve dimenzije, neparni nivoi stabla mogu da sadrže domen za x koordinate, parni nivoi stabla mogu da sadrže domen za y koordinate. Kako god, nije sasvim očigledno da će logika rotacije da bude produžena za takve slučajeve da bi zadržala stablo balansiranim.

Mnogo jednostavnije rešenje je da se koriste umetnuti intervali stabla. Prvo, kreiraj stablo koristeći domen za y koordinate. Sad, za svaki čvor stabla, dodaj još jedan interval na x domene, za sve elemente čiji y domen preseca čvorove je y domen.

Prednost ovog rešenja je ta da može biti produženo na proizvoljnu dimenziju koristeći isti bazni kod.

U početku, cena za dodatna stabla bi izgledala previsokom ali to obično nije slučaj. Sa rešenjem gore, treba ti samo jedan čvor po x koordinati, cena je onda ista u oba slučaja. Jedina razlika je ta da ti treba dodatno struktuirano stablo po vertikali intervala. Ova struktura je obično jako mala.

Medijski/dužinski orijentisano stablo

Slično Uvećanom stablu, ali na simetričan način, gde Binarno stablo pretrage je uređeno Medijskim tačkama intervala. I postoji Maksimum-orijentisanih Binarni hipova u svakom čvoru, uređeno po dužini intervala (ili pola dužine). Takođe smeštamo minimalnu moguću vrednost podstabla u svakom čvoru, dodatno maksimalnoj mogućoj vrednosti (zato je simetrično).

Test preklapanja

Koristeći samo početne i krajnje vrednosti dva intervala $\left(a_{i},b_{i}\right)$, za $i=0,1$, test preklapanja može biti izveden:

$a_{0}\leqslant a_{1}<b_{0}$    OR    $a_{0}<b_{1}\leqslant b_{0}$    OR    $a_{1}\leqslant a_{0}<b_{1}$    OR    $a_{1}<b_{0}\leqslant b_{1}$

Ali sa definisanjem:

$m_{i}={\frac {a_{i}+b_{i}}{2}}$

$d_{i}={\frac {b_{i}-a_{i}}{2}}$

Test preklapanja je sličan:

$\left|m_{1}-m_{0}\right|<d_{0}+d_{1}$

Dodavanje intervala

Dodavanje novih intervala u stabo je isto kao BSP, samo koristimo medijusku vrednost kao ključ, i kad nađemo/napravimo čvor da stavimo interval. Trebalo bi da izbacimo $d_{i}$ do Binarnog hipa povezanog sa čvorom i da unapredimo minimalne i maksimalne moguće vrednosti povezane sa svim višim čvorovima.

Traženje svih preklapajućih intervala

Da koristimo $a_{q},b_{q},m_{q},d_{q}$ za upit intervala, i $M_{n}$ za ključ čvora (u poređenju sa $m_{i}$ od intervala)

Krećući sa korenom, u svakom čvoru, prvo proverimo da li je moguće da se naš ispitivan interval preklapa sa čvorom podstabla koristeći minimalne i maksimalne vrednosti čvora (ako ne, ne idemo dalje za ovaj čvor).

Onda izračunamo $\min \left\{d_{i}\right\}$ za interval unutar ovog čvora (ne za njegovu decu) da li se preklapa sa ispitanim intervalom (znajući $m_{i}=M_{n}$):

$\min \left\{d_{i}\right\}=\left|m_{q}-M_{n}\right|-d_{q}$ I izvodeći ispitivanje Binarni hip za $d_{i}$ veći od $\min \left\{d_{i}\right\}$

Onda prođemo kroz oba leva i desna deteta čvora, radeći isto. U najgorem slučaju, moramo da skeniramo sve čvorove BSP-a, ali pošto Binarni hip ispituje optimum, nema mnogo brige.

Za ovaj algoritam je očekivano da bude brži od tradicionalnog Intervala stabla (Uvećano stablo) u pretragama, dodavanje je samo nešto sporije (uređenje raste je isto).

Literatura

• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry, Second Revised Edition. Springer-Verlag 2000. Section 10.1: Interval Trees. str. 212–217.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd izd.), MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3 
• Franco P. Preparata and Michael Ian Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985

Spoljašnje veze

• CGAL : Computational Geometry Algorithms Library in C++ contains a robust implementation of Range Trees
• Interval Tree (an augmented self balancing avl tree implementation)