Решение рекуррентного отношения для числа узлов в дереве AVL?

Question

Предположим, что мы имеем это рекуррентное соотношение, которое приходит в анализе АВЛ деревьев:

• F = 1
• F = 2
• Р _п = Р _{п - 1} + Ж _{п - 2} + 1 (где п ≥ 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
• Р (5) = 12 = 13 - 1
• Р (6) = 20 = 21 - 1

похоже, эти термины являются только члены из Серия Фибоначчи с 1 вычитается из них. В частности, обратите внимание, что F = 2, F = 3, F = 5 и т. Д.Таким образом, это выглядит, как картина

• Р (1) = 2 - 1 = F - 1
• Р (2) = 3 - 1 = F - 1
• F (3) = 5 - 1 = F - 1
• Р (4) = 8 - 1 = F - 1
• Р (5) = 13 - 1 = F - 1
• Р (6) = 21 - 1 = F - 1

Таким образом, в более общем случае, это выглядит как картина Р (п) = Р _{п + 2} - 1. Мы могли бы попытаться формализовать с помощью математической индукции:

Базовые случаи:

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

Индуктивный шаг: Пусть F (п) = F _{п + 2} - 1 и F (N + 1) = F _{п + 3} - 1. Тогда мы имеем, что

• Р (п + 2) = Р (п) + F (п + 1) + 1 = F _{п + 2} - 1 + Ж _{п + 3} - 1 + 1 = (F _{n + 2} + F _{n + 3}) - (1 + 1) + 1 = F _{п + 4} - 1 = F _{(п + 2) + 2} - 1

Et вуаля! Индукция проверяется.

Так как же я думаю, что искать этот образец с серией Фибоначчи? Ну ... рекурсивное определение вроде бы похоже на одно для серии Фибоначчи, поэтому я ожидал, что между ними есть какая-то связь. Наблюдение за тем, чтобы все было числом Фибоначчи минус один, было просто творческим прозрением. Вы могли бы попытаться решить эту проблему, используя генераторные функции или другие комбинаторные трюки, хотя я не очень разбираюсь в них.

Надеюсь, это поможет!