Общее количество узлов в структуре данных дерева?

Question

У меня есть структура данных дерева, которая L уровней глубоко, каждый узел имеет около N узлов. Я хочу выработать общее количество узлов в дереве. Чтобы сделать это (я думаю), мне нужно знать, какой процент узлов будет иметь дети.

Каков правильный термин для этого отношения листовых узлов к нелистовым узлам в N?

Какова формула для расчета общего числа узлов в трех?

Update Кто-то уже Ветвление фактор в одном из ответа, но затем исчез. Я думаю, что это был тот термин, который я искал. Значит, не должна ли формула учитывать фактор ветвления?

Обновление Я должен был сказать оценку гипотетической структуры данных, а не точную цифру!

Answer 1

Хорошо, каждый узел имеет около N подузлов, а дерево - L уровней.

With 1 level, the tree has 1 node. 
With 2 levels, the tree has 1 + N nodes. 
With 3 levels, the tree has 1 + N + N^2 nodes. 
With L levels, the tree has 1 + N + N^2 + ... + N^(L-1) nodes. 

Общее количество узлов (N^L-1)/(N-1).

Хорошо, только маленький пример, почему он является экспоненциальным:

    [NODE] 
         | 
        /|\ 
        /| \ 
       /| \ 
       / | \ 
      [NODE] [NODE] [NODE] 
       | 
      /|\ 
      /| \ 

Answer 2

Если вы не знаете ничего, кроме глубины дерева, то ваш единственный вариант для расчета общего размера - это пройти и подсчитать их.

Answer 3

Формула для вычисления количества узлов в глубине L является: (Принимая во внимание, что есть N корневых узлов)

N ^л

Для того, чтобы вычислить количество всех узлов нужно сделать, это для каждого слоя:

for depth in (1..L) 
    nodeCount += N ** depth 

Если есть только один корневой узел, вычтите 1 из L и добавьте 1 к общему количеству узлов.

Помните, что если в одном узле количество листьев отличается от среднего, это может сильно повлиять на ваш номер. Чем дальше в дереве, тем больше воздействие.

 
    *    *     *   N ** 1 
    ***    ***    ***  N ** 2 
*** *** ***  *** *** ***  *** *** *** N ** 3 

Это сообщество wiki, поэтому не стесняйтесь изменять мою ужасную алгебру.

Answer 4

Если ваше дерево примерно полный, что каждый уровень имеет полный набор детей в течение последних двух, за исключением, то вы имеют между N^(L-2) и N^(L-1) листовые узлы и между N^(L-1) и N^L узлов всего.

Если ваше дерево не заполнено, то знание количества листовых узлов не помогает, поскольку полностью неуравновешенное дерево будет иметь один листовой узел, но сколько угодно родителей.

Интересно, насколько точна ваша заявка «каждый узел имеет около N узлов» - если вы знаете средний коэффициент ветвления, возможно, вы можете вычислить ожидаемый размер дерева.

Если вы можете найти отношение листьев к внутренним узлам, и вы знаете среднее число детей, вы можете приблизиться к нему как (n * ratio)^N = n. Это не даст вам ответа, но мне интересно, может ли кто-то с лучшими математиками, чем я, найти способ вставить L в это уравнение и дать вам что-то разрешимое.

Тем не менее, если вы хотите точно знать, вы должны перебирать структуру дерева и подсчитывать узлы по мере продвижения.

Answer 5

Как раз для того, чтобы исправить опечатку в первом ответе: общее количество узлов для дерева глубины L (N^(L + 1) -1)/(N-1) ... (т. Е. к мощности L + 1, а не только к L).

Это можно показать следующим образом. Во-первых, принять нашу теорему:

1 + N^1 + N^2 + ... + N^L = (N^(L + 1) -1)/(N-1)

Multiply (N-1):

(N-1) (1 + N^1 + N^2 + ... + N^L) = N^(L + 1) -1.

Разверните левую сторону:

N^1 + N^2 + N^3 + ... + N^(L + 1) - 1 - Н^1 - N^2 - ... - N^L.

Все члены N^1 до N^L отменены, что оставляет N^(L + 1) - 1. Это наша правая сторона, поэтому начальное равенство истинно.