math - resueltos - ¿Cuál es el número total de nodos en un árbol k-ary completo, en términos del número de hojas?
recorrido de arboles binarios ejercicios resueltos (3)
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 niños), y sé cuántas hojas tendrá tener antes de que 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.
La fórmula para 2L-1 que mencionaste viene 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 tiene la misma lógica: en el último nivel tienes 3 hojas de 3 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.
Espero que te ayude
Para cualquier árbol k-ary, la cantidad total de nodos n = [(k ^ (h + 1)) - 1] / (h-1) donde h es la altura del árbol k-aria.
Ej .: para árbol binario completo (k = 2) total no. de nodos = [(2 ^ (h + 1)) - 1] / (h-1).
Entonces para la altura 3 el total no. de nodos será 15.
Para árbol de árbol ternario completo (k = 3) total no. de nodos = [(3 ^ (h + 1)) - 1] / (h-1).
Entonces para la altura 3 el total no. de nodos será 40.
Piense en cómo probar el resultado de un árbol binario completo, y verá cómo hacerlo en general. Para el árbol binario completo, digamos de altura h , la cantidad de nodos N es
N = 2^{h+1} - 1
¿Por qué? Como el primer nivel tiene 2^0 nodos, el segundo nivel tiene 2^1 nodos y, en general, el k ésimo nivel tiene 2^{k-1} nodos. Sumar 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 solo el número de nodos en el último nivel, entonces L = 2^h . Por lo tanto, por sustitución, obtenemos
N = 2*L - 1
Para un árbol kary, nada cambia excepto el 2 . Asi que
N = 1 + k + k^2 + k^3 + ... + k^h = (k^{h+1} - 1) / (k - 1)
L = k^h
así que un poco de álgebra puede llevarte al último paso para obtener
N = (k*L - 1) / (k-1)