Учитывая, что дерево имеет высоту h и степень d, применяется следующее.
Минимальное количество узлов
Чтобы построить дерево высоты h с таким количеством узловнасколько возможно, вы захотите, чтобы у каждого узла был только один дочерний элемент.Следовательно, вам понадобится h узлов.
Максимальное количество узлов
Чтобы использовать как можно больше узлов, вам нужно, чтобы каждый узел (кроме листьев) имелкак можно больше детей, то есть детей.Это будет выглядеть так:
level nodes at level
1 1 (d^0)
2 d (d^1)
3 d^2
4 d^3
Таким образом, число узлов представляет собой сумму, подобную
num_nodes = d^0 + d^1 + d^2 + d^3 + ....
Это геометрическая сумма, которая может быть рассчитана как:
num_nodes = (1 - d^h)/(1 - d)