バイナリツリーが最大で$ lceil n/2 rceil $葉を持っていることを証明する

Question

私はそれを証明しようとしています バイナリツリー $ n $ nodesの場合、せいぜい$ left lceil frac {n} {2} right rceil $葉を持っています。誘導でこれを行うにはどうすればよいですか？

ヒープに関する元の質問に従っていた人々のために、それは動かされました ここ.

Answer 1

私は今、質問が以下であると仮定します：

$ n $ nodesのバイナリツリーが与えられた場合、最大$ left lceil frac {n} {2} right rceil $葉が含まれていることを証明します。

ツリー定義で作業してみましょう$ mathrm {tree} = mathrm {empty} mid mathrm {leaf} mid mathrm {node}（ mathrm {tree}、 mathrm {tree}）$。このようなツリー$ t $の場合、$ n_t $を$ t $のノードの数と$ l_t $ $ $ $ $ $ $ of $ t $とします。

誘導によってこれを行うのは正しいですが、必要になります 構造 ツリー構造に続く誘導。木の場合、これはしばしば完全に誘導として行われます 身長 木の$ h（t）$。

誘導アンカーには2つの部分があります。まず、$ h（t）= 0 $の場合、$ l_t = n_t = 0 $で$ t = mathrm {empty} $を持っています。主張は明らかに空の木のために保持されます。 $ h（t）= 1 $、ie $ t = mathrm {leaf} $の場合、同様に$ l_t = 1 = left lceil frac {n_t} {2} right rceil $を持っています。葉を保持します。

誘導仮説は次のとおりです。クレームがすべての（バイナリ）ツリーに対して$ h（t） leq k $、$ k geq 1 $ arbitraryyが固定されていると仮定します。

誘導ステップについては、$ h（t）= k+1 $の任意のバイナリツリー$ t $を検討してください。 $ k geq 1 $、$ t = mathrm {node}（l、r）$および$ n_t = n_l+ n_r+ 1 $。 $ l $および$ r $はバイナリツリー（そうでなければ$ t $はそうではありません）と$ h（l）、h（r） leq k $であるため、誘導仮説が適用され、持っています

$ qquad displaystyle l_l leq left lceil frac {n_l} {2} right rceil text {and} l_r leq left lceil frac {n_r} {2} righ

$ t $のすべての葉は$ l $または$ r $のいずれかであるため、私たちはそれを持っています

$ qquad begin {align*} l_t＆= l_l + l_r ＆ leq left lceil frac {n_l} {2} right rceil + left lceil frac {n_r}} {2} 右 rceil ＆ leq left lceil frac {n_l + n_r + 1} {2} right rceil qquad（*）＆= left lceil frac {n_t} {2} 右 rceil end {align*} $

$（*）$でマークされた不平等は、2 mathbb {n} $の$ n_l、n_r のかどうかについて（4つの方法）ケースの区別で確認できます。誘導の力により、これは証拠を結論付けます。

---

演習として、同じ手法を使用して、次のステートメントを証明できます。

• 高さ$ h $のすべての完全なバイナリツリーには、$ 2^H-1 $ノードがあります。
• すべての完全なバイナリツリーには、奇数のノードがあります。

Answer 2

私は質問に少し混乱しています。最大$ 3 $の程度の木に興味がある場合、これがウィキペディアによると言っていることです。単一のエッジには$ n = 2 $ノードと$ n = 2 $の葉がありますが、$ n// 2 = 1 $。とにかく、ここに簡単な議論がある近いものがあります。

$ t $を$ n $ nodesと$ l $の葉を持つそのようなツリーとします。 $ t $はツリーであるため、$ n -1 $エッジがあり、それらを二重にカウントします。 n + 2 $$。これは、上記の2-vertexの例ではきついです。 2度2と$ n ge 3 $の1つのルートがあると仮定したい場合は、この引数を改善して、探しているものである$$ 2L le n + 1 $$を与えることができます。ツリーがいっぱいになるとこれはきついです。