Intervalno drevo

Iz MaFiRaWiki

Intervalno drevo je podatkovna struktura, ki nam omogoča najti vse intervale iz dane množice, ki se prekrivajo z danim intervalom ali točko.

Intervalno drevo je urejeno drevo, ki vsebuje intervale. Če so intervali paroma disjunktni, jih lahko vstavimo v običajno iskalno drevo. Z intervalnimi drevesi pa lahko predstavimo tudi intervale, ki se prekrivajo.

Imamo množico intervalov [li,ri] za i = 1, \dots, n na številski osi, ki se lahko med seboj prekrivajo. Intervale predstavimo z dvojiškim drevesom, ki ima v vozliščih naslednje podatke:

  1. število v (običajno je to eno od krajišč intervala)
  2. seznam vseh intervalov, ki vsebujejo točko v, urejene po naraščajočih levih krajiščih.
  3. seznam vseh intervalov, ki vsebujejo točko v, urejene po padajočih desnih krajiščih.

Pri tem veljata:

  1. desna krajišča intervalov v levem poddrevesu so manjša od vrednosti korena v
  2. leva krajišča intervalov v desnem poddrevesu so večja od vrednosti korena v.

Običajno vzamemo za vrednost korena drevesa mediano krajišč pripadajočih intervalov.


(Od tu naprej je treba članek še popraviti.)

Iz tega sledi, da je to dvojiško iskalno drevo, kjer se za iskanje uporablja vrednost vozlišča oz. vrednost krajišč intervalov.

v - vozlišče
L - levo poddrevo
D - desno poddrevo

  1. Intervali za katere velja, da je r_i (desno krajišče intervala) manjše od vozlišča v, so celotno vsebovani v levem poddrevesu vozlišča.
  2. Image:PopolnoLevo.jpg

  3. Intervali za katere velja, da je l_i(levo krajišče intervala) večje od vozlišča v, so celotno vsebovani v desnem poddrevesu vozlišča v.
  4. Image:PopolnoDesno.jpg

  5. Intervali za katere velja l_i < = v.pt <= r_i, kjer je v.pt vrednost vozlišča, so vsebovani v vozlišču. To pomeni, da vsebujejo vrednost vozlišča (v.pt).
  6. Image:Vsebovan.jpg

V vozlišču hranimo:

  1. v.pt - vrednost vozlišča
  2. v.levo - seznam intervalov, ki vsebujejo vrednost vozlišča, urejeni po levem krajišču intervala
  3. v.desno - seznam intervalov, ki vsebujejo vrednost vozlišča, urejeni po desnem krajišču intervala

Vsebina

Lastnosti

  • Vsako vozlišče vsebuje od 1 do n intervalov.
  • Število vozlišč je O(n).
  • Višina drevesa je odvisna od izbranega korena.

Izbira korena

v je središče krajišč intervalov, ki ga uporabimo za koren intervalnega drevesa.
Recimo, da imamo množico intervalov, ki so prikazani na sliki (ker nimamo dostopa do slike le opomba: desno krajišče intervala d je 7) .

Image:Sredisce.jpg

  • Krajišča intervalov = {1, 2, 3, 4, 5, 6, 7}
  • Za središče krajišč intervalov izberemo 4, označimo kot v.pt (vrednost vozlišča).
  • Po izbrani sredini je višina drevesa O(log n).
  • Izbira sredine je možna le pri statični množici intervalov.

Primer konstrukcije intervalnega drevesa

Zasledila sem več različnih konstrukcij intervalnega drevesa:

  1. Vozlišča intervalnega drevesa predstavljajo krajišča intervalov. V vozliščih hranimo vrednosti krajišč intervalov, seznam intervalov urejen po levih krajiščih intervalov in seznam intervalov urejen po desnih krajiščih intervalov. Interval je lahko vsebovan natanko v enem vozlišču.
  2. Intervale razbijemo na elementarne intervale. Nato skonstruiramo intervalno drevo iz krajišč elementarnih intervalov. V vozliščih hranimo vrednosti krajišč elementarnih intervalov in seznam intervalov, ki vsebujejo vrednost krajišča. Ko interval vstavimo v vozlišče, interval zavzame vse vrednosti iz levega poddrevesa in vse vrednosti iz desnega poddrevesa. Tako intervalno drevo ima list za vsak elementarni interval. V listih ne hranimo nobene vrednosti. Listi predstavljajo elementarne intervale.
  3. Vsako vozlišče lahko vsebuje en interval in eno točko. Točka je maksimalna vrednost krajišč intervalov v poddrevesu ukoreninjenem v korenu oz. vozlišču. Drevo je urejeno po levih krajiščih intervalov.


Recimo, da imamo množico intervalov, ki jih vidimo na sliki (ker nimamo dostopa do slike le opomba: desno krajišče intervala d je 7).

Image:sredisce.jpg
Iz slike razberemo naslednje intervale.

Interval Levo krajišče Desno krajišče
a 1 3
b 4 6
c 2 4
d 5 7
e 1 2
f 3 6


Pri izbiri središča je razloženo kako izberemo središče intervalov, ki ga uporabimo za koren intervalnega drevesa.
Torej iz krajišč ={1, 2, 3, 4 , 5, 6, 7} izberemo za koren 4.

Skonstruiramo drevo, ki je na kratko opisano pod 1. točko.

1. Korak:
Za koren intervalnega drevesa smo si izbrali vrednost 4. Pogledamo kateri intervali imajo neprazen presek z vrednostjo 4. Najdene intervale vstavimo v dva seznama in sicer, v prvem bomo imeli intervale urejene po levem krajišču intervalov, v drugem seznamu bomo intervale imeli urejene po desnem krajišču intervalov. Kajti za drevo, ki je opisano pod prvo točko je značilno, da hrani v vozliščih vrednost krajišč intervalov in dva seznama.</p> Dobimo drevo s korenom, ki ima vrednost 4, dva seznama v vozlišču in levo in desno poddrevo, ki hranita intervale celotno vsebovane v levem oz. desnem poddrevesu. To so taki intervali, kjer je vrednost desnega krajišča manjše od vrednosti korena intervalnega drevesa (levo poddrevo) oz. kjer je vrednost levega krajišča večja od vrednosti korena intervalnega drevesa (desno poddrevo).
Image:Konstr1.JPG

2. Korak:
Postopek iz prvega koraka ponovimo na levem poddrevesu in desnem poddrevesu.

V levem poddrevesu imamo intervale a[1, 3] in e[1, 2]. Naprej izberemo središče med krajišči intervalov, ki bo predstavljalo koren levega poddrevesa. Izberemo krajišče z vrednostjo 2, ki predstavlja središče krajišč intervalov a in e.

V desnem poddrevesu imamo samo en interval, in sicer d[5, 7]. Izberemo središče, in sicer 7. Ne moremo izbrati 6, ker 6 ni krajišče intervala. V vozliščih hranimo samo krajišča intervalov, ne pa tudi vrednosti, ki jih intervali vsebujejo.

Naslednja naloga je pogledati kateri intervali v poddrevesih imajo neprazen presek z vrednostjo, ki smo si jo izbrali za koren poddrevesa tako kot levega tudi desnega. Pogledati moramo tudi kateri intervali so celotno vsebovani v levem poddrevesu vozlišča, ki smo si ga izbrali za koren poddrevesa in kateri intervali so celotno vsebovani v desnem poddrevesu vozlišča, ki smo si ga izbrali za koren desnega poddrevesa.

V levem poddrevesu vsebujeta vrednost korena poddrevesa oz. imata neprazen presek z vrednostjo korena poddrevesa intervala a[1, 3] in e[1, 2]. V vozlišču hranimo tudi seznama urejena po levem krajišču intervalov in desnem krajišču intervalov.

V desnem poddrevesu vsebuje vrednost korena poddrevesa oz. ima neprazen presek z vrednostjo korena poddrevesa samo en interval, in sicer d[5, 7]. Seznama, ki jih vsebuje vozlišče sta {d} in {d}.

Dobimo naslednje intervalno drevo:

Image:Konstr2.JPG

Iskanje intervalov, ki prekrivajo dani interval oz. točko

Imamo intervale:

  • A [1,3]
  • B [4,6]
  • C [2,4]
  • D [5,7]
  • E [1,2]
  • F [3,6]

Iz intervalov sestavimo intervalno drevo. Pred tem, pa izberemo koren kot je to opisano pri izbiri središča.
V našem primeru bo to 4.
Ne pozabimo, da v vozlišču hranimo vrednost in dva seznama.
Prvi seznam so intervali vsebovani v vozlišču urejeni po levih krajiščih intervalov.
Drugi seznam so intervali vsebovani v vozlišču urejeni po desnih krajiščih intervalov.

Dobimo intervalno drevo.

Image:Konstr2.JPG
Intervalna drevesa uporabljamo zato, da ugotovimo kateri intervali v intervalnem drevesu prekrivajo dani intervali oz. točko.

1. Primer: izberemo si interval [2,5]
To je primer, ko iščemo intervale v levem in desnem poddrevesu, saj je vrednost korena drevesa vsebovana v danem intervalu. Poiskati moramo intervale, ki prekrivajo dani interval oz. poiskati moramo intervale, ki imajo z danim intervalom neprazen presek.

Najprej preberemo intervale, ki so vsebovani v korenu. Dobimo prvi del seznama intervalov, ki prekrivajo vhodni interval.
To so: b, c in f.

Nato se spustimo v levo poddrevo do vozlišča z vrednostjo 2. Vrednost levega krajišča danega intervala je enaka vrednosti vozlišča. Sledi, da ima dani interval neprazen presek z intervali, ki so vsebovani v vozlišču, zato si zapomnimo intervale. Dobili smo drugo množico intervalov, ki prekrivajo oz. imajo neprazen presek z danim intervalom.

Nato se vrnemo do korena in se spustimo v desno poddrevo do vozlišča z vrednostjo 7. Vrednost 7 je večja od desnega krajišča danega intervala, zato pogledamo seznam intervalov urejen po levih krajiščih in njihove vrednosti levih krajišč. V našem primeru imamo samo en interval in sicer d[5, 7]. Vrednost levega krajišča intervala d je enaka vrednosti desnega krajišča danega intervala, zato ima interval d neprazen presek z danim intervalom. Dobili smo še tretjo množico intervalov. Če vse tri množice združimo skupaj dobimo vse intervale, ki imajo neprazen presek z danim intervalom.

  • A={b, c, f}
  • B={a, e}
  • C={d}
A U B U C = {a, b, c, d, e, f}
Image:iskanje01.jpg

Torej intervali, ki prekrivajo dani interval so: a, b, c, d, e in f.

2. Primer: izberemo interval [1,3]
Vrednost desnega krajišča intervala je manjša od vrednosti korena intervalnega drevesa, zato bomo intervale iskali v levem poddrevesu. Pred tem, pa si poglejmo leva krajišča intervalov iz seznama intervalov urejenih po levih krajiščih, ki so vsebovana v korenu drevesa, saj so lahko vrednosti levih krajišč vsebovane v danem intervalu.
Intervali v seznamu urejenem po levih krajiščih intervalov so: c[2, 4],f[3, 6] in b[4, 6].
Interval c ima neprazen presek z danim intervalom, ker je vrednost levega krajišča vsebovana v danem intervalu [1, 3].
Interval f tudi prekriva dani interval, ker je vrednost levega krajišča intervala enaka vrednosti desnemu krajišču danega intervala.
Interval b pa ne prekriva danega intervala, ker je vrednost njegovega levega krajišča večja od vrednosti desnega krajišča danega intervala.
Dobimo prvo množico intervalov, ki prekrivajo dani interval. Nato se spustimo v levo poddrevo do vozlišča z vrednostjo 2. Vrednost 2 je vsebovana v danem intervalu. Dobimo drugo množico intervalov, ki prekrivajo dani interval.

  • A={c, f}
  • B={a, e}

A U B = {a, c, e, f}
Image:iskanje02.jpg

Torej intervali, ki prekrivajo dani interval so: a, c, e in f.

3. Primer: izberemo interval [5,7]
Vrednost levega krajišča danega intervala je večja od vrednosti korena intervalnega drevesa, zato bomo intervale iskali v desnem poddrevesu. Preden se spustimo v desno poddrevo si poglejmo seznam intervalov urejenih po desnih krajiščih intervalov. Pogledamo, če so vrednosti desnih krajišč intervalov vsebovane v danem intervalu oz. imajo z danim intervalom neprazen presek.
Intervali v seznamu urejenem po desnih krajiščih intervalov so: c[2, 4], b[4, 6] in f[3, 6].

Interval c ima prazen presek z danim intervalom, ker je vrednost njegovega desnega krajišča manjše od vrednosti levega krajišča danega intervala.
Interval b ima neprazen presek z danim intervalom, ker je vrednost njegovega desnega krajišča vsebovana v danem intervalu.
Interval f ima neprazen presek z danim intervalom, ker je vrednost njegovega desnega krajišča vsebovana v danem intervalu.
Dobili smo prvo množico intervalov, ki prekrivajo dani intervali, in sicer A = {b, f}.

Nato se spustimo v desno poddrevo do vozlišča z vrednostjo 7. Vrednost 7 je vsebovana v danem intervalu.
Dobili smo drugo množico intervalov, ki imajo neprazen presek z danim intervalom. V našem primeru je to samo en interval, B = {d}. Če združimo množici skupaj dobimo seznam vseh intervalov, ki imajo neprazen presek z danim intervalom.

  • A={b, f}
  • B={d}

A U B = {b, d, f}
Image:iskanje03.jpg

Torej intervali, ki prekrivajo dani interval so: b, d in f.

4. Primer: izberemo točko 3
Tako kot pri zgornjih primerih se spustimo v globino in sicer v levo poddrevo, saj je vrednost točke manjša od vrednosti korena. Preden se spustimo si poglejmo seznam intervalov urejenih po levih krajiščih. Pogledamo, če so vrednosti levih krajišč manjše oz. enake dani točki.
Intervali v seznamu urejenem po levih krajiščih intervalov so: c[2, 4],f[3, 6] in b[4, 6].

Interval c ima neprazen presek z danim intervalom, ker je vrednost točke večja od vrednosti levega krajišča intervala.
Pogledamo še desno krajišče intervala in vidimo, da je vrednost točke manjša od vrednosti desnega krajišča intervala. Sledi, da ima dana točka neprazen presek z danim intervalom.
Interval f ima neprazen presek z dano točko, ker je vrednost njegovega levega krajišča enaka vrednosti dane točke.
Interval b ima prazen presek z dano točko, ker je vrednost njegovega levega krajišča večja od vrednosti dane točke.
Spustimo se do vozlišča, ki ima vrednost 2. Ker je vrednost dane točke večja od vrednosti vozlišča si pogledamo seznam intervalov urejenih po desnih krajiščih.
Dano točko primerjamo z vrednostmi desnih krajišč intervalov.
Vrednost desnega krajišča intervala e[1, 2] je manjša od vrednosti dane točke, zato ima dana točka prazen presek z intervalom e.
Vrednost desnega krajišča intervala a[1, 3] je enaka vrednosti dane točke, zato ima dana točka neprazen presek z intervaloma.

Dobili smo dve množici intervalov, ki prekrivajo dano točko to sta:
  • A = {c, f}
  • B = {a}

A U B = {a, c, f}
Torej intervali, ki prekrivajo dano točko so a, c in f.

Osebna orodja