Árboles N-arios y Representación con Vectores

Parte de: Java para Principiantes › Árboles N-arios y representación con vectores

Modelo del Mundo Real

Árboles N-arios: Más Allá del Binario

A diferencia de un árbol binario, un nodo puede tener 0, 1, 2… K hijos. Un sistema de archivos, el DOM de una página o una jerarquía de categorías son árboles generales.

El grado (cantidad de hijos) no está acotado ni es uniforme: home tiene 2 hijos, etc/ tiene 5, mientras que bin/ y var/ son hojas con 0 hijos. Esa asimetría es imposible de modelar con un árbol binario.

Dilema de Implementación

Array Fijo de Hijos vs Lista Dinámica

Nodo[] hijos = new Nodo[MAX] reserva memoria fija por adelantado: brutal en nodos hoja. List<Nodo> hijos crece según necesidad, a costa de la sobrecarga de un objeto ArrayList por nodo.

Opción A · Array Fijo Nodo[] hijos = new Nodo[8]

Nodo etc/ (5 hijos reales) reserva 8 punteros por adelantado:

nginx ssh hosts resolv.conf ssl null null null

3 / 8 celdas desperdiciadas (37,5%)

Nodo hoja bin/ (0 hijos) reserva las mismas 8 celdas:

null null null null null null null null

8 / 8 celdas desperdiciadas (100%)

Opción B · Lista Dinámica List<Nodo> hijos = new ArrayList<>()

Nodo etc/ (5 hijos): la lista crece exactamente a 5 elementos.

nginx ssh hosts resolv.conf ssl

0 celdas desperdiciadas, pero +overhead de objeto ArrayList por nodo

Nodo hoja bin/ (0 hijos): la lista queda vacía.

(vacía)

0 celdas desperdiciadas, aún así carga un objeto ArrayList por hoja

Transformación Estructural

Primer Hijo / Siguiente Hermano (LCRS)

Cada nodo solo necesita dos referencias: primerHijo (el hijo más a la izquierda) y siguienteHermano (el próximo nodo a su derecha en el mismo nivel). Deslizá para transformar el árbol N-ario en un árbol binario estricto.

Vista N-aria Vista Binaria (LCRS)

primerHijo siguienteHermano

En 0%: árbol N-ario tradicional, cada nodo con una lista de hijos. En 100%: solo el hijo más izquierdo cuelga hacia abajo (primerHijo); los demás se encadenan hacia la derecha (siguienteHermano), formando un árbol binario estricto.

Recorrido en Profundidad

Preorden: el Padre Antes que sus Hijos

Se visita el nodo, luego se recorre cada subárbol de izquierda a derecha. El mismo recorrido, aplicado sobre la versión LCRS, produce exactamente la misma secuencia.

Árbol N-ario

Árbol LCRS (binario)

1: A 2: B 3: E 4: F 5: C 6: D

Representación Compacta en Memoria

Vector de Padres: int[] padre

Se numeran los nodos de 0 a N-1. padre[i] guarda el índice del padre del nodo i (la raíz vale -1). Hacé click en cualquier celda de la tabla para iluminar la relación en el árbol.

i	0	1	2	3	4
padre[i]	-1	0	0	0	1

Hacé click en un índice de la tabla para ver su relación padre-hijo.

Algoritmos sobre el Vector

Subir a la Raíz: O(1) vs Listar Hijos: O(N)

Subir hacia la raíz es instantáneo: while (p != -1) p = padre[p];. Listar los hijos de un nodo requiere barrer todo el array buscando padre[j] == nodo, en O(N).

Nodo seleccionado:

0-1

Elegí un nodo y una operación.

Árboles Completos y Aritmética de Índices

Árbol Ternario Completo: Sin Punteros, Solo Fórmulas

Si el árbol es K-ario completo, la posición de cada nodo se calcula: hijo j-ésimo de i está en 3i + j; el padre de i está en ⌊(i-1) / 3⌋. Hacé click en un nodo o una celda del array.

hijo_j(i) = 3×i + j (j = 1, 2, 3) padre(i) = ⌊(i − 1) / 3⌋

Nodo 1: padre = 0 · hijos = 4, 5, 6 (3×1+1, 3×1+2, 3×1+3)