Árboles con Raíz en Teoría de Grafos

1. ¿Qué es un Árbol con Raíz?

En teoría de grafos, un árbol es un grafo conexo sin ciclos. Un árbol con raíz es simplemente un árbol en el que se ha elegido un vértice especial como raíz. Esa única elección da a todos los demás nodos un claro sentido de "arriba" (hacia la raíz) y "abajo" (alejándose de ella), convirtiendo un árbol simple en una jerarquía.

Un dato útil: un árbol con n nodos tiene siempre exactamente n - 1 aristas, y existe exactamente un camino entre dos nodos cualesquiera, ni más ni menos.

2. Terminología Clave

• Raíz: el nodo superior; el único sin padre.
• Padre / Hijo: si una arista conecta A (más cerca de la raíz) con B, entonces A es el padre y B es el hijo.
• Hermanos: nodos que comparten el mismo padre.
• Hoja: un nodo sin hijos, un "extremo" del árbol.
• Nodo interno: cualquier nodo con al menos un hijo.
• Ancestro / Descendiente: nodos en el camino hacia la raíz / hacia abajo desde un nodo.
• Profundidad: el número de aristas desde la raíz hasta un nodo. La raíz tiene profundidad 0.
• Altura: la distancia más larga desde un nodo hasta una hoja. La altura del árbol es la altura de su raíz.
• Subárbol: un nodo junto con todos sus descendientes.

3. Árboles con y sin Raíz

Un árbol sin raíz solo describe qué nodos están conectados: no hay arriba ni abajo. En cuanto eliges una raíz, el mismo conjunto de aristas adquiere dirección: ahora se entiende que las aristas apuntan alejándose de la raíz, así que un árbol con raíz se comporta como un tipo especial de grafo dirigido. Elegir una raíz distinta produce una jerarquía diferente a partir del mismo árbol subyacente.

4. Cómo se Representan los Árboles con Raíz

Hay tres formas habituales de almacenar un árbol con raíz en código:

• Arreglo de padres: guarda el padre de cada nodo en un arreglo (padre[i]). Compacto e ideal para operaciones de "subir hasta la raíz".
• Listas de hijos: cada nodo tiene una lista de sus hijos, la representación más flexible para los recorridos.
• Hijo-izquierdo / hermano-derecho: una codificación de estilo binario que almacena cualquier árbol n-ario con solo dos punteros por nodo.

5. Tipos de Árboles con Raíz

• Árbol binario: cada nodo tiene como máximo dos hijos, uno "izquierdo" y uno "derecho".
• Árbol binario de búsqueda (BST): un árbol binario mantenido en orden, de modo que las búsquedas toman O(log n) cuando está equilibrado.
• Árbol n-ario: los nodos pueden tener cualquier número de hijos, como una carpeta del sistema de archivos.
• Árboles equilibrados (AVL, rojo-negro, B-árboles) mantienen automáticamente su altura pequeña para garantizar operaciones rápidas.

6. Recorrer un Árbol con Raíz

Visitar todos los nodos se llama recorrido, y hay dos grandes familias:

• En profundidad (DFS): baja lo más posible antes de retroceder. En árboles binarios tiene las variantes preorden, inorden y postorden.
• En anchura (BFS): visita todos los nodos de un nivel antes de bajar, también llamado recorrido por niveles.

Si esto te suena, es porque son las mismas estrategias usadas en grafos generales. Consulta nuestro análisis de BFS vs DFS.

7. Aplicaciones del Mundo Real

• Sistemas de archivos: carpetas y archivos forman un árbol con raíz, con el directorio raíz en la cima.
• El DOM de HTML: cada página web es un árbol con raíz de elementos, incluida la que estás leyendo.
• Bases de datos: los B-árboles y B+-árboles impulsan los índices que aceleran las consultas.
• Compiladores: el código fuente se analiza en un árbol de sintaxis abstracta (AST).
• Árboles de decisión y montículos: los modelos de aprendizaje automático y las colas de prioridad se construyen sobre árboles con raíz.