data-structures - recorrido - profundidad de un arbol

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 que cada nodo tiene sobre 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 de hojas a nodos de hojas en N?

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

Actualizar Alguien mencionó el factor de ramificación en una de las respuestas, 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

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

N ^L

Para calcular la cantidad de todos los nodos, se necesita 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 recuento total de nodos.

Tenga en cuenta que si en un nodo la cantidad de hojas es diferente de la del caso 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 wiki de la comunidad, así que siéntete libre de alterar mi espantoso álgebra.

Answer 2

Si no sabes nada más que la profundidad del árbol, entonces tu única opción para calcular el tamaño total es pasar y contarlos.

Answer 3

Si su árbol está aproximadamente lleno , es decir, cada nivel tiene su complemento completo de niños, excepto los dos últimos, entonces tiene 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 iterar sobre la estructura del árbol y contar los nodos a medida que avanza.

Answer 4

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 L).

Esto se puede demostrar de la siguiente manera. Primero, toma nuestro teorema:

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

Multiplica ambos lados por (N-1):

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

Expande 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.

Answer 5

De acuerdo, 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, solo un pequeño ejemplo de por qué, es exponencial:

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