Polno drevo

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 23:34, 19 maj 2008
IgorPrsa (Pogovor | prispevki)
Za polno drevo veljajo naslednje trditve:
← Prejšnja različica
Različica od 12:41, 22 maj 2008
MatijaLokar (Pogovor | prispevki)

Naslednja različica →
Vrstica 1: Vrstica 1:
-{{Student|IgorPrsa|DIRI}} 
- 
Binarno drevo je polno (popolnoma izravnano), če velja, da so vsi listi na istem nivoju, vsi notranji vozli pa imajo natanko dva lista. Binarno drevo je polno (popolnoma izravnano), če velja, da so vsi listi na istem nivoju, vsi notranji vozli pa imajo natanko dva lista.
<div>[[Slika:fulltree001.png|Polno drevo]]<br /> <div>[[Slika:fulltree001.png|Polno drevo]]<br />

Različica od 12:41, 22 maj 2008

Binarno drevo je polno (popolnoma izravnano), če velja, da so vsi listi na istem nivoju, vsi notranji vozli pa imajo natanko dva lista.

Polno drevo
Slika1: Polno drevo višine 3 s 15 vozlišči.


Za polno drevo veljajo naslednje trditve:

  • Prazno drevo ima višino − 1
  • drevo višine h = 0 ima en vozel, ki je hkrati list in koren;
  • polno drevo višihe h ima skupno n = 2h + 1 − 1 vozlišč;
  • polno drevo z n vozli ima višino h = log(n + 1) − 1
  • nobeno drugo binarno drevo enake višine nima več vozlišč;
  • nobeno drugo binarno drevo z enakim številom vozlišč ni nižje.

Polno drevo je idealno, kar se tiče izrabe prostora, saj ga maksimalno izkoristi. Tabela, v katero so shranjeni podatki, je popolnjena. Težava pa je v tem, da tako drevo lahko obstaja, skorajda, le teoretično, v praksi pa je mnogo bolj uporabno levo poravnano drevo, AVL drevo, B-drevo... saj so taka drevesa bolj dinamična.

Glej tudi

Osebna orodja