Как найти минимально возможную высоту дерева?

Question

Разделение узла в дереве определяется как количество дочерних узлов узла. Разветвление дерева определяется как максимальный разветвление любого узла в дереве. Предположим, что дерево T имеет n узлов и разветвление f> 1. Какова минимально возможная высота T?

Я понятия не имею, как начать эту проблему. Я решил первую часть, которая заключается в том, чтобы найти максимальное количество узлов, которые могут быть Т в терминах высоты h и разветвления f> 1. Я получил (f^(h + 1) -1)/(f-1) , Я думаю, вы можете использовать это для решения вышеизложенного. Может кто-нибудь, пожалуйста, указать мне в правильном направлении?

Спасибо!

Answer 1

Я бы подошел к этой проблеме, развернув ее и пытаясь найти максимальное количество узлов, которые вы можете упаковать в дерево с заданной высотой и отключением T_max(h,f). Таким образом, у каждого другого дерева T(h,f) гарантировано будет столько же или меньше узлов, кроме T_max(h,f). Поэтому, если вы найдете такой T_max(h,f), что

total_nodes(T_max(h,f)) > n > total_nodes(T_max(h-1,f)) 

h будет гарантированно минимальную высоту дерева с n узлами и f вентилятор-аут.

Чтобы найти такое дерево, вам нужно максимально увеличить количество узлов в каждом слое дерева. Другими словами, каждый узел такого дерева должен иметь вентилятор f, не менее. Поэтому вы начинаете вставлять узлы в дерево, по одному уровню за раз. После заполнения слоя вы начинаете добавлять еще один слой. После того, как в таком дереве вставлены n узлов, вы останавливаете и проверяете высоту дерева. Это будет минимальная высота, которую вы ищете.

Или, вы можете сделать расчет вместо:

nodes_in_level(1) = 1 
nodes_in_level(2) = f 
nodes_in_level(3) = f * f 
... 
nodes_in_level(x) = f^(x - 1) 

Это стандартный geometric progression. Таким образом, максимальные узлы данного дерева с высотой x и вентилятор f являются суммой такой геометрической прогрессии, и не должно быть слишком много проблем, чтобы выяснить наименьший x, для которого число узлов больше n.