AALIE

Método del Árbol de Recursión

Construcción, análisis por niveles y resolución de recurrencias mediante árboles de llamadas.

Cuándo aplica el método del árbol

El método del árbol de recursión representa una ecuación de recurrencia como un árbol de llamadas. Cada nodo representa una llamada recursiva, cada nivel representa una profundidad de expansión y el costo total se obtiene sumando el costo de todos los niveles más el costo de las hojas.

Aplica pedagógicamente a cualquier ecuación de recurrencia, pero es especialmente útil cuando el Teorema Maestro no aplica, por ejemplo en recurrencias no balanceadas como $T (n) = T (n /3) + T (2 n /3) + c n$ , o cuando la ecuación tiene más de un llamado recursivo de distinto tamaño.

Cuándo usar Teorema Maestro y cuándo usar Árbol de Recursión

Situación	Método recomendado	Razón
$T (n) = a T (n / b) + f (n)$ y encaja en un caso del Maestro	Teorema Maestro	Es más directo y evita dibujar todo el árbol.
Subproblemas de distinto tamaño	Árbol de Recursión	El Teorema Maestro básico exige subproblemas homogéneos.
El resultado del Maestro no es intuitivo para el estudiante	Árbol como justificación visual	El árbol muestra de dónde sale cada término de la suma.
Recurrencia de resta con ramificación	Árbol o ecuación característica	El árbol permite visualizar crecimiento exponencial por profundidad.

Modelo mental del árbol

La raíz representa el primer ambiente de ejecución: la llamada original $T (n)$ . Sus hijos representan las llamadas recursivas que esa raíz dispara. Cada hijo vuelve a generar otros hijos hasta que se alcanza el caso base.

Qué se paga en cada nodo

El costo escrito dentro de un nodo es el trabajo no recursivo: dividir, comparar, combinar, imprimir o ejecutar instrucciones locales. Las llamadas recursivas no se cuentan dentro de $f (n)$ ; se expanden como hijos del árbol.

Esqueleto de árbol para T(n)=2T(n/2)+f(n)

Renderizando diagrama...

Paso a paso — Árbol de Recursión

Detectar la recurrencia y extraer parámetros. Identifica cuántos llamados hay, el factor de reducción o resta, y el costo por nodo $f (n)$ . Ejemplo: $T (n) = 2 T (n /2) + c n$ tiene $a = 2$ , $b = 2$ y $f (n) = c n$ .
Dibujar los primeros 3 niveles del árbol. La raíz representa el primer ambiente. Su costo en el nodo es $f (n)$ . Cada hijo tiene tamaño $n / b$ y costo $f (n / b)$ . Dibujar tres niveles suele bastar para ver el patrón.
Construir el modelo de un nivel genérico i. Para el nivel $i$ : nodos $a^{i}$ , tamaño por nodo $n / b^{i}$ , costo por nodo $f (n / b^{i})$ y costo total $a^{i} f (n / b^{i})$ .
Determinar la altura del árbol. Si el caso base es $T (1)$ y el tamaño se divide por $b$ , se resuelve $n / b^{h} = 1$ , por lo tanto $h = lo g_{b} n$ . El número de niveles es $h + 1$ .
Costear las hojas. En el nivel $h$ hay $a^{h} = a^{l o g_{b} n} = n^{l o g_{b} a}$ hojas. Si cada hoja cuesta constante, el costo total de hojas es proporcional a $n^{l o g_{b} a}$ .
Construir y simplificar la suma total. Se suman los costos de todos los niveles internos más las hojas.
Identificar qué domina. Compara niveles intermedios contra hojas y raíz para decidir el orden final.

Suma total estándar

T (n) = i = 0 \sum h - 1 a^{i} f (\frac{n}{b ^{i}}) + n^{l o g_{b} a}

Esta fórmula suma el trabajo en todos los niveles del árbol. El término $i$ representa el nivel actual, desde la raíz (0) hasta justo antes de las hojas (h-1). En cada nivel, tenemos $a^{i}$ nodos (factor de ramificación elevado al nivel), cada uno procesando un subproblema de tamaño $n / b^{i}$ . La altura del árbol $h$ determina cuántos niveles recorremos, y el término final $n^{l o g_{b} a}$ contabiliza el costo total de las hojas en el nivel base.

Modelo del nivel genérico i para recurrencias balanceadas

Elemento del nivel i	Expresión	Interpretación
Número de nodos	$a^{i}$	Cada nodo genera a hijos por nivel.
Tamaño por nodo	$\frac{n}{b ^{i}}$	Cada nivel divide el tamaño por b.
Costo por nodo	$f (\frac{n}{b ^{i}})$	Trabajo local de un nodo de tamaño n/b^i.
Costo total del nivel	$a^{i} f (\frac{n}{b ^{i}})$	Suma del trabajo local de todos los nodos del nivel.

Patrones de dominancia

Después de construir la suma total, el paso decisivo es identificar qué parte del árbol domina el crecimiento asintótico.

Patrones de dominancia en árboles de recursión

Patrón	Señal	Resultado típico	Intuición
Dominan las hojas	El costo por nivel crece geométricamente al bajar.	$Θ (n^{l o g_{b} a})$	Hay demasiadas hojas o demasiada ramificación.
Todos los niveles cuestan igual	Cada nivel cuesta, por ejemplo, cn.	$Θ (n lo g n)$	Se paga el mismo costo por cada nivel y hay log n niveles.
Domina la raíz	Los costos decrecen rápido al bajar.	$Θ (f (n))$	El trabajo local inicial pesa más que todo lo que ocurre debajo.

Cuidado

No decidas el resultado mirando solo la cantidad de hojas. Un árbol puede tener muchas hojas, pero si el costo por nivel cae suficientemente rápido, la raíz puede dominar. Siempre suma o compara el costo por nivel.

Ejemplo 1 — T(n)=2T(n/2)+cn

Resolver $T (n) = 2 T (n /2) + c n$ , con $T (1) = 1$ . Este patrón corresponde a Merge Sort o al mejor caso de Quicksort.

Primeros niveles de T(n)=2T(n/2)+cn

Nivel	Nodos	Costo por nodo	Costo total del nivel
0	1	$c n$	$c n$
1	2	$c (n /2)$	$2 \cdot c (n /2) = c n$
2	4	$c (n /4)$	$4 \cdot c (n /4) = c n$
$i$	$2^{i}$	$c (n / 2^{i})$	$2^{i} \cdot c (n / 2^{i}) = c n$

Árbol de los primeros niveles

Renderizando diagrama...

Parámetros

a = 2, b = 2, f (n) = c n

Nivel genérico

Costo nivel i = 2^{i} \cdot c (\frac{n}{2 ^{i}}) = c n

Altura

\frac{n}{2 ^{h}} = 1 \Rightarrow h = lo g_{2} n

Número de niveles

lo g_{2} n + 1

Hojas

2^{l o g_{2} n} = n hojas, cada una de costo constante

Costo hojas

Θ (n)

Suma total

T (n) = c n (lo g_{2} n + 1) = c n lo g_{2} n + c n

Resultado

T (n) = Θ (n lo g n)

Resultado

$T (n) = c n lo g_{2} n + c n$ y por tanto $T (n) \in Θ (n lo g n)$ . El crecimiento es linealítmico.

Ejemplo 2 — T(n)=2T(n−1)+1

Resolver $T (n) = 2 T (n - 1) + 1$ , con $T (1) = 1$ . Este es el patrón de Torres de Hanói: resta y serás vencido.

Primeros niveles de T(n)=2T(n−1)+1

Nivel	Nodos	Costo por nodo	Costo total del nivel
0	1	1	1
1	2	1	2
2	4	1	4
3	8	1	8
$i$	$2^{i}$	1	$2^{i}$

Árbol inicial de Torres de Hanói

Renderizando diagrama...

Nivel genérico

Costo nivel i = 2^{i}

Altura

h = n - 1 porque se resta 1 hasta llegar a T (1)

Suma total

T (n) = i = 0 \sum n - 1 2^{i}

Serie geométrica

i = 0 \sum n - 1 2^{i} = 2^{n} - 1

Resultado

T (n) = 2^{n} - 1 \in Θ (2^{n})

Resultado

$T (n) = 2^{n} - 1$ y por tanto $T (n) \in Θ (2^{n})$ . El crecimiento es exponencial.

Ejemplo enriquecido — T(n)=T(n/3)+T(2n/3)+cn

Un caso donde el árbol de recursión es especialmente útil es en recurrencias no balanceadas como: $T (n) = T (n /3) + T (2 n /3) + c n$ .

Por qué no aplica Teorema Maestro básico

El Teorema Maestro básico requiere subproblemas homogéneos de tamaño $n / b$ . Aquí los hijos tienen tamaños diferentes: $n /3$ y $2 n /3$ .

Árbol no balanceado inicial

Renderizando diagrama...

Costo raíz

c n

Costo nivel 1

c (n /3) + c (2 n /3) = c n

Observación

La suma de tama \overset{n}{˜} os de subproblemas en cada nivel completo es n

Costo por nivel

Θ (n)

Rama más larga

n (\frac{2}{3})^{h} = 1 \Rightarrow h = lo g_{3/2} n

Costo de niveles

Θ (n) \cdot Θ (lo g n) = Θ (n lo g n)

Resultado

T (n) = Θ (n lo g n)

Cuidado con las hojas

En árboles no balanceados no todas las ramas tienen la misma altura. Para una explicación inicial basta usar la rama más larga para acotar el número de niveles y observar que el costo por nivel completo es lineal. Para una demostración formal fina se usa sustitución o el teorema Akra–Bazzi, que está fuera del alcance de este módulo.

Ejemplos enriquecidos de dominancia

Ejemplos rápidos de dominancia

Recurrencia	Costo nivel i	Qué domina	Resultado
$T (n) = 4 T (n /2) + n$	$4^{i} \cdot \frac{n}{2 ^{i}} = n \cdot 2^{i}$	Hojas / niveles bajos	$Θ (n^{2})$
$T (n) = 2 T (n /2) + n$	$2^{i} \cdot \frac{n}{2 ^{i}} = n$	Todos los niveles	$Θ (n lo g n)$
$T (n) = 2 T (n /2) + n^{2}$	$2^{i} \cdot (\frac{n}{2 ^{i}})^{2} = \frac{n ^{2}}{2 ^{i}}$	Raíz / niveles superiores	$Θ (n^{2})$

Detalle — T(n)=4T(n/2)+n

Nivel genérico

Costo nivel i = 4^{i} \cdot \frac{n}{2 ^{i}} = n 2^{i}

Altura

h = lo g_{2} n

Último nivel interno

n 2^{l o g_{2} n} = n^{2}

Suma geométrica

i = 0 \sum l o g_{2} n n 2^{i} = n (2^{l o g_{2} n + 1} - 1) = Θ (n^{2})

Detalle — T(n)=2T(n/2)+n²

Nivel genérico

Costo nivel i = 2^{i} \cdot (\frac{n}{2 ^{i}})^{2} = \frac{n ^{2}}{2 ^{i}}

Suma geométrica decreciente

i = 0 \sum l o g_{2} n \frac{n ^{2}}{2 ^{i}} \leq 2 n^{2}

Resultado

T (n) = Θ (n^{2})

Errores típicos

Errores frecuentes en el método del árbol

Error	Por qué está mal	Corrección
Contar solo nodos y olvidar el costo por nodo	El costo total no depende solo de cuántas llamadas hay.	Multiplicar nodos por costo por nodo en cada nivel.
Usar $lo g_{b} n$ en recurrencias de resta	Si el tamaño pasa de n a n−1, la altura no es logarítmica.	Para $T (n - b)$ , la altura suele ser lineal en n.
Olvidar las hojas	En algunos árboles las hojas dominan el costo total.	Agregar explícitamente el costo de hojas a la suma.
Suponer que todos los niveles cuestan igual	Eso solo ocurre en casos específicos como $2 T (n /2) + c n$ .	Calcular el costo genérico $a^{i} f (n / b^{i})$ .
Forzar una forma balanceada en un árbol no balanceado	Recurrencias como $T (n /3) + T (2 n /3)$ no tienen todos los hijos del mismo tamaño.	Analizar suma de tamaños por nivel y altura de la rama más larga.
Declarar resultado exacto cuando solo se demostró orden	Muchas sumas se simplifican asintóticamente.	Distinguir entre forma exacta y conclusión $Θ (\cdot)$ .

Resumen operativo

Receta mínima

Escribir la recurrencia y separar llamados recursivos de costo local.
Dibujar raíz, nivel 1 y nivel 2.
Encontrar el patrón del nivel genérico.
Calcular la altura hasta el caso base.
Costear hojas.
Sumar niveles internos más hojas.
Identificar término dominante y concluir en notación $Θ$ .

Fórmulas clave

Nivel genérico balanceado

Costo nivel i = a^{i} f (\frac{n}{b ^{i}})

Altura por división

\frac{n}{b ^{h}} = 1 \Rightarrow h = lo g_{b} n

Hojas

a^{h} = a^{l o g_{b} n} = n^{l o g_{b} a}

Suma total

T (n) = i = 0 \sum h - 1 a^{i} f (\frac{n}{b ^{i}}) + n^{l o g_{b} a}