Los árboles son grafos conectados sin ciclos. Su estructura jerárquica permite organizar datos, representar decisiones, buscar valores, modelar sistemas de archivos y recorrer relaciones de dependencia.
Los grafos describen conexiones generales. Cuando las conexiones forman una jerarquía sin ciclos, aparece una estructura especialmente útil: el árbol.
Los árboles están presentes en el sistema de archivos, el DOM de una página, los árboles de búsqueda, los menús, los compiladores y muchas representaciones de decisiones. Su ausencia de ciclos hace que entre dos nodos haya un camino inequívoco.
Un árbol es un grafo no dirigido, finito, conectado y sin ciclos. Un bosque es un grafo sin ciclos que puede tener varias componentes conectadas.
La conectividad garantiza que el árbol es una sola pieza. La aciclicidad evita rutas redundantes que vuelven al mismo lugar.
Para un grafo no dirigido con n vértices, las siguientes condiciones son equivalentes cuando se cumplen los supuestos adecuados:
Estas caracterizaciones ofrecen distintas formas de reconocer un árbol. Según los datos disponibles, puede resultar más fácil contar aristas, buscar ciclos o comprobar conectividad.
Un árbol con n vértices tiene exactamente n - 1 aristas. Esta es una de sus propiedades más útiles.
La propiedad puede demostrarse por inducción: al agregar una hoja a un árbol se agrega un vértice y exactamente una arista, preservando la diferencia de uno.
En un árbol existe un único camino simple entre cada par de vértices. Si hubiera dos caminos simples distintos entre los mismos vértices, al combinarlos se formaría un ciclo.
Esta unicidad simplifica búsquedas y razonamientos. En un grafo general pueden existir muchas rutas alternativas, lo que requiere decidir cuál recorrer o cuál es mejor.
Un árbol enraizado elige un vértice especial llamado raíz. Al orientarlo conceptualmente desde la raíz hacia abajo, aparecen relaciones de padre, hijo, ancestro y descendiente.
La raíz no cambia las aristas del árbol original; agrega una perspectiva jerárquica. Elegir otra raíz puede cambiar quién es padre o hijo sin cambiar el grafo subyacente.
En un árbol enraizado, una hoja es un nodo sin hijos. Un nodo interno tiene al menos un hijo. Dos nodos con el mismo padre son hermanos.
El término hoja puede tener una definición distinta en un árbol no enraizado, donde suele referirse a un vértice de grado 1. Es importante indicar qué convención se usa.
La profundidad de un nodo es el número de aristas desde la raíz hasta ese nodo. La altura de un nodo es la longitud del camino más largo desde él hasta una hoja. La altura del árbol es la altura de la raíz.
Algunos textos cuentan niveles desde 1 o miden altura por nodos en vez de aristas. En un algoritmo o documentación conviene fijar la convención para evitar errores de uno.
En un árbol ordenado, el orden entre los hijos de cada nodo es relevante. Por ejemplo, un primer y un segundo hijo no son intercambiables.
Los árboles de sintaxis y los árboles binarios suelen ser ordenados. En cambio, una jerarquía de categorías puede tratar sus hijos como un conjunto sin orden intrínseco.
Un árbol binario es un árbol enraizado y ordenado en el que cada nodo tiene como máximo dos hijos: izquierdo y derecho.
La distinción entre izquierdo y derecho es parte de la estructura. Un nodo con solo hijo izquierdo no es igual, como árbol ordenado, a un nodo con solo hijo derecho.
Estas expresiones se parecen, pero describen propiedades distintas:
| Tipo | Propiedad |
|---|---|
| Lleno o estricto | Todo nodo interno tiene exactamente dos hijos. |
| Completo | Todos los niveles se llenan salvo quizá el último, que se llena de izquierda a derecha. |
| Perfecto | Todo nodo interno tiene dos hijos y todas las hojas están a la misma profundidad. |
Todo árbol perfecto es lleno y completo, pero las otras implicaciones no se cumplen en general. La terminología puede variar ligeramente entre fuentes, por lo que conviene describir la propiedad concreta.
Si la raíz tiene altura 0, un árbol binario de altura h tiene como máximo 2h+1 - 1 nodos. En el nivel i hay como máximo 2i nodos.
La relación inversa muestra que un árbol binario equilibrado con n nodos tiene altura proporcional a log2(n), una razón clave de su eficiencia en búsquedas.
class NodoBinario {
constructor(valor, izquierdo = null, derecho = null) {
this.valor = valor;
this.izquierdo = izquierdo;
this.derecho = derecho;
}
}
const arbol = new NodoBinario(
8,
new NodoBinario(3, new NodoBinario(1), new NodoBinario(6)),
new NodoBinario(10)
);Cada nodo conserva referencias a sus hijos. La ausencia de hijo se representa con null. Esta estructura refleja directamente la definición recursiva de un árbol binario.
Un recorrido visita todos los nodos siguiendo una regla. En preorden se procesa primero el nodo actual, después el subárbol izquierdo y finalmente el derecho.
El preorden es útil para serializar una estructura jerárquica o procesar un contenedor antes de sus contenidos.
En inorden se recorre izquierdo, nodo y derecho. En postorden se recorre izquierdo, derecho y nodo.
El postorden es apropiado cuando un nodo debe procesarse después de todos sus descendientes, como al calcular tamaños acumulados o liberar estructuras.
function preorden(nodo, resultado = []) {
if (nodo === null) return resultado;
resultado.push(nodo.valor);
preorden(nodo.izquierdo, resultado);
preorden(nodo.derecho, resultado);
return resultado;
}
function inorden(nodo, resultado = []) {
if (nodo === null) return resultado;
inorden(nodo.izquierdo, resultado);
resultado.push(nodo.valor);
inorden(nodo.derecho, resultado);
return resultado;
}
console.log(preorden(arbol)); // [8, 3, 1, 6, 10]
console.log(inorden(arbol)); // [1, 3, 6, 8, 10]La recursión encaja naturalmente porque cada hijo es a su vez la raíz de un subárbol. En árboles muy profundos puede ser preferible una implementación iterativa con una pila explícita.
El recorrido por niveles, también llamado en anchura, visita primero la raíz, luego todos sus hijos, después los nietos y así sucesivamente. Usa una cola para recordar los nodos pendientes.
Este recorrido anticipa la búsqueda en anchura de grafos. La diferencia es que en un árbol no hay ciclos que obliguen a marcar vértices ya visitados.
Un árbol binario de búsqueda o BST organiza valores comparables con una regla: los valores del subárbol izquierdo son menores que el nodo y los del derecho son mayores, según la política elegida para duplicados.
Buscar, insertar y eliminar pueden ser O(log n) si el árbol está equilibrado. Si se insertan valores ordenados en un BST simple, puede degenerar en una cadena y las operaciones pasan a O(n).
Un heap binario es un árbol binario completo con una propiedad de prioridad. En un min-heap, cada nodo es menor o igual que sus hijos; por ello, el mínimo está en la raíz.
Los heaps implementan colas de prioridad y se usan en planificación de tareas y algoritmos de caminos mínimos. No deben confundirse con un BST: sus reglas de orden son diferentes.
Un árbol es adecuado cuando cada elemento, salvo la raíz, tiene un único padre en la jerarquía. Si un elemento debe tener varios padres, el modelo general de grafo suele ser más apropiado.
Los árboles organizan relaciones jerárquicas de forma eficiente y sin ambigüedad de caminos. En el próximo tema ampliaremos la mirada sobre grafos para estudiar caminos, ciclos y conectividad.