math - AVL ツリーのノード数の再帰関係を解くには?

Question

AVL ツリーの分析で出てくる次の再帰関係があるとします。

• F1 = ₁
• F ₂ = 2
• F _n = F _{n - 1} + F _{n - 2} + 1 (n ≥ 3)

F(n) の閉形式を取得するには、この再帰をどのように解決しますか? この数は、高さ nのAVL ツリー内の内部ノードの最小数を取得するために使用されます。

Answer 1

この再発を解決する方法はたくさんありますが、そのほとんどはかなり複雑です。これを行う最も簡単な方法は、シリーズのいくつかの用語を展開して、見つけたものを確認することだと思います。

• F(1) = 1
• F(2) = 2
• F(3) = 4
• F(4) = 7
• F(5) = 12
• F(6) = 20

これを見ると、次のことが成り立つことがわかります。

• F(1) = 1 = 2 - 1
• F(2) = 2 = 3 - 1
• F(3) = 4 = 5 - 1
• F(4) = 7 = 8 - 1
• F(5) = 12 = 13 - 1
• F(6) = 20 = 21 - 1

これらの項は、フィボナッチ数列から 1 を引いた項にすぎないようです。_{特に、F 3} = 2、F ₄ = 3、F ₅ = 5 などに注意してください。したがって、パターンは次のようになります。

• F(1) = 2 - 1 = F ₃ - 1
• F(2) = 3 - 1 = F ₄ - 1
• F(3) = 5 - 1 = F ₅ - 1
• F(4) = 8 - 1 = F ₆ - 1
• F(5) = 13 - 1 = F ₇ - 1
• F(6) = 21 - 1 = F ₈ - 1

_{したがって、より一般的には、パターンは F(n) = F n + 2} - 1のように見えます。数学的帰納法を使用してこれを形式化することができます。

基本ケース:

• F(1) = 1 = 2 - 1 = F ₃ - 1
• F(2) = 2 = 3 - 1 = F ₄ - 1

誘導ステップ: F(n) = F _n+2 - 1 および F(n + 1) = F _n+3 - 1と仮定します。

• F(n + 2) = F(n) + F(n + 1) + 1 = F _n+2 - 1 + F _n+3 - 1 + 1 = (F _n+2 + F _n+3 ) - ( 1 + 1) + 1 = F _n+4 - 1 = F _{(n + 2) + 2} - 1

出来上がり！誘導はチェックアウトします。

では、フィボナッチ数列でそのパターンを探すにはどうすればよいと思いましたか? うーん... 再帰的な定義はフィボナッチ数列の定義のように見えたので、おそらくそれらの 2 つの間に何らかの関連があると予想しました。すべてがフィボナッチ数から 1 を引いたものであるという観察は、単なる創造的な洞察でした。私はそれらの専門家ではありませんが、生成関数またはその他の組み合わせのトリックを使用して、これを解決しようとする可能性があります。

お役に立てれば！