data-structures - AVL ツリーの最小ノード

Question

高さ h の AVL ツリーのノードの最小数は? 私はインターネットでいくつかの調査を行いましたが、それらはすべて非常に混乱しています。

Answer 1

高さ h のツリーの AVL ツリーのノードの最小数。次の式は、N(h) 関数の再帰呼び出しを示しています。

formula N(h)=1+N(h-1)+N(h-2)

N(0)=1 ,N(1) = 2, N(2) = 4たとえば、 がわかっているので、次の方程式を のこれらの既知の値に減らすことができh = 6ます。

N(3)=1+N(3-1)+N(3-2)=1+N(2)+N(1)=7

N(4)=1+N(4-1)+N(4-2)=1+N(3)+N(2)=12

N(5)=1+N(5-1)+N(5-2)=1+N(4)+N(3)=20

N(6)=1+N(6-1)+N(6-2)=1+N(5)+N(4)=33

Answer 2

高さ h の AVL ツリーには、少なくとも 2(h/2)-1 個の内部ノードがあります。

証明:高さ h の AVL ツリーの内部ノードの最小数を n(h) とします。

n(1)=1 および n(2)=2。したがって、補題は h=1 と h=2 に対して成り立ちます。