Árboles y recorridos
Qué es un árbol
- Grafo conexo y sin ciclos.
- Con n vértices tiene exactamente n menos uno aristas.
- Entre dos nodos cualesquiera hay un único camino.
Árbol enraizado
Al designar un nodo como raíz, todo el árbol cobra dirección: cada nodo tiene un padre hacia la raíz e hijos que se alejan de ella. Las hojas son los nodos sin hijos.
Altura y profundidad
- La profundidad de un nodo es su distancia a la raíz.
- La altura del árbol es la máxima profundidad alcanzada.
- Estas medidas resumen lo «hondo» que es el árbol.
Subárboles y recursión
Cada hijo es raíz de un subárbol con la misma estructura que el todo. Esa autorreferencia hace que los árboles se procesen de forma natural con funciones recursivas.
Recorrido en profundidad
El recorrido en profundidad (DFS) se hunde por una rama hasta el final antes de retroceder y probar la siguiente. Explora lejos y pronto, y se implementa con una pila o con recursión.
Recorrido en amplitud
El recorrido en amplitud (BFS) visita nivel a nivel, de cerca de la raíz hacia fuera. Es el aliado natural para encontrar el camino más corto en número de aristas, y usa una cola.
Cuándo usar cada recorrido
- DFS: explorar todo el árbol, detectar ciclos, ordenar dependencias.
- BFS: alcanzar lo más cercano primero, caminos mínimos por tramos.
- La elección depende de la pregunta, no de la moda.
Árboles binarios y de decisión
- Un árbol binario tiene como mucho dos hijos por nodo.
- Los árboles de decisión particionan datos preguntando por características.
- Son modelos interpretables de clasificación y regresión.
Árboles en datos
- Sistemas de ficheros y menús jerárquicos son árboles.
- Estructuras de índice y de búsqueda organizan datos en árbol.
- La jerarquía de un organigrama o de una taxonomía se modela así.
Propiedades que conviene recordar
- Un grafo es árbol si es conexo y sin ciclos, o si hay un único camino entre cada par.
- Quitar cualquier arista de un árbol desconecta dos partes.
- Añadir cualquier arista crea exactamente un ciclo.
Errores frecuentes
- Confundir el recorrido en profundidad con el en amplitud y sus estructuras.
- Olvidar el caso base en una función recursiva sobre subárboles.
- Asumir que todo grafo conexo es árbol cuando tiene ciclos.
Ejemplo resuelto: recorrer un árbol
Dado un árbol de carpetas, recórrelo para listar primero todo el contenido de cada carpeta antes de pasar a la siguiente hermana.
- Arranca en la raíz, la carpeta principal.
- Aplica profundidad: baja por una rama hasta una hoja.
- Retrocede al último nodo con hermanas sin visitar.
- Repite hasta haber pasado por todos los nodos.
- Cambia a amplitud si prefieres avanzar nivel a nivel.
¿Para qué sirve en la realidad?
Los árboles organizan datos jerárquicos y decisiones: los recorridos en profundidad y amplitud son la base de buscar en estructuras de índice, evaluar árboles de decisión y navegar sistemas de ficheros.
En un árbol con n vértices, el número de aristas es:
El recorrido en amplitud visita una rama hasta el fondo antes de pasar a la siguiente.
Árboles
Distingue los dos recorridos según su comportamiento.
Profundidad
Amplitud
Árbol (teoría de grafos)
Grafo conexo sin ciclos y sus propiedades.
Une cada propiedad o término de árboles con su pareja:
El grafo de la jerarquía
# Árboles y recorridos ## Estructura ### raíz y hojas ### padres e hijos ### sin ciclos ## Medidas ### altura ### profundidad ## Recorridos ### profundidad con pila ### amplitud con cola
Recorrido de árboles
Estrategias de profundidad y amplitud para visitar nodos.
Piensa en el sistema de carpetas de tu ordenador como un árbol. Señala la raíz, una hoja, y explica si querrías un recorrido en profundidad o en amplitud para listar todos los ficheros agrupados por carpeta.