Drevo (podatkovna struktura)

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Drevo je nelinearna podatkovna struktura. Osnovni elementi v drevesu so vozlišča. Vsako vozlišče ima lahko več naslednikov, vendar kvečjemu enega predhodnika. Koren je vrhnje vozlišče, edino vozlišče v drevesu brez prednika.

Rekurzivna definicija drevesa pravi:
Drevo je končna množica vozlišč, od katerih je eno koren, ostala vozlišča pa razpadejo na n >= 0 disjunktnih množic T1,..., Tn. Te množice(poddrevesa) so tudi drevesa.

Shema drevesa:

image:Shema drevesa.jpg


Vsebina

Pojmi, povezani s podatkovno strukturo drevo

  • Vozlišče: je osnovni element drevesa. Vsebuje podatek in informacijo o iz njega izhajajočih poddrevesih. Ima lahko več potomcev, vendar največ enega prednika.

image:Vozlisce.JPG


  • Potomec vozlišča: poljubno vozlišče poddrevesa, ki izhaja iz njegovega prednika.

image:PotomciVozlisca.jpg


  • Oče ali prednik: 1 je oče vozliščema 2 in 3. 2 je oče vozliščema 4 in 5. 3 je oče vozliščema 6 in 7. Koren drevesa je edino vozlišče brez očeta (v našem primeru je koren drevesa 1).

image:Oce.jpg


  • Sin ali naslednik: je koren poddrevesa, ki izhaja iz njegovega očeta.

image:Sin.jpg


  • Stopnja vozlišča: je število poddreves, ki izhajajo iz vozlišča.

image:StopnjaVozlisca.jpg


  • Stopnja drevesa: je maksimalna stopnja vozlišč. Drevo na prejšnji sliki ima stopnjo 3.


  • List ali končno vozlišče: je vozlišče, ki nima sinov.

image:List.jpg


  • Notranja vozlišča: so vsa vozlišča, razen listov.

image:NotranjeVozlisce.jpg


  • Nivo vozlišča: če ima oče nivo n, ima sin nivo n + 1. Koren ima nivo 1, njegovi sinovi 2, sinovi sinov 3, itd.

image:NivoVozlisca.jpg


  • Višina drevesa: je enaka največjemu nivoju vozlišča v drevesu.

image:Visina.jpg


  • Urejeno drevo: je drevo, pri katerem je vrstni red poddreves (sinov) pomemben.Pri tem nas urejenost podatkov v vouzliščih ne zanima.


  • Izrojeno drevo: je drevo, pri katerem ima vsako vozlišče (razen lista) le enega sina.

image:IzrojenoDrevo.jpg


  • Polno drevo stopnje k: je drevo, kjer ima vsako vozlišče (razen listov) natanko k sinov. Vsi listi so na istem nivoju.

image:PolnoDrevo.jpg


  • Prazno drevo: je drevo brez vozlišč.


  • Gozd: množica disjunktnih dreves.

image:Gozd.jpg

Predstavitev dreves

Dreves lahko predstavimo na veliko načinov. Spodaj je naštetih le nekaj.

  • Klasična predstavitev drevesa:
 image:KlasicnaPred.jpg
  • Predstavitev drevesa z gnezdenjem podatkov:
 +----------- šport -----------+
 |            +---- ples ----+ |
 | smučanje   |balet   valček| |
 |            +--------------+ |
 +-----------------------------+
  • Predstavitev drevesa z diagramom, ki vsebuje smiselne zamike:
 Slika:Diagram.jpg
  • Predstavitev drevesa s tabelo:

Pri tej predstavitvi podatke iz drevesa hranimo v tabeli. Samo strukturo drevesa določajo indeksi elementov.
Razlaga prevedbe drevesa na tabelo za dvojiška drevesa:
Koren je v tabeli na mestu 1. Če je vozlišče na i-tem mestu v tabeli, potem za njegovega očeta in oba sinova veljajo naslednje formule:

            oče(i) = i/2
            levi sin(i) = 2*i
            desni sin(i) = 2*i + 1

 image:KlasicnaPred.jpg
 prevedemo na tabelo:
+----------------------------------------+ |šport|smučanje|ples| - | - |balet|valček| +----------------------------------------+

Če drevo ni polno, moramo za vsako nezasedeno vozlišče izpustiti prazno mesto v tabeli, da ohranimo indeksiranje. Ta predstavitev je učinkovita, če je drevo polno ali podobno polnemu. V nasprotnem primeru je v tabeli veliko praznih mest.

  • Predstavitev drevesa z dvojiškim drevesom:
 Naj bo naše osnovno drevo:
 slika:Osnovno.jpg
 Osnovni drevo transformiramo: kazalec v globino kaže na levega sina, kazalec v desno pa na 
 desnega brata:
 slika:Transformirano.jpg
 Tako transformirano drevo je že dvojiško, le pravilno ga moramo gledati:
 slika:Dvojisko.jpg
  • ...

Najpogostejše operacije nad drevesom

  • dodajanje elementa v drevo,
  • brisanje elementa iz drevesa,
  • iskanje določenega elementa v drevesu,
  • iskanje poti od korena do določenega elementa v drevesu.


Pregled dreves

- v določenem vrstnem redu obiščemo vsako vozlišče drevesa natanko enkrat.


Vrste dreves

  • dvojiška drevesa
  • 2-3 drevesa
  • AVL drevesa
  • B-drevesa
  • Rdeče-črna drevesa
  • R-drevesa
  • najbolj leva drevesa...


Glej tudi


Viri

Osebna orodja