¿Qué es un árbol y por qué estudiarlos?

Como cualquier estructura de datos, un árbol es una colección de datos que se relacionan entre sí. Lo que hace especial a un árbol es que organiza la información de forma jerárquica, es decir, algunos elementos están por encima o por debajo de otros.

Esto lo diferencia de una estructura lineal, como una lista o un arreglo, donde todos los elementos se encuentran al mismo nivel.

La jerarquización de datos es lo que hace que el árbol sea una estructura tan poderosa. Veamos un ejemplo sencillo.

Imagina que tienes una lista de 9 películas y, como usuario, quieres ver la película número 9. En una estructura lineal, tendrías que recorrer película por película hasta llegar a ella.

En una estructura tipo árbol, en cambio, puedes organizar esas películas para llegar mucho más rápido. Por ejemplo, tu árbol puede comenzar con un nodo llamado Películas. De Películas derivan tres categorías: Acción, Comedia y Fantasía. De cada una de estas categorías derivan 3 películas.

Si la película que buscas pertenece a Fantasía, solo necesitas recorrer el camino Películas → Fantasía → encontrar la película. En lugar de recorrer 9 elementos, solo recorrerías 2.

Aunque el árbol se utiliza para mucho más que facilitar la búsqueda de información. Por ejemplo, los archivos en tu computadora están organizados en forma de árbol: un directorio (carpeta) funciona como un nodo padre, y los archivos o subcarpetas que contiene son sus nodos hijos.

Si tienes experiencia programando, seguramente habrás notado que el DOM(Document Object Model) también está representado como un árbol de elementos. Además, muchos de los algoritmos que usamos para clasificar datos o realizar cálculos aritméticos se apoyan en la estructura del árbol para alcanzar sus objetivos de forma eficiente. Sin embargo, antes de profundizar en cómo utilizar el árbol en programación, es fundamental entender bien cuáles son sus componentes básicos.

Componentes de un árbol

Un árbol está formado por nodos. Cada nodo es una pieza de datos que se conecta con otros nodos.

• El primer nodo del árbol se llama Nodo Raíz.
• A partir del nodo raíz se derivan todos los demás nodos.

Existen distintos tipos de nodos según su relación con otros:

• Nodo padre: es un nodo del que deriva al menos un nodo hijo.
• Nodo hijo: es un nodo que tiene al menos un nodo padre.
• Nodo hermano: es un nodo que comparte el mismo nodo padre con otro nodo.
• Nodo hoja: es un nodo hijo del que no deriva ningún otro nodo. Son los últimos elementos del árbol.

Camino en un árbol

Un concepto clave para entender cómo funciona un árbol es el de camino.

El camino es la sucesión de nodos que se recorren desde un nodo hasta otro.

Para entender esto, primero debemos introducir el concepto de arista.. Una arista es la conexión entre dos nodos. Cada vez que un nodo padre se conecta con un nodo hijo, existe una arista entre ellos.

Volviendo al ejemplo de las películas, el camino hacia la película 1 sería:

Películas → Fantasía → 1

En este recorrido:

• Cada flecha representa una arista.
• Cada cambio de un nodo a otro es un salto.

La longitud del camino se define como el número de **aristas **que hay entre el nodo inicial y el nodo destino. En este caso, la longitud del camino es de 2, ya que se recorren dos aristas.

Otra forma sencilla de entenderlo es preguntarse: ¿Cuántos saltos necesito para llegar al nodo que busco?

Restricciones del camino en un árbol

Una característica importante de un árbol de datos estándar es que los nodos solo están conectados entre padre e hijo. Esto implica dos cosas fundamentales:

• No se puede ir directamente de un nodo a su hermano.
• Solo existe un único camino entre dos nodos.

Siguiendo con el ejemplo del árbol de películas: si mi programa está situado en el nodo Acción, no puedo ir directamente a Fantasía, ya que son nodos hermanos. Primero debo subir al nodo padre Películas, luego bajar a Fantasía y, finalmente, llegar al nodo 1.

El recorrido sería:

Acción → Películas → Fantasía → 1

En este caso, la longitud del camino es de 3, porque se necesitan tres saltos para llegar al destino.

Otras características importantes

• Nivel: el nivel de un nodo indica su posición con respecto a la raíz. En algunos casos, la raíz se considera nivel 0 y en otros nivel 1. Lo importante es entender que cada nueva generación de nodos hijos representa un nivel más.
• Altura: es la cantidad total de niveles que tiene un árbol. En algunos casos, se define una altura máxima antes de crear el árbol.
• Peso: es la cantidad total de nodos que contiene el árbol.
• Orden: es un valor previamente definido que indica el número máximo de nodos hijos que puede tener un nodo padre. Por ejemplo, un árbol binario tiene orden 2, lo que significa que cada nodo puede tener como máximo dos hijos.
• Grado: es el número de nodos hijos que tiene un nodo padre. Un nodo con tres hijos tiene grado 3. El grado puede estar limitado por el orden, pero no necesariamente.
• Grado del árbol: es el grado máximo entre todos los nodos del árbol.

Notas finales

Ahora que entiendes mejor qué es una estructura de árbol, podemos enfocarnos en cómo utilizarla en programación. Más abajo encontrarás posts relacionados con tutoriales y ejemplos prácticos que te ayudarán a profundizar en el uso de árboles y a verlos en acción.