完全なバイナリツリーに$ lceil n/2 rceil $葉があることを証明するにはどうすればよいですか？

Question

$ n $ nodesの完全なバイナリツリーが与えられます。完全なバイナリツリーに正確に$ lceil n/2 rceil $葉があることを証明しようとしています。誘導によってこれを行うことができると思います。

$ h（t）= 0 $の場合、ツリーは空です。したがって、葉はなく、主張は空の木を保持します。

$ h（t）= 1 $の場合、ツリーには1つのノードがあり、これも葉であるため、クレームは保持されます。ここで私は立ち往生しています、私は誘導仮説として何を選ぶべきか、そして誘導ステップをどのように行うかわかりません。

Answer 1

あなたが誘導によって証明しようとしている声明が

すべての正の整数$ n $の場合、$ n $ nodesの完全なバイナリツリーには$ lceil {n/2} rceil $葉があります。

その後、誘導仮説はそうでなければなりません

すべての正の整数に対して$ k

同様に、あなたが誘導によって証明しようとしている声明が

すべての正の整数$ n $について、$ n $ whatsitsのHoosegowには2^{ lfloor sqrt {n} rceil！} cdot n^ pi $ nubbleframetsがあります。

その後、誘導仮説はそうでなければなりません

すべての正の整数に対して$ k

Answer 2

まず、用語でもう少し具体的になるのに役立つかもしれません。 [CLRS01]がそれを定義する方法で「完全」を意味すると思います。

すべての葉には同じ深さがあり、すべての内部ノードには度2があります。

第二に、この宿題ですか？

構造誘導を使用してこれを証明できます。 「ベース」ツリーの主張が保持されていることを示し、これらから他の完全なバイナリツリーがどのように構築されているかを考えてください。

この方法で大きな木を構築すると、ノードの総数はどのように増加しますか？葉の数はどのように増加しますか？

ヒント：

$ lceil n+1 rceil = 2 lceil n/2 rceil $はありますか？