Это отличное место для рисования картинок и поиска рисунка.
Вот самые маленькие деревья высот AVL 0 и 1:
*
*
|
*
Самое маленькое дерево высот AVL 2 было бы сделано с использованием деревьев высот 0 и 1 (если вы использовали высоты 1 и 1, вы могли бы увеличить количество узлов, используя деревья высотой 0 и 1), а наименьший параметр -
*
/ \
* *
|
*
Тогда самое маленькое дерево высоты 3 будет использовать деревья высот 1 и 2, которые будут выглядеть так:
*
/ \
* *
| / \
* * *
|
*
И, в более общем случае, самое маленькое дерево высоты k, где k ≥ 2 , получается путем взятия двух наименьших деревьев высот k-1 и k-2 и связывания их вместе с новым узлом в root.
. Это дает рекуррентное соотношение:
T (n) = T (n - 1) + T (n - 2) + 1
T (0) = 1
T (1) = 2
Повторение этой повторяемости дает следующий шаблон:
h = 0 1 2 3 4 5 6 7 8
1 2 4 7 12 20 33 54 88
Есть несколько вещей, которые вы могли бы сделать дальше:
- Не могли бы вы написать код ome, чтобы оценить это рекуррентное отношение на все большие и большие значения п? Это может дать вам функцию, которая напрямую вычисляет нужное вам число.
- Повторение T (n) = T (n-2) + T (n-1) + 1 выглядит как лот как повторение Фибоначчи F (n) = F (n-2) + F (n-1). Видите ли вы какую-либо связь между числами T (n) и последовательностью Фибоначчи? Это может позволить вам непосредственно вычислить ответ.
Надеюсь, это поможет!