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

Question

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

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

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

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

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

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

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

Это можно показать следующим образом. Сначала возьмем нашу теорему:

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

Умножьте обе стороны на (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 - N ^ 1 - N ^ 2 - ... - N ^ L.

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

Answer 3

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

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

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

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

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

Answer 4

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

N ^L

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

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

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

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

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

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

Answer 5

Оценка Кнута [1], [2] является точечной оценкой , которая нацелена на количество узлов в произвольном конечном дереве без необходимости проходить через все узлы и даже если дерево не сбалансировано , Оценка Кнута является примером объективной оценки; ожидаемое значение оценки Кнута будет числом узлов в дереве. С учетом вышесказанного оценка Кнута может иметь большую дисперсию, если рассматриваемое дерево не сбалансировано, но в вашем случае, поскольку каждый узел будет иметь около N дочерних элементов, я не думаю, что дисперсия оценки Кнута должна быть слишком большой. Эта оценка особенно полезна, когда кто-то пытается измерить количество времени, которое потребуется, чтобы выполнить поиск методом грубой силы.

Для следующих функций мы будем предполагать, что все деревья представлены в виде списков списков. Например, [] обозначает дерево с одним узлом, а [[],[[],[]]] обозначает дерево с 5 узлами и 3 листьями (узлы в дереве находятся в однозначном соответствии с левыми скобками). Следующие функции написаны на языке GAP.

Функция simpleestimate выдает на выходе оценку количества узлов в дереве tree. Идея simpleestimate заключается в том, что мы случайным образом выбираем путь x_0, x_1, ..., x_n от корня x_0 дерева до листа x_n. Предположим, что у x_i есть преемники a_i. Тогда simpleestimate вернет 1 + a_1 + a_1 * a_2 + ... + a_1 * a_2 *… * a_n.

point:=tree; prod:=1; count:=1; list:=[]; 
while Length(point)>0 do prod:=prod*Length(point); count:=count+prod; point:=Random(point); od;
return count; end;

Функция estimate просто выдаст среднее арифметическое оценок, полученных при многократном применении функции simpleestimate(tree) samplesize.

estimate:=function(samplesize,tree) local count,i; 
count:=0; 
for i in [1..samplesize] do count:=count+simpleestimate(tree); od; 
return Float(count/samplesize); end;

Пример: simpleestimate([[[],[[],[]]],[[[],[]],[]]]); возвращает 15 в то время как estimate(10000,[[[],[[],[]]],[[[],[]],[]]]); возвращает 10.9608 (а дерево на самом деле имеет 11 узлов).

1. Оценка размера дерева поиска. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.5569&rep=rep1&type=pdf

2. Оценка эффективности программ возврата. Дональд Э. Кнут http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/S0025-5718-1975-0373371-6.pdf

Answer 6

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