Podatkovna struktura: R-drevo

Podatkovna struktura: R-drevo

Avtor: Petra Adamič

Učni cilji: Predstaviti podatkovno strukturo R-drevo.

Predstavitev

Podatkovna struktura R-drevo je uporabna za delo s prostorsko urejenimi večdimenzionalnimi podatki. Podatki so lahko na primer zemljevidi držav v geoloških bazah podatkov, avdio in video dokumenti. Sama struktura je zelo uporabna za GPS, saj poišče določene podatke v okviru nekega ranga.

R-drevo je ime dobilo po pravokotniku(ang. rectangle). Glavna ideja strukture je, da združimo najbližje objekte in jih omejimo z minimalnim pravokotnikom v višjem nivoju drevesa. Vsi podatki ležijo znotraj pravokotnika, zato ne moremo do objekta, če poizvedba ne seka tega pravokotnika.

R-drevo je uravnoteženo iskalno drevo (vsi listi so na istem nivoju).

Primera grafičnega prikaza strukture:

  • dvodimenzionalni primer
(http://www2.nauk.si/files/352/R-tree.png)
vir slike: Wikipedia
  • tridimenzionalni primer

    (http://www2.nauk.si/files/352/3dPrimer.png)
    vir slike: Wikipedia

Predstavitev

R-drevesa so primerna za hranjenje velike količine podatkov. Prav tako so zelo uporabna za baze, kjer so vozlišča poklicana, ko se jih potrebuje in ni potrebno, da je celo drevo zabeleženo v spominu.

Glavna ideja iskanja v strukturi je, da nam omejujoči pravokotniki povedo, če moramo iskati znotraj nekega poddrevesa. Na ta način večina vozlišč med iskanjem ni pregledana.

Glavna težava R-dreves je zgraditi učinkovito drevo, ki je uravnoteženo, hkrati pa morajo pravokotniki prekrivati čim manj praznega prostora in ne smejo prekrivati preveč podatkov.

Da ohranimo učinkovito drevo, vstavljamo elemente tako, da vedno vstavimo v poddrevo, kjer je potrebno najmanjše povečanje omejujočega področja.

R-drevesa ne zagotavljajo dobrega delovanja v najslabšem primeru, ampak na splošno dobro delujejo z resničnimi podatki.

Variacije R-dreves

Poleg R-dreves poznamo še nekaj variacij te strukture.

  • R* drevo – za indeksiranje prostorskih informacij. Podpira točkovne in prostorske podatke za nekoliko višjo ceno kot ostala r-drevesa
  • R+ drevo – metoda za gledanje podatkov lokacije, največkrat kot x,y koordinate in za lokacije na površju Zemlje
  • Hilbertovo R-drevo – indeks za večdimenzionalne objekte, črte, regije, 3-D objekti ali za večparametrične objekte
  • X-drevo – v računalništvu struktura, ki izvira iz R-drevesa, za shranjevanje podatkov v več dimenzijah

Lastnosti

Notranja vozlišča imajo med m in M naslednikov, kjer je m najmanjše število vpisov v vozlišče, M pa največje.

Podatki se hranijo izključno v listih, kjer vsak list vsebuje kazalec na nek objekt.

Vsako vozlišče, ki ni list, usmerja in kaže na naslednike.

Če vozlišče ni list, ima vsaj dva naslednika.


Postavitev podatkov

Podatki so shranjeni na nivojih, ki imajo lahko različno število vnosov (do nekega vnaprej def maksimuma in ponavadi večje od minimalne izpolnitve).

Vsak vnos v notranje vozlišče shrani dva kosa podatkov – pot do identifikacije naslednika in mejno polje vseh vnosov tega naslednika.

Listi shranijo podatke, ki so potrebni za naslednike (pogosto točko ali mejo polja, ki predstavljajo naslednika in zunanjo identifikacijo za naslednika).

Za točkovne podatke so lahko vnosi v liste kar točke same.

Za poligonske podatke shrani samo minimalno omejujoči pravokotnik tega poligona skupaj z unikatno identifikacijo v drevesu.

Primer strukture

Ogledali si bomo grafični prikaz strukture. (Slike povzete iz strani klik)

Mislimo si, da imamo neke podatke o študentih. Podano imamo, kateri semester obiskujejo in koliko točk so dosegli. To prikazuje spodnja slika:

(http://www2.nauk.si/files/352/shema1.png)

Naslednja slika nam prikazuje sestavo strukture R-drevesa. V našem primeru je minimalni vpis v vozlišče 2 in maksimalni vpis 5. To pomeni, da mora vsako vozlišče vsebovati vsaj 2 in največ 5 podatkov.

(http://www2.nauk.si/files/352/shema4.png)
prikaz strukture

Tukaj pa lahko vidimo razporeditev točk in posameznih pravokotnikov (ki predstavljajo poddrevesa) na grafu:

(http://www2.nauk.si/files/352/shema3.png)
graf strukture

Iskanje elementa

Vnos je iskalni pravokotnik. Iskanje se začne na vrhu drevesa. Vsako notranje vozlišče vsebuje nabor pravokotnikov in kazalcev na ustrezne naslednike. Vsak list vsebuje pravokotnik objektov (kazalci na objekte). Za vsak pravokotnik v vozlišču se je treba odločiti, če prekriva iskalni pravokotnik ali ne. Če ga prekriva, moramo pregledati tudi ustrezne naslednike. Pregledovanje poteka rekurzivno, dokler ne pregledamo vseh ustreznih naslednikov. Ko dosežemo liste, z iskalnim pravokotnikom pregledamo vsebujoče pravokotnike in njihove objekte. Če obstajajo in ležijo znotraj iskalnega pravokotnika, dodamo k rezultatu.

Iskanje začnemo v korenu in se pomikamo k naslednikom.

Algoritem:

T je koren R-drevesa.

Pregledamo vse zapise, katerih pravokotniki prekrivajo določen iskalni pravokotnik S.

Če T ni list, algoritem uporabimo za vsakega direktnega naslednika, ki se prekriva s S.

Če je T list, kot rezultat vrnemo vse zapise, ki se prekrivajo s S.

Primer iskanja

Recimo, da bi za naš primer radi poiskali vse študente, ki so vsaj v 6 semestru in so dosegli med 20 in 65 točk. Na sliki vidimo iskalni pravokotnik, ki je obarvan sivo. To je območje, ki nas zanima.

(http://www2.nauk.si/files/352/shema2.png)
primer iskalnega pravokotnika

filmček razlage

Na spodnji sliki se vidi, kateri elementi pridejo v poštev pri pregledovanju strukture. Vidimo, da nam ni potrebno pregledati vseh.

(http://www2.nauk.si/files/352/shemaIskanje.png)
obkrožimo elemente, ki smo jih pregledali

Končna rešitev je, da zahtevanim pogojem ustrezajo trije študenti: C, E in K.

Primer iskanja

V filmčku je prikazana razlaga za iskanje pravilne rešitve z iskalnim pravokotnikom:

Primer iskanja

filmček razlage

Na spodnji sliki se vidi, kateri elementi pridejo v poštev pri pregledovanju strukture. Vidimo, da nam ni potrebno pregledati vseh.

(http://www2.nauk.si/files/352/shemaIskanje.png)
obkrožimo elemente, ki smo jih pregledali

Končna rešitev je, da zahtevanim pogojem ustrezajo trije študenti: C, E in K.

Vstavljanje elementa

Za vstavitev objekta rekurzivno prehodimo drevo iz korena naprej. Na vsakem koraku preučimo vse pravokotnike trenutnega vozlišča in kandidata izberemo metodično, tako da izberemo pravokotnik, ki potrebuje najmanjše povečanje. Iskanje poteka po isti poti, dokler ne dosežemo lista. Če je list poln, se mora pred vstavljanjem razdeliti.

Novonastalo vozlišče je potrebno dodati temu nivoju, kar lahko povzroči prekoračitev, ki se lahko širi vse do korena. Če pride do tega, se ustvari nov koren in s tem se poveča višina drevesa.


Za vstavljanje poznamo tri algoritme:

  • Vstavi - glavni algoritem
  • IzberiList
  • UrediList

Moramo paziti, kako razcepiti vozlišče in kako urediti pravokotnike, saj se lahko čisto malo povečajo ali pa povsem spremenijo obliko.

Vstavljanje elementa

Izbira poddrevesa za vstavitev

Na vsakem nivoju se moramo odločiti v katero poddrevo je treba vstaviti nove podatke. Ko je podatkovni objekt cel vsebovan v enem samem pravokotniku, je izbira očitna. Ko pa imamo več možnosti ali pa pravokotnik potrebuje povečanje, ima izbira velik vpliv na učinkovitost drevesa. Ponavadi so objekti vstavljeni v poddrevo, ki potrebuje najmanjše povečanje pravokotnika (pri naprednejših R+ - drevesih so uporabljena drugačna metodična orodja).



Delitev prekoračenega vozlišča

Ker imamo za prerazporeditev vseh objektov v vozlišču na dva vozlišča eksponentno število možnosti, moramo najti najboljšo razdelitev. V navadnem R-drevesu poznamo kvadratno in linearno razdelitev.

V kvadratični razdelitvi algoritem najde par pravokotnikov, ki sta najslabša kombinacija, kar jih je lahko v enem vozlišču in jih postavimo kot začetnika, vsakega za svojo skupino. Nato najdemo vnose, ki imajo najmočnejšo prednost glede na eno skupino (v skladu s povečanjem območja) in pripišemo ta objekt tej skupini, dokler niso vsi objekti v neki skupini (zadoščanje minimalnemu polnilu). Obstaja tudi nekaj drugih strategij razdelitve, razlikujejo se predvsem glede na tip drevesa (variacijska drevesa).

Primer vstavljanja

Vstavljanje si bomo pogledali grafično na primeru od prej. (Primer in slike povzete po klik)

Mislimo si, da želimo na seznam dodati študenta Z, ki je v 10 semestru in je dosegel 65 točk.

Na spodnji sliki vidimo, kje se ta točka nahaja na grafu.

(http://www2.nauk.si/files/352/ShemaVstavi1.png)
dodamo točko Z na ustrezno mesto na grafu

Primer vstavljanja

Ko postavimo točko na graf, vidimo da je znotraj pravokotnika R1. Ker je najbližje pravokotniku R3 in ker R3 še ni dosegel maksimalnega števila elementov, ga povečamo tako, da je točka Z znotraj pravokotnika.

(http://www2.nauk.si/files/352/shemaVstavi2.png)
pravokotnik R3 se poveča, da sprejme točko Z

Na spodnji sliki vidimo, katere elemente smo pri vstavljanju upoštevali.

(http://www2.nauk.si/files/352/shemaVstavi3.png)
obkroženi so elementi, ki smo jih spreminjali

Zaključek

Struktura R-drevo je zelo uporabna podatkovna struktura za shranjevanje velike količine podatkov. Je pa tudi zelo zapletena struktura. V tej seminarski nalogi sem predstavila nekaj osnovnega o podatkovni strukturi. Opisala sem kako struktura nastane ter nekaj algoritmov. Prikazala sem iskanje in vstavljanje elementov na preprostem dvodimenzionalnem primeru.

Kviz

1. Ali lahko vstavljamo nove elemente v notranja vozlišča?

Da
Ne

Pravilno

Odgovor je pravilen, saj lahko elemente vstavljamo le v liste.

Zapri

Narobe

Odgovor ni pravilen, elemente lahko vstavljamo le v liste.

Zapri

Kviz

2. Iskanje elementa vedno poteka čez vsa poddrevesa in gre preko vseh elementov.

Da
Ne

Pravilno

Odgovor je pravilen, saj nam ni potrebno pregledati vseh elementov.

Zapri

Narobe

Odgovor je napačen, saj nam ni potrebno pregledati vseh elementov, ampak le naslednike poddreves, ki jih prekriva iskalni pravokotnik.

Zapri

Viri in literatura

0%
0%