Каково общее количество узлов в полном k-арном дереве в терминах количества листьев?
Я делаю уникальную форму кодирования Хаффмана, и я создаю k-ary (в данном конкретном случае, 3-арное) дерево, полное (каждый node будет иметь 0 или k детей), и я знаю сколько листьев у него будет, прежде чем я его построю. Как вычислить общее количество узлов в дереве в терминах количества листьев?
Я знаю, что в случае полного бинарного дерева (2-арного) формула для этого равна 2L - 1, где L - количество листьев. Я хотел бы распространить этот принцип на случай k-арного дерева.
Ответы
Ответ 1
Подумайте о том, как доказать результат для полного двоичного дерева, и вы увидите, как это сделать в целом. Для полного двоичного дерева, например height 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 -ary ничего не меняется, но 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)
Ответ 2
Для любого k-арного дерева общее число узлов n = [(k ^ (h + 1)) - 1]/(h-1), где h - высота k-арного дерева.
Ex: - для полного двоичного дерева (k = 2) общее число. узлов = [(2 ^ (h + 1)) - 1]/(h-1).
Итак, для высоты 3 общий №. узлов будет 15.
Для полного тройного древовидного дерева (k = 3) общее число. узлов = [(3 ^ (h + 1)) - 1]/(h-1).
Итак, для высоты 3 общий №. узлов будет 40.
Ответ 3
Формула для 2L-1, о которой вы упоминали, - это поиск полного, полного и сбалансированного двоичного дерева: на последнем уровне у вас есть 2 ^ h листа, а на других уровнях: 1 + 2 + 4 +.... + 2 ^ (h-1) = 2 ^ h -1 листы. Когда вы "путаете" уровни в дереве и создаете неуравновешенный, то количество внутренних узлов, которые у вас есть, не изменяется.
В трехмерном дереве его та же логика: на последнем уровне у вас есть 3 ^ h листьев, а на других уровнях: 1 + 3 + 9 +.... + 3 ^ (h-1) = ( 3 ^ h -1)/2, это означает, что на 3-арном дереве у вас есть 1.5 * L - 0.5 листа (и это имеет смысл, потому что степень больше, вам нужно меньше внутренних узлов). Я так же и здесь, когда вы испортили уровни в дереве, вам все равно потребуется такое же количество внутренних узлов.
Надеюсь, что это поможет вам
