Calculadora de nodos del árbol de recursión

Las recurrencias de divide y vencerás de la forma T de n igual a a veces T de n entre b más el trabajo no recursivo aparecen en todo curso de algoritmos cuando se dibujan como árboles el merge sort, las particiones espaciales binarias o la recursión multiway. Los estudiantes necesitan un recuento fiable de cuántos nodos hay en cada nivel y hasta qué profundidad crece el árbol antes de que los subproblemas alcancen el caso base. Esta calculadora de nodos del árbol de recursión acepta el factor de ramificación a, la razón de reducción b y el tamaño de entrada raíz n, recorre el árbol hasta que el tamaño del subproblema sea como máximo uno, y devuelve el número de niveles, la altura, los totales de nodos y de hojas, la secuencia de nodos por nivel, los tamaños de subproblema y dos distribuciones fraccionarias del trabajo. Una asume coste unitario por nodo; la otra asume trabajo proporcional al tamaño del subproblema, como en el dibujo clásico del merge sort donde cada nivel completo sigue haciendo trabajo lineal en n.

Qué cuenta un árbol de recursión y cómo se definen los niveles

Un árbol de recursión es la imagen de cada subproblema que genera un algoritmo de divide y vencerás cuyo tiempo cumple T de n igual a a veces T de n entre b más f de n. La raíz representa la instancia original de tamaño n. Cada nodo interno tiene exactamente a hijos, cada uno resuelve un problema cuyo tamaño es el del padre dividido por b.

Los niveles se numeran desde cero en la raíz. En el nivel i hay a elevado a i nodos, y cada uno tiene tamaño de subproblema n dividido por b elevado a i, siempre que los tamaños sigan siendo reales y positivos. El recorrido continúa mientras el tamaño actual sea estrictamente mayor que uno; el primer nivel cuyo tamaño es menor o igual que uno se conserva como nivel de hojas de casos base y entonces se detiene.

Esa convención coincide con la condición de parada de los libros de texto al resolver entradas de tamaño constante de forma directa. La altura del árbol es el número de niveles menos uno, es decir el número de aristas en un camino de la raíz a una hoja. Los nodos hoja equivalen a a elevado a la altura cuando los tamaños llegan a uno en una potencia exacta y, en general, al recuento de nodos del último nivel registrado.

Los nodos internos son el total menos las hojas. Con factor de ramificación uno el árbol es una sola espina de longitud igual al número de divisiones sucesivas hasta que el tamaño es como máximo uno. Con factor mayor que uno la forma cerrada del total de nodos en L niveles es a elevado a L menos uno, todo ello entre a menos uno; este extremo lo recalcula sumando la serie geométrica para que tamaños fraccionarios y casos base tempranos sigan coherentes con el recorrido.

Dónde ayuda contar los nodos del árbol

Los cursos de algoritmos y las plataformas de tutoría usan una calculadora de nodos del árbol de recursión para que el alumnado compruebe profundidad y amplitud con a, b y n arbitrarios sin dibujar cientos de nodos a mano. Los generadores de exámenes necesitan un oráculo determinista que marque como incorrecto un recuento de hojas o de niveles alegado en lugar de aceptar conjeturas asintóticas vagas.

Las herramientas de preparación de entrevistas y los visualizadores de complejidad emparejan los arrays por nivel con gráficos para que los candidatos vean por qué el divide y vencerás equilibrado suele gastar el mismo trabajo en cada nivel cuando a es igual a b. Los cuadernos de ingeniería que prototipan divisores multiway o grafos de tareas en paralelo pueden validar el fan-out antes de escribir planificadores de producción. La validación fallida no consume saldo.