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

Предположим, что мы имеем такое рекуррентное отношение, которое возникает при анализе деревьев AVL:

  • F1 = 1
  • F2 = 2
  • Fn = F n-1 + F n - 2 + 1 (где n ≥ 3)

Как бы вы решили эту рекуррентность, чтобы получить замкнутую форму для F (n)? Это число используется для получения минимального числа внутренних узлов в дереве AVL высотой n.

1 3
data-structures discrete-mathematics avl-tree recurrence

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) = F n + 2 - 1. Мы могли бы попытаться формализовать это с помощью математической индукции:

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

  • F(1) = 1 = 2 - 1 = F3 - 1
  • F(2) = 2 = 3 - 1 = F4 - 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

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

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

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

3