Polno drevo

Iz MaFiRaWiki

Dvojiško 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 dvojiško drevo enake višine nima več vozlišč;
  • nobeno drugo dvojiško drevo z enakim številom vozlišč ni nižje.

Če polno drevo hranimo v tabeli, gl.dvojiško drevo, je prostor za shranjevanje optimalni ozkoriščen. Tabela, v katero so shranjeni podatki, je popolnjena. Težava je v tem, da je vzdrževanje polnega drevesa zelo "drago". Drevesa, kot so: levo poravnano drevo, AVL drevo, B-drevo... so lažja za vzdrževanje, saj je dodajanje in brisanje elementov preprostejše ("cenejše").

Glej tudi

Osebna orodja