STABLA

strana

Pojam “stablo” se u programiranju koristi da oznaci strukturu podataka koja ima “razgranatu” strukturu, po uzoru na pojam stabla u teoriji grafova. Stablo se cesto koristi kao glavni oblik nekog spremista podataka, zbog lakog pisanja odgovarajuceg koda kroz koriscenje rekurzije, brzog upisivanja podataka i brzog pristupa trazenim podacima. Najcesce korisceno stablo je stablo u kojem svaki cvor mora imati tacno dve grane, takozvano binarno stablo.

Binarno stablo je u informatici struktura namenjena cuvanju podataka. Njene memorijske jedinice su organizovane po principu piramide. Tacnije, svaka memorijska jedinica (cvor) binarnog stabla moze da pokazuje na jos najvise dva elementa (njegova deca), dok stablo ima samo jedan element na koga ne pokazuje ni jedan drugi (koren). Od ovog elementa se moze doci u bilo koji drugi elemenat stabla. Svaki elemenat stabla moze biti i svestan koji elemenat pokazuje na njega (tj. ko mu je roditelj).

Osnovni pojmovi

Cvor stabla je jedna memorijska celija stabla. Ona moze imati nula, jedan ili dva podcvora. Ista moze da nosi dve razlicite vrednosti:

  1. Kljuc. Najcesce numericka vrednost, po kojoj se neki element rasporedjuje u binarnom stablu.
  2. Vrednost. Podatak koji treba zapamtiti. Moze se desiti da su vrednost i klju jedno te isto, tj. da se sortiranje binarnog stabla vrsi po samoj vrednosti.

Koren stabla je cvor stabla koji nije podcvor nijedno drugog cvora u stablu.
List je cvor stabla koji nema nijedan podcvor.
Roditelj nekog cvora je cvor koji pokazuje na njega.
Dete nekog cvora je cvor na koji neki drugi cvor pokazuje.

 
stabla.txt · Last modified: 2012/02/22 18:04 by marjan.djordevic
 
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