Stablo (struktura podataka)
Pojam „stablo“ se u programiranju koristi da označi strukturu podataka koja ima „razgranatu“ strukturu, po uzoru na pojam stabla u teoriji grafova.
Stablo je graf koji ima za 1 manji broj grana od čvorova.
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[uredi | uredi izvor]
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[uredi | uredi izvor]
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 rješenje konstrukcije i korišćenja stabla najčešće nije dobro niti lako rješenje. Umjesto 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 cijelog 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[uredi | uredi izvor]
Binarno stablo se najčešće koristi za smještaj podataka koji moraju biti u uređenom rasporedu, tj. sortirani, kako bi im se moglo brzo pristupati metodom binarne pretrage. Međutim, za smještaj bilo kakvih podataka čiji čvorovi mogu imati više od jednog djeteta potrebno je višestruko stablo. Na primjer, jezik XML po samoj svojoj definiciji zahtijeva drvoliku strukturu podataka sa neograničenim brojem grana po jednom čvoru. Takođe, datotečni sistem kao drvolika struktura zahtijeva 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 rješavanje problema izlaza iz lavirinta se, međutim, najčešće ostvaruje upotrebom reda.
Vidi još[uredi | uredi izvor]
Spoljašnje veze[uredi | uredi izvor]
- Opis pojma u rječniku algoritama i struktura podataka (jezik: engleski)
