Višina drevesa

Iz MaFiRaWiki

Višina drevesa, je podatek, ki nam pove, koliko nivojev nad korenom ima drevo. Za višino drevesa veljajo naslednje trditve:

  • prazno drevo ima višino -1;
  • drevo le s korenom ima višino 0;
  • drevo z dvema elementoma (enim vozlom) ima višino 1;
  • polno dvojiško drevo višine k ima natančno 2k+1 - 1 vozlov;

Računanje višine drevesa (poddrevesa) je uporabno predvsem pri oravnotežanju dreves npr. AVL-drevesih.

Primer treh dreves višine 3

Polno drevo
Slika1: Polno drevo višine 3 s 15 vozlišči.
Drevo višine 3
Slika2: Drevo višine 3.
Drevo višine 3
Slika3: Izrojeno drevo višine 3.
Osebna orodja