¿Cuál es el número total de nodos en un árbol k-ary completo, en términos del número de hojas?

Question

Estoy haciendo una forma única de codificación Huffman, y estoy construyendo un árbol k-ary (en este caso particular, 3-ary) que está lleno (cada nodo tendrá 0 o k hijos), y sé cuántas hojas tendrá antes de que yo lo construya. ¿Cómo calculo el número total de nodos en el árbol en términos del número de hojas?

Sé que en el caso de un árbol binario completo (2-ary), la fórmula para esto es 2L - 1, donde L es el número de hojas. Me gustaría extender este principio al caso de un árbol k-ary.

Answer 1

Piense en cómo demostrar el resultado de un árbol binario completo, y verá cómo hacerlo en general. Para el árbol binario completo, por ejemplo de la altura h, el número de nodos N es

N = 2^{h+1} - 1

¿Por qué? Como el primer nivel tiene nodos 2^0, el segundo nivel tiene nodos 2^1 y, en general, el k tiene nodos 2^{k-1}. La adición de estos para un total de h+1 niveles (por lo que la altura h) da

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

El número total de hojas L es sólo el número de nodos en el último nivel, por lo L = 2^h. Por lo tanto, por sustitución, obtenemos

N = 2*L - 1 

Durante k árboles ary, nada cambia, pero el 2. Así

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

L = k^h 

y por lo que un poco de álgebra le puede dar el último paso para obtener

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

Answer 2

La fórmula para 2L-1 que mencionaste proviene de buscar en un árbol binario completo, completo y equilibrado: en el último nivel tienes 2 hojas de^h, y en los otros niveles: 1 + 2 + 4 +. ... + 2^(h-1) = 2^h -1 hojas. Cuando "desordenan" niveles en el árbol y crean uno desequilibrado, la cantidad de nodos internos que tiene no cambia.

En el árbol 3-ary es la misma lógica: en el último nivel tiene 3 hojas de^h, y en los otros niveles: 1 + 3 + 9 + .... + 3^(h-1) = (3^h -1)/2, eso significa que en un árbol 3-ary tienes 1.5 * L - 0.5 hojas (y esto hace sentido - porque el grado es más grande, necesitas menos nodos internos). También creo que aquí, cuando arruinas los niveles en el árbol, necesitarás la misma cantidad de nodos internos.

esperanza que le ayuda

Answer 3

Para cualquier árbol k-ario el número total de nodos n = [(k^(h + 1)) - 1]/(h-1) donde h es la altura del árbol k-ary.

Ej .: - Para árbol binario completo (k = 2) total no. de nodos = [(2^(h + 1)) - 1]/(h-1).

Así que para la altura 3 el total de no. de nodos será 15.

Para árbol ternario completo (k = 3) total no. de nodos = [(3^(h + 1)) - 1]/(h-1).

Así que para la altura 3 el total de no. de nodos será 40.