Uporabniški pogovor:IgorPrsa

Iz MaFiRaWiki

Polno drevo

GFDL Avtor tega članka je študent/ka IgorPrsa.

Pripravil/a ga je pri predmetu DIRI.


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

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 skupno 15 vozlišči.


Za polno drevo veljajo naslednje trditve:

  • drevo višine h=0 ima en vozel, ki je hkrati list in koren;
  • polno drevo višihe h ima skupno n=h+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.
Osebna orodja