Visina dvoiškega drevesa

Iz MaFiRaWiki

(Preusmerjeno iz J. Kruskalom)

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 ima višino 1;

Računanje višine drevesa (poddrevesa) je uporabno predvsem pri oravnotežanju dreves npr. AVL-drevesih. * Število vozlišč na nivoju k: največ 2k-1 Število vseh vozlišč: največ 2k - 1, najmanj k Potomcev: najmanj k-1, največ 2k-1 - 1 Prednikov: k - 1

Osebna orodja