Stabla odlučivanja

Visoka Poslovna Škola Strukovnih Studija

Blace

Seminarski Rad

iz predmeta Algoritmi i Strukture Podataka

na temu Stabla Odlučivanja

Student: Jovanović Filip
Broj Indeksa: 65/09 III
Odsek: Računarstvo I Informatika
Smer: Informacione Tehnologije
Godina Studija: II

Profesor: Ph.D Jevtović Branislav

Asistent: Ubavić Vladica

______________________________________________________________________________ u Blacu, Jun 2011.

______________________________________________________________________________

Visoka Poslovna Škola Strukovnih Studija - Blace
Odsek: Računarstvo I Informatika
Smer: Informacione Tehnologije

Seminarski Rad iz predmeta Algoritmi i Strukture Podataka

Tema rada: Stabla Odlučivanja

Student: Jovanović Filip 65/09 III

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

_______________________________________________________________________________________________________________________________________________________________________________
Oficijalna stranica Visoke Poslovne Škole Strukovnih Studija - Blace
http://www.vpskp.edu.rs/

Sadržaj

Naslovna strana

Apstraktni vektorski logotip Visoke Poslovne Škole, osnovni podaci o seminarskom radu sa podacima studenta, asistenta i profesora

Sadržaj

Spisak svih stranica sa detaljnim podacima o poglavljima u radu

Uvod

Teorijske osnove o predmetu Algoritmi i Strukture Podataka

Stabla

Detaljna analiza strukture stabala i najbitnije teorijske činjenice o svim stablima

Prolazi kroz stablo

Detaljna analiza strukture stabla i prolaza koji se mogu izvršiti kroz njega

Stablo Binarnog Pretraživanja (BST)

Osnovne informacije i karakteristike BST-a

Stablo Odlučivanja

Teorijske osnove u odlučivanju sa grafičkim prikazima zbog boljeg razumevanja sistema

Primeri korišćenja stabla odlučivanja

Fenomen razumevanja smisla rada preko konkretnih problema sa rešenjima

Reference

Spisak materijala korišćenih u izradi seminarskog rada iz predmeta Algoritmi i Strukture Podataka

Visoka Poslovna Škola Strukovnih Studija - Blace
Odsek: Računarstvo I Informatika
Smer: Informacione Tehnologije

Seminarski Rad iz predmeta Algoritmi i Strukture Podataka

Tema rada: Stabla Odlučivanja

Student: Jovanović Filip 65/09 III

Većina terminologije potiče iz ovih izvora.

Stablo je konačan skup čvorova sa svojstvima:



postoji poseban čvor koji se naziva

koren

(root)



ostali čvorovi su podeljeni u k disjunktnih podskupova T

..T

, od kojih je svaki stablo. T

..T

se nazivaju i

podstabla

A je koren stabla, dok skup H, I, E, F, J, K čini skup krajnjih čvorova ili ti listova. Koreni podtabla nekog
čvora su deca tog čvora pa u ovom slučaju imamo E, F, G kao decu čvora C. Čvor C možemo nazvati
roditeljem, isto kao i u slučaju G i J, gde je G roditelj, u nekim slučajevima nazivan i otac, a J dete.

Stablo se može definisati kao poseban oblik nelinearnog grafa: Linearni graf je skup čvorova i skup relacija
(nazivaju se linije grafa) koji opisuju veze između čvorova. Linearni graf je povezan ako je svaki par
čvorova u grafu povezan linijom.

Stablo se onda može definisati kao povezan graf koji ne sadrži petlje, odnosno ako važi:



Bilo koja dva čvora u stablu su povezana linijom



Stablo sa n čvorova ima n-1 linija

Za dva stabla se kaže da su slična ako imaju istu strukturu, tj. tačnije ako su oba prazna ili su sva njihova
podstabla slična. A postoje i dva stabla koja su ekvivalentna ako su slična i imaju identičan informacioni
sadržaj u odgovarajućim čvorovima.

Pre nego što analiziramo određenu vrstu stabla moramo se upoznati i sa ostalim terminima iz algoritama i
struktura podataka.



Terminalni čvor ili list je čvor koji nema podstabla.



Čvor d je dete čvoru k ako je d koren podstabla od čvora k. Čvor k je roditelj.



Stepen čvora je broj podstabala datog čvora



Šuma je skup stabala koja ne preklapaju



Nivo čvora je 1 ako je koren ili jednak broju čvorova koji se prodju na putu od korena do datog
čvora.

Visoka Poslovna Škola Strukovnih Studija - Blace
Odsek: Računarstvo I Informatika
Smer: Informacione Tehnologije

Seminarski Rad iz predmeta Algoritmi i Strukture Podataka

Tema rada: Stabla Odlučivanja

Student: Jovanović Filip 65/09 III



Visina (ili dubina) stabla je maksimalni nivo na kome se nalazi neki čvor stabla

Postoji više oblika u kom se javljaju stabla. Jedan od tih oblika je i binarno stablo. Ono takođe može imati i
svoje varijacije. Striktno binarno stablo je binarno stablo kod koga svaki čvor nema nijedno podstabla ima
tačno dva. Kompletno binarno stablo je striktno binarno stablo kod koga su svi listovi na istom nivou. Broj
čvorova u kompletnom stablu je: n = 2

-1, gde je h visina stabla.

Skoro kompletno binarno stablo je binarno stablo za koga važi da su svi nivoi u stablu popunjeni, osim
eventualno zadnjeg, i to tako da se popunjavanje vrši s leva u desno.

Prolazi kroz stablo

Način kako se mogu obići čvorovi datog stabla, a da se pri tome posete tačno jednom objašnjava nam
oblast prolaza kroz stablo. Postoji više načina kako se to može učiniti.
Tri su standardna načina:



Prefiks prolaz



Infiks prolaz



Postfiks (sufiks) prolaz