5

The Algorithm Design Manualを読んでいます。著者は、木の高さは次のように述べています。

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.

彼は次に、完全にバランスの取れた二分探索木の高さは次のようになると言い続けています。

h = log n

nこの 2 番目のステートメントでは、「リーフ ノードの総数」または「ノードの総数」を示しているのだろうか。

ノードの総数と完全にバランスの取れた二分探索木の高さとの間に数学的な関係があるのでしょうか?

4

3 に答える 3

0

完全二分木では、ノードの数 (n) と木の高さ (h) は次のような関係にあります。

n = 2^(h+1) -1

これはツリーのすべてのノードです

于 2015-05-20T03:46:46.823 に答える