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

Ответ 1

Хорошо, каждый node имеет около 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]
              |
             /|\
            / | \

Ответ 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. Это наша правая часть, поэтому исходное равенство верно.

Ответ 3

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

N ^L

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

Ответ 6

Оценка Кнута [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