math - 求解 AVL 树中节点数的递归关系？

Question

假设我们有这个递归关系，它出现在 AVL 树的分析中:

F1 = 1

F2 = 2

Fn = Fn - 1 + Fn - 2 + 1(其中 n ≥ 3)

你将如何解决这个递归以获得 F(n) 的封闭形式？此数字用于获取 AVL tree 中内部节点的最小数量。与高度 n。

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 的术语。特别要注意的是，F3 = 2、F4 = 3、F5 = 5 等等。因此，看起来模式是

F(1) = 2 - 1 = F3 - 1

F(2) = 3 - 1 = F4 - 1

F(3) = 5 - 1 = F5 - 1

F(4) = 8 - 1 = F6 - 1

F(5) = 13 - 1 = F7 - 1

F(6) = 21 - 1 = F8 - 1

因此，更一般地，看起来模式是 F(n) = Fn + 2 - 1。我们可以尝试使用数学归纳法将其形式化:

基本情况:

F(1) = 1 = 2 - 1 = F3 - 1

F(2) = 2 = 3 - 1 = F4 - 1

归纳步骤:假设 F(n) = Fn+2 - 1 和 F(n + 1) = Fn+3 - 1。那么我们有

F(n + 2) = F(n) + F(n + 1) + 1 = Fn+2 - 1 + Fn+3 - 1 + 1 = (Fn+2 + Fn+3) - (1 + 1) + 1 = Fn+4 - 1 = F(n + 2) + 2 - 1

等等!感应检查出来。

那么我是如何想到用斐波那契数列寻找这种模式的呢？嗯……递归定义有点像斐波那契数列的定义，所以我预计这两者之间可能存在某种联系。观察到一切都是斐波那契数减一只是创造性的洞察力。您可能会尝试使用生成函数或其他组合技巧来解决这个问题，尽管我不是这方面的专家。

希望这可以帮助!