解決AVL樹中節點數量的遞推關係？

Question

假設我們有這樣的遞推關係，這在AVL樹的分析上來：

• ˚F = 1
• ˚F = 2
• ˚F_ň = F _{N - 1} + F _{N - 2} + 1（其中n ≥ 3）

你會如何解決這個復發來獲得F（n）的封閉形式？這個數字用於獲得高度爲n的AVL tree中的最小內部節點數。

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 = 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

的Et瞧！入門檢查。

那麼我怎麼想到用斐波那契數列來尋找那個模式呢？那麼......遞歸定義看起來像斐波那契數列的定義，所以我預計它們之間可能有某種聯繫。觀察一切都是斐波納契數字減去一個就是創造性的洞察力。你可能試圖通過使用生成函數或其他組合技巧來解決這個問題，儘管我對它們並不熟悉。

希望這會有所幫助！