Блог

Я использую уникальную форму кодирования Хаффмана и создаю k-арное (в данном конкретном случае 3-арное) дерево, которое является полным (у каждого узла будет 0 или k дочерних элементов), и я знаю, сколько у него будет листьев, прежде чем я его построю. Как мне вычислить общее количество узлов в дереве с точки зрения количества листьев?

Я знаю, что в случае полного двоичного дерева (2-арного) формула для этого равна 2L — 1, где L — количество листьев. Я хотел бы распространить этот принцип на случай k-арного дерева.

Подумайте о том, как доказать результат для полного двоичного дерева, и вы увидите, как это сделать в целом. Для полного двоичного дерева, скажем, высоты h , количество узлов N равно

N = 2^{h 1} - 1

Почему? Поскольку на первом уровне есть 2^0 узлы, на втором уровне есть 2^1 узлы, и, в общем случае, на k -м уровне есть 2^{k-1} узлы. Суммируя их для получения общего количества h 1 уровней (таким образом, высоты h ), получаем

 N = 1   2   2^2   2^3   ...   2^h = (2^{h 1} - 1) / (2 - 1) = 2^{h 1} - 1
  

Общее количество листьев L — это просто количество узлов на последнем уровне, так что L = 2^h . Следовательно, путем подстановки мы получаем

 N = 2*L - 1
  

Для k -арного дерева ничего не меняется, кроме 2 . Итак

 N = 1   k   k^2   k^3   ...   k^h = (k^{h 1} - 1) / (k - 1)

L = k^h
  

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

 N = (k*L - 1) / (k-1)
  

Формула для 2L-1, о которой вы упомянули, получена из рассмотрения полного, завершенного и сбалансированного двоичного дерева: на последнем уровне у вас есть 2 ^ h листьев, а на других уровнях: 1 2 4 …. 2^( h-1) = 2 ^ h -1 листа. Когда вы «перепутаете» уровни в дереве и создадите несбалансированный, количество имеющихся у вас внутренних узлов не изменится.

В 3-арном дереве та же логика: на последнем уровне у вас есть 3 ^ h листьев, а на других уровнях: 1 3 9 …. 3^( h-1) = (3 ^ h -1 ) / 2, это означает, что в 3-арном дереве у вас есть 1,5 * L — 0,5 листа (и это имеет значение — поскольку степень больше, вам нужно меньше внутренних узлов). Я думаю, что и здесь, когда вы перепутаете уровни в дереве, вам все равно понадобится такое же количество внутренних узлов.

Надеюсь, что это поможет вам

Проблема более общая, и результат справедлив для любого полного k-арного дерева (не обязательно полного).

Мы могли бы доказать это и с помощью теории графов. Обратите внимание на следующий рисунок, что в полном k-арном дереве есть только 3 типа узлов с n = I L узлов, т. Е. с I внутренними и L конечными узлами:

1. 1 корневой узел со степенью ровно k
2. (I-1) внутренние узлы, каждый со степенью ровно k 1 (поскольку root также является внутренним узлом)
3. L конечных узлов, каждый со степенью 1

Теперь, если мы используем следующие два факта из теории графов:

5. Дерево с n узлами имеет n-1 ребер
6. Сумма степеней узлов в любом графе в два раза превышает количество ребер в графе

Объединяя все вышесказанное, мы получаем,

Сумма степеней всех узлов в дереве

= 1.k (I-1)(k 1) L.1 = 2 (I L-1)

=> L = (k-1)I 1

Для любого k-арного дерева общее количество узлов n = [(k ^ (h 1))-1]/(h-1) где h — высота k-арного дерева.

Пример:- Для полного двоичного дерева (k = 2) общее количество узлов = [(2 ^(h 1))-1]/(h-1).

Таким образом, для высоты 3 общее количество узлов будет равно 15.

Для полного троичного дерева (k = 3) общее количество узлов = [(3 ^(h 1))-1]/(h-1).

Таким образом, для высоты 3 общее количество узлов будет равно 40.