BINARNO STABLO

Binarno stablo je specijalni slučaj stabla u kome ni jedan čvor nema stepen veći od 2. To praktično znači da svaki čvor ima najviše dva naslednika. Dakle, binarno stablo je skup od jednog ili više čvorova takvih da:

  1. Postoji jedan čvor koji je koren stabla i
  2. Preostali čvorovi su podeljeni u dva disjunktna skupa, tako da svaki skup predstavlja binarno

stablo. Ova dva skupa se nazivaju levo i desno podstablo.

Za binarno stablo važi:

  1. Maksimalni broj čvorova na i-tom nivou je 2i−1
  2. Ako je k dubina binarnog stabla, onda je maksimalan broj čvorova koje stablo može da ima je: 2k − 1 = 2k −1 + 2k − 2 + … + 20

Puno binarno stablo je binarno stablo dubine k koje sadrži 2k − 1 čvorova. Ukoliko je broj čvorova manji od 2k − 1 , binarno stablo je nepotpuno.
Kompletno binarno stablo dubine k je stablo sa n čvorova u kome bi se ovih n čvorova moglo numerisati brojevima od 1 do n, kao kada bi to bilo prvih n čvorova u punom stablu dubine k.
Obilazak binarnog stabla
Pod obilaskom binarnog stabla podrazumevamo prolazak kroz sve njegove čvorove određenim redosledom, pri čemu je istovremeno moguće izvršiti i određenu operaciju nad podacima koji su u njima zapisani.
U zavisnosti od redosleda obrade određenog čvora i njegovog levog i desnog podstabla, obilazak stabla se može izvršiti na šest načina:

  • LPD obilazak levog podstabla, obrada podatka, obilazak desnog podstabla
  • LDP obilazak levog podstabla, obilazak desnog podstabla, obrada podatka
  • PLD obrada podatka, obilazak levog podstabla, obilazak desnog podstabla
  • PDL obrada podatka, obilazak desnog podstabla, obilazak levog podstabla
  • DLP obilazak desnog podstabla, obilazak levog podstabla, obrada podatka
  • DPL obilazak desnog podstabla, obrada podatka, obilazak levog podstabla

pri čemu:
L – označava obilazak levog podstabla,
D – označava obilazak desnog podstabla,
P – označava obradu podatka u trenutnom čvoru.
Tako, na primer LPD označava redosled u kome krećemo od korena, obilazimo levo podstablo, obrađujemo podatak u korenu i na kraju obilazimo desno podstablo. S obzirom na to da su levo i desno podstablo takođe binarna stabla, potpuno ista procedura se koristi i za njihov obilazak.
Redosled LPD se naziva još i inorder, redosled LDP postorder, a redosled PLD preorder. Ostala tri redosleda se nikada ne koriste.

 
binarna_stabla.txt · Last modified: 2011/12/08 09:03 by djorde.brankovic
 
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