R-drevo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Definicija R-drevesa

R-drevo je popolnoma uravnoteženo drevo in zelo uporabno pri delu s prostorsko urejenimi mnogodimenzionalnimi podatki. Vsi te podatki se hranijo v listih.
Z razvojem novih aplikacij v multimedijskem ali CAD sektorju je postalo vse težje obvladati tipe podatkov, kakršni so podobe, avdio in video dokumenti ali zemljevidi držav, ki jih lahko najdemo v geoloških bazah podatkov. Primer geološke aplikacije je najti vse kmete, ki imajo v lasti zemljo na določenem območju, na primer, če država želi zgraditi avtocesto, ki bo potekala na tem območju. Ker predhodne merilne metode (na primer B drevo) niso bile primerne za obvladovanje večdimenzionalnih podatkovnih predmetov, je bila potrebna nova, učinkovita in dinamična, na merilu zasnovana struktura za obvladovanje teh prostorskih podatkov. Leta 1984 je Antonin Guttman predstavil strukturo, kakršna je opisana zgoraj, imenuje se R drevo. Guttman je za iskanje, vstavljanje in brisanje podal algoritme in dokazal, da je R drevo zelo učinkovito.

Lastnosti R-dreves

Za R-drevesa je značilno:

   * Tipična lastnost, ki R-drevo loči od ostalih je, da imajo notranja vozlišča med m in M
naslednikov. m je najmanjše število vpisov v vozlišče in M je največje število vpisov
v vozlišče. * R-drevo je popolnoma uravnoteženo, to pomeni, da se vsi listi nahajajo na isti višini. * Podatki se hranijo izključno v listih. * Vsak končni list vsebuje kazalec na nek objekt. * Vsak ne-list vsebuje dve lastnosti: usmerja in kaže na naslednike. * Oče ima vsaj dva sinova, razen če je oče list.

Časovna zahtevnost

  • R-drevo ne zagotavlja neke dobre časovne zahtevnosti (boljše od O(n)), zaradi tega, ker se npr.v 2D pravokotniki prekrivajo.

Iskanje elementa

Iskanje v R-drevesu deluje podobno kot v B drevesu. Z iskanjem začnemo v korenu in se pomikamo proti sinovom. Lahko se zgodi, da se nekaj pravokotnikov, ki jih želimo poiskati prekriva (glej Preprost primer R-drevesa v 2D). Ker moramo obiskati vse te pravokotnike, ni mogoče zagotoviti nobene dobre časovne zahtevnosti (boljše od O(n)). Algoritem: Iskanje Naj bo T koren R-drevesa. Pregledamo vse zapise, katerih pravokotniki prekrivajo določen iskalni pravokotnik S.

   * Če T ni list, potem uporabi algoritem Iskanje za vsakega otroka, čigar koren je označen
s kazalcem nanj in ki se prekriva z S. * Če je T list, vrni vse zapise, ki se prekrivajo z S kot celota rezultatov.

Primer iskanja elementov v R-drevesu

Podan imam 2D primer. m in M sta najmanjša in največja količina vpisov v vozliščih. V našem primeru: m=2 in M=5. Definiran imam primer baze podatkov, kjer stolpec ime predstavlja ime študenta, semester nam pove, kateri semester študent trenutno obiskuje in točke, ki pa so seštevek vseh doseženih točk na univerzi.

Slika:Slika1.PNG

V tem primeru hočemo poiskati vse študente, ki so v šestem semestru ali višje in so pridobili med 20 in 65 točk. To je rumen pravokotnik S spodaj na sliki.

Slika:Slika2.PNG

Iz zgornjega grafa se nazorno vidi, da R1 prekriva iskani pravokotnik S in ne R2, zato iščemo v R1. V naslednjem koraku se R4 in R5 prekrivata z S. Sedaj v teh pravokotnikih najdemo rezultate, ki so znotraj iskalnega pravokotnika. Iz R4 dobimo C in iz R5 dobimo E in K, zato je celota rezultatov enaka množici {C, E, K}.

Slika:Slika3.PNG

Vstavljanje elementa


Če želim v bazo podatkov vstaviti nov vnos, potem moram R-drevesu dodati nov kazalec na vozlišče. To je tudi edina možnost, da R-drevo raste v višino. Namreč, če pride do presežka vozlišč, je potrebno to vozlišče razdeliti. V primeru, da je razcep potreben v korenu, bo višina narasla. Pri vstavljanju so potrebni trije algoritmi, če želimo da pravilno vstavimo element. Glavni algoritem je algoritem Vstavi, znotraj tega pa se uporabljata še dva algoritma, algoritema IzberList in UrediDrevo. Pri tem je potrebno biti zelo pazljiv že s tem, kako razcepiti vozlišče in potem ko vstavimo element, kako bomo urediti pravokotnike, ki se lahko samo malo povečajo, ali pa čisto spremenijo obliko. Več o tem si lahko preberete http://www.fmi.uni-passau.de/~neumann/proseminar/proseminar.pdf.

Primer vstavljanja elementa v R-drevo

Za primer vzamemo isto bazo podatkov kot zgoraj.
V tem primeru hočem vstaviti novega študenta (Q, 10, 65).

Slika:Slika6.PNG

Na koordinato (10, 65) želim vstaviti novega študenta Q. Algoritem IzberList vrne R1 kot prvo novo vozlišče. Potem je izbran R3 kot pravokotnik, kamor vstavimo novega študenta Q. Tako je študent Q vstavljen v R3. Potem pa se še izvede algoritem UrediDrevo, ki ponovno uredi(posodobi) pravokotnika R3 in R1.

Slika:Slika4.PNG
Slika:Slika5.PNG

Zaključek

Kot sem omenila že v povzetku, je podatkovna struktura R-drevo zelo uporabna v praksi, vendar pa pri tem potrebujemo kar veliko razumevanja. Ko sem želela bolj podrobno opisati algoritem Vstavljanje v R-drevo, se po nekaj korakih nisem več znašla. Zato je opisan bolj površno in bi tistemu, ki bi se rad poglobil v to, priporočala da si bolj obširno pogleda spodaj navedeno literaturo.

Glej tudi

Zunanje povezave

Osebna orodja