Vzťah medzi počtom uzlov a výškou - dátové štruktúry, výška, binárne-vyhľadávací strom

Čítam Príručka projektovania algoritmov, Autor uvádza, že výška stromu je:

h = log n,
where
h is height
n = number of leaf nodes
log is log to base d, where d is the maximum number of children allowed per node.

Potom pokračuje v tom, že výška perfektne vyváženého binárneho vyhľadávacieho stromu by bola:

h = log n

Zaujímalo by ma, či n v tomto druhom vyhlásení označuje "celkový počet uzlov listov"alebo" celkový počet uzly".

Čo vyvoláva väčšiu otázku, existuje matematický vzťah medzi celkovým počtom uzlov a výškou dokonale vyváženého binárneho stromu vyhľadávania?

odpovede:

5 pre odpoveď č. 1

iste, n = 2^h kde h, n označujú výšku stromu a počet jeho uzlov.

náčrt náčrtu:

dokonale vyvážený binárny strom má

• skutočný faktor vetvenia 2 na každom vnútornom uzle.
• rovnaké dĺžky koreňovej dráhy pre každý uzol listu.

okolo uzlov listov v perfektne vyváženom binárnom strome:

pretože počet listov je počet uzlovmínus počet uzlov v perfektne vyváženom binárnom strome s výškou zníženou o jeden, počet listov je polovica počtu všetkých uzlov (presne, polovica n+1).

tak h jednoducho sa líši o 1, čo zvyčajne neprináša žiadneskutočný rozdiel v zložitosti. toto tvrdenie môže byť ilustrované tým, že si pamätá, že to zodpovedá rovnakým rozdielom ako definovanie výšky jedného stromu uzlov ako 0 (štandardné) alebo 1 (neobvyklé, ale možno rozlíšiteľné od prázdneho stromu).

---

2 pre odpoveď č. 2

Nezáleží na tom, či hovoríte o všetkých uzlochalebo len uzly listov: buď je viazaný nad a pod druhým vynásobený konštantným faktorom. V perfektne vyváženom binárnom strome je počet uzlov na plnej úrovni počet všetkých uzlov vo vyššie uvedených úrovniach plus jeden.

---

0 pre odpoveď č. 3

V úplnom binárnom strome majú počet uzlov (n) a výška stromu (h) takýto vzťah nižšie.

n = 2 (h + 1) -1

to sú všetky uzly stromu

---