Каково общее количество узлов в полном k-арном дереве с точки зрения количества листьев?

Question

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

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

Answer 1

Подумайте, как доказать результат для полного бинарного дерева, и вы увидите, как это сделать в целом. Для полного двоичного дерева, скажем, высоты 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)

Answer 2

Для любого 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.

Answer 3

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

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

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