NノードのAVLツリーがC <= N/2を維持するのはなぜですか？

Question

Cが「唯一の子」ノードの数を示している場合（ノードが唯一の子であり、その親がヌルでない場合& &には兄弟はありません）、なぜNノードを持つすべてのAVLツリー：C < =（N/2）？

Answer 1

高さ1のAVLツリー（すなわち、ルートのみからなる）を考えてみましょう。条件は明らかに保持されます（N = 1、C = 0）。

高さ2のAVLツリーを考えてみましょう。2つの子（N = 3、C = 0）または1つの子（N = 2、C = 1）を持つルートのいずれかがあります。したがって、条件は高さ2の木にも当てはまります。

ここで、高さh（h> = 2）とh-1の木について条件が成立すると仮定し、高さhの木+1。高さhの子と高さhまたはh-1の子を持つ新しいルートをとることによって、高さh + 1のツリーを構築できます。これらは、AVLプロパティをそのまま維持する唯一の許可された構成です。 2つのサブツリーの新しいルートもルートも、「唯一の子」ノードではありません。従って、N = 1 + N1 + N2、C = C1 + C2となる。 C1 < = N1/2およびC2 < = N2/2であるので、C < = N/2となる。

ここで、誘導によって、すべての高さのAVLツリーに対して条件が成立します。