0

私は圧縮試行について読んでいて、次を読みました：

圧縮されたトライは、L 個の葉を持つツリーであり、トライのすべての内部ノードには少なくとも 2 つの子があります。

次に、著者は、すべての内部ノードに少なくとも 2 つの子があり、最大で L-1 個の内部ノードがあるような L の葉を持つツリーを書いています。なぜこれが真実なのか、私は本当に混乱しています。

誰かがそれの帰納的証明を提供できますか?

4

3 に答える 3

3

帰納的証明: ツリーの葉の数
に関する帰納法によって証明します。ベース: 1 枚の葉から作られたツリーは、実際には根だけを持つツリーです。内部ノードは 0 であり、主張は真です。 L 個の葉を持つ圧縮されたツリーに対して主張が真である と仮定します。ステップ: T を L+1 枚の葉を持つ木とします。任意の葉を選び、それを l としてトリミングします。 ツリーを再度圧縮するには、l の父親をリーフにする必要があります [l の父親に l を含む 2 人以上の息子がいる場合は、この手順をスキップしてください]。l の兄弟と同じ値を与え、兄弟をトリムすることでそれを行います。 これで、L 枚の葉を持つ木 T' ができました。 帰納法: T' は最大で L-1 個の内部ノードを持ちます。 L






したがって、T には L-1+1 = L 個の内部ノードと、最大で L+1 個のリーフがありました。
QED

代替証明:
L 個の葉を持つ二分木には L-1 個の内部ノード (1 + 2 + 4 + ... + L/2 = L-1)
があります。「最悪の場合」では、二分木があるため [すべての内部ノードは少なくとも 2 人の息子!]、L-1 を超える内部ノードを持つことはできません!

于 2012-01-16T13:04:36.843 に答える
0

よし、やってみよう。

手始めにツリーを定義します。

T_0 = { Leaf }

T_i = T_i-1 union { Node(c1, ..., cn) | n >= 1 && ci in T_i-1 }

Trees = sum T_i

さて、あなたの主張の（スケッチ）証明です。

  1. それを確認するのは簡単ですT_0

  2. For T_i:新しい要素t \in T_i内T_i-1または新しい要素内にある場合。前者の場合はIHをご利用ください。後者の場合、アサーションをチェックします (単純: もしcis がL_i葉をt持っているなら、葉を持っていL = L_1 + ... + L_nます。それはまた、内部ノードよりも多くありませんL_1 - 1 + L_2 - 1 + ... + L_n - 1 + 1(子の場合は IH、自己の場合は +1 による)。各内部ノードには少なくとも 2 つの子があると仮定しているため (それはトライの定義からの事実です)、それは以下ですL_1 + l_2 + ... + L_n - 2 + 1 = L - 1)。

  3. 帰納法により、アサーションがt in T_iすべての に対して成り立つ場合i、それは に対して成り立ちt in Treesます。

于 2012-01-16T13:16:24.710 に答える
0

L 個の内部ノードを持つツリーを描画してみてください。すべてのノードには 2 つの子があり、L 個の葉があります。これが不可能な理由がわかれば、L-1 内部ノードで機能する理由を理解するのは難しくありません。

于 2012-01-16T13:03:18.800 に答える