Número total de nodos en una estructura de datos de árbol?

Question

Tengo una estructura de datos de árbol que tiene L niveles de profundidad cada nodo tiene aproximadamente N nodos. Quiero calcular el número total de nodos en el árbol. Para hacer esto (creo) necesito saber qué porcentaje de los nodos tendrán hijos.

¿Cuál es el término correcto para esta relación de nodos hoja a nodos hoja en N?

¿Cuál es la fórmula para calcular el número total de nodos en los tres?

actualización Alguien mencionó factor de ramificación en una de la respuesta, pero luego desapareció. Creo que este era el término que estaba buscando. Entonces, ¿no debería una fórmula tener en cuenta el factor de bifurcación?

Actualización Debería haber dicho una estimación sobre una estructura de datos hipotética, ¡no la cifra exacta!

Answer 1

Bien, cada nodo tiene aproximadamente N subnodos y el árbol tiene L niveles de profundidad.

With 1 level, the tree has 1 node. 
With 2 levels, the tree has 1 + N nodes. 
With 3 levels, the tree has 1 + N + N^2 nodes. 
With L levels, the tree has 1 + N + N^2 + ... + N^(L-1) nodes. 

El número total de nodos es (N^L-1)/(N-1).

Ok, sólo un pequeño ejemplo por qué, es exponencial:

    [NODE] 
         | 
        /|\ 
        /| \ 
       /| \ 
       / | \ 
      [NODE] [NODE] [NODE] 
       | 
      /|\ 
      /| \ 

Answer 2

Si no conoce otra cosa que la profundidad del árbol, entonces su única opción para calcular el tamaño total es pasar y contarlos.

Answer 3

La fórmula para calcular la cantidad de nodos en profundidad L es: (Dado que hay N nodos raíz)

N ^L

Para calcular el número de todos los nodos que uno necesita para hacer esto para cada capa:

for depth in (1..L) 
    nodeCount += N ** depth 

Si solo hay 1 nodo raíz, reste 1 de L y agregue 1 al total de nodos.

Tenga en cuenta que si en un nodo la cantidad de hojas es diferente de la caja promedio, esto puede tener un gran impacto en su número. Cuanto más arriba en el árbol, más impacto.

 
    *    *     *   N ** 1 
    ***    ***    ***  N ** 2 
*** *** ***  *** *** ***  *** *** *** N ** 3 

Esta es la wiki de la comunidad, así que siéntete libre de alterar mi aterrador álgebra.

Answer 4

Si el árbol es de aproximadamente completa, es decir cada nivel tiene su asignación completa de los niños a excepción de los dos últimos, a continuación, tener entre N^(L-2) y N^(L-1) nodos de hojas y entre N^(L-1) y N^L nodos totales.

Si su árbol no está lleno, conocer el número de nodos de hoja no ayuda, ya que un árbol totalmente desequilibrado tendrá un nodo de hoja pero arbitrariamente muchos padres.

Me pregunto qué tan precisa es su afirmación 'cada nodo tiene sobre N nodos' - si conoce el factor de ramificación promedio, quizás pueda calcular el tamaño esperado del árbol.

Si puede encontrar la proporción de hojas en los nodos internos, y conoce el número promedio de hijos, puede aproximar esto como (n * ratio)^N = n. Esto no le dará su respuesta, pero me pregunto si alguien con mejores matemáticas que yo puede encontrar una manera de interponer L en esta ecuación y darle algo soluble.

Aún así, si quiere saber con precisión, debe recorrer la estructura del árbol y contar los nodos a medida que avanza.

Answer 5

Solo para corregir un error tipográfico en la primera respuesta: el número total de nodos para un árbol de profundidad L es (N^(L + 1) -1)/(N-1) ... (es decir, a la potencia L + 1 en lugar de solo a L).

Esto se puede mostrar de la siguiente manera. En primer lugar, tomar nuestro teorema:

1 + N^1 + N^2 + ... + N^L = (N^(L + 1) -1)/(N-1)

Multiply ambos lados por (N-1):

(N-1) (1 + N^1 + N^2 + ... + N^L) = N^(L + 1) -1.

Expand el lado izquierdo:

N^1 + N^2 + N^3 + ... + N^(L + 1) - 1 - N^1 - N^2 - ... - N^L.

Todos los términos N^1 a N^L se cancelan, lo que deja N^(L + 1) - 1. Este es nuestro lado derecho, por lo que la igualdad inicial es verdadera.