This is an old revision of the document!


Stabla (struktura podataka)

Pojam „stablo“ se u programiranju koristi da označi strukturu podataka koja ima „razgranatu“ strukturu, po uzoru na pojam stabla u teoriji grafova1). Stablo se često koristi kao glavni oblik nekog spremišta podataka, zbog lakog pisanja odgovarajućeg koda kroz korišćenje rekurzije, brzog upisivanja podataka i brzog pristupa traženim podacima. Najčešće korišćeno stablo je stablo u kojem svaki čvor mora imati tačno dvije grane, tj. binarno stablo.

Terminologija

U terminologiji stabla kao strukture podataka, koriste se slični pojmovi kao kod običnog stabla. Tako, čvor koji ne sadrži granu nijednog drugog čvora a koji posredno ili neposredno sadrži sve druge čvorove naziva se „korijen“. Čvorovi koji ne sadrže nijednu granu, tj. nalaze se na „vrhu“ stabla, nazivaju se „listovima“ Takođe, postoji terminologija „roditelj-dijete“, u kojoj se čvor A koji sadrži čvor B naziva roditeljem čvora B, dok se čvor B naziva djetetom čvora A.

Konstrukcija

Stablo se u programiranju ostvaruje korišćenjem pokazivača da bi se usmjerilo ka odgovarajućim granama. Naime, svaki čvor se konstruiše tako da posjeduje mogućnost čuvanja jedne ili više adresa drugih čvorova, što omogućava „prelaženje“ iz jednog čvora u drugi, tj. kretanje po stablu.

Budući da stablo može imati neograničen broj čvorova (uslovno govoreći, zbog ograničene količine memorije na računarskim uređajima), iterativno rešenje konstrukcije i korišćenja stabla najčešće nije dobro niti lako rješenje. Umesto toga, pišu se funkcije koje se rekurzivno pozivaju dok jedna od instanci funkcije ne primi traženi čvor kao argument. Tada se izvrši željena radnja (vraćanje rezultata ili stvaranje novog čvora) i rekurzivni lanac se odmotava i završava. Slabost rekurzivnog rješenja leži u situacijama kada je stablo veliko, te dolazi do prenatrpavanja funkcijskog steka procesa što može dovesti do usporenosti ili naglog prekidanja celog programa.

Dok se binarno stablo u programiranju ostvaruje relativno jednostavno, korišćenjem tačno dva pokazivača, neograničen broj grana po čvoru se implementira na nešto složeniji način. Potrebno je u svakom čvoru čuvati neku strukturu podataka koja podržava neograničen broj pokazivača, što se najčešće čini koristeći liste ili obične nizove koji se proširuju po potrebi.

Upotreba

Binarno stablo se najčešće koristi za smeštaj podataka koji moraju biti u uređenom rasporedu, tj. sortirani, kako bi im se moglo brzo pristupati metodom binarne pretrage. Međutim, za smeštaj bilo kakvih podataka čiji čvorovi mogu imati više od jednog deteta potrebno je višestruko stablo. Na primjer, jezik XML po samoj svojoj definiciji zahteva drvoliku strukturu podataka sa neograničenim brojem grana po jednom čvoru. Takođe, datotečni sistem kao drvolika struktura zahteva neograničen broj grana po jednom direktorijumu. U pojedinim implentacijama video igara, lavirinti se takođe implementiraju kao višestruka stabla, pri čemu je svako polje u lavirintu predstavljeno jednim čvorom u stablu, a polja na koja se može preći iz datog polja su predstavljena kao grane odgovarajućeg čvora. Obično rešavanje problema izlaza iz lavirinta se, međutim, najčešće ostvaruje upotrebom reda.

Primer

Sledeći primer pokazuje formiranje i ispisivanje uredjenog binarnog stabla u programskom jeziku C:

stablo.c
#include <stdio.h>
#include <stdlib.h>
 
struct cvor
{
 int broj;
 struct drvo *levi,*desni;
};
 
#define novi(x) x=(struct cvor *) malloc(sizeof(struct cvor))
 
void dodaj(struct cvor **,int);
struct cvor* form();
void ispis(struct cvor*);
 
main()
{
 struct cvor *koren;
 int n,m;
 koren=form();
 ispis(koren);
}
 
void dodaj(struct cvor **p,int k)
{
 
 struct cvor *temp,*pom1,*pom2;
 novi(temp);
 
 if(!temp) 
 {
  printf("\nGreska pri alokaciji memorije\n");
  exit(0);
 }
 
 temp->broj=k;
 temp->levi=temp->desni=NULL;
 
 if (!(*p)) *p=temp;
 else
 {
  pom1=*p;
  while(pom1)
  {
   pom2=pom1;
   if(k < pom1->broj) pom1=pom1->levi;
   else pom1=pom1->desni;
  }
 if(k < pom2->broj) pom2->levi=temp;
 else pom2->desni=temp;
 }
}
 
 
struct cvor* form()
{
 
 struct cvor *koren;
 int k;
 koren=NULL;
 scanf("%d",&k);
 while(k) 
 {
  dodaj(&koren,k);
  scanf("%d",&k);
 }
 return koren;
}
 
void ispis(struct cvor *p)
{
 if (p) 
 {
  ispis(p->levi);
  printf("%5d",p->broj);
  ispis(p->desni);
 }
}
 
1.stabla_strukture_podataka.1323331172.txt.gz · Last modified: 2011/12/08 08:59 by marko.dragicevic
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki