Как найти нижнюю и верхнюю границу m для m-арного дерева?

Question

Полное m-арное дерево T имеет 81 лист и высоту 4, как найти верхнюю и нижнюю границы для m.

Я не получаю это, как по мне m> = 3, так что как найти нижнюю границу для этого.

Answer 1

ниже связаны действительно 3: так как число узлов умножается на наиболее m на каждой глубине, один нуждается в арность по крайней мере, 3, чтобы получить 81 листьев на глубину 4.

Теперь давайте говорить о верхняя связаны.

Рассмотрим это дерево:

o 
    /|\ 
    o o o 
/|\ 
o o o 

Если по полный вы имеете в виду, что каждый узел глубины < 4 имеет m детей, то пример не является полным. В этом случае m^4 = 81 так m=3.

Если вы имеете в виду, что каждый внутренний (то есть не листовой) узел имеет m детей, то пример равен. С этим определением, вот пример полного 3-ичным деревом глубины 4 с 9 листов:

 o 
     /|\ 
     o o o 
    /|\ 
    o o o 
    /|\ 
    o o o 
/|\ 
o o o 

Я надеюсь, что этот вопрос является яснее. Это домашнее задание? Пока я оставлю это вам, чтобы вычислить верхнюю границу.

Answer 2

m.i + 1 = n, тогда для увеличения m мы должны увеличить i, что является числом внутренних элементов. m-1 + m-1 + m-1 + m = 81. Затем m = 21.