Las estructuras de datos lineales como los arreglos son útiles, pero tienen limitaciones. Cuando los datos tienen una relación jerárquica, como un árbol genealógico o la estructura de archivos en una computadora, necesitamos algo más adecuado. Aquí es donde entran los árboles.

Un tipo fundamental es el árbol binario de búsqueda (BST, por sus siglas en inglés). Cada nodo en un BST tiene como máximo dos hijos: uno izquierdo y uno derecho. La regla es simple: todos los valores en el subárbol izquierdo de un nodo son menores que el valor del nodo, y todos los valores en el subárbol derecho son mayores.

Pero los BST tienen una debilidad. Si insertas datos que ya están ordenados (por ejemplo, 1, 2, 3, 4, 5), el árbol se vuelve desequilibrado. Se convierte esencialmente en una lista enlazada, y la eficiencia de búsqueda se degrada a $O(n)$, que es mucho más lento.

Para solucionar esto, usamos árboles autobalanceados. Un ejemplo popular es el árbol AVL. Un árbol AVL es un BST que se monitorea a sí mismo para mantenerse equilibrado. Cada nodo calcula un "factor de equilibrio": la diferencia de altura entre su subárbol izquierdo y su subárbol derecho. Si este factor es mayor que 1 o menor que -1, el árbol está desequilibrado.

Otro tipo de árbol importante es el árbol B. A diferencia de los árboles binarios, los nodos de un árbol B pueden tener muchos hijos y almacenar múltiples claves. Esta estructura es ideal para sistemas que leen y escriben grandes bloques de datos, como bases de datos y sistemas de archivos. Al mantener el árbol poco profundo y ancho, los árboles B minimizan el número de accesos a disco necesarios para encontrar datos.

Mientras que los árboles modelan jerarquías, los grafos modelan redes. Un grafo consiste en un conjunto de vértices (o nodos) conectados por aristas (o enlaces). Piensa en una red social: cada persona es un vértice y una amistad es una arista. Este es un ejemplo de un grafo no dirigido, donde la relación es mutua.

Ahora, considera la web. Las páginas web son vértices y los enlaces de una página a otra son aristas. Si la página A enlaza a la página B, no significa necesariamente que la página B enlace de vuelta a la A. Esta es la idea detrás de un grafo dirigido.

Una vez que tienes un grafo, a menudo necesitas una forma de visitarlos todos. Para esto, usamos algoritmos de recorrido. Los dos más comunes son la Búsqueda en Anchura (BFS) y la Búsqueda en Profundidad (DFS).

La Búsqueda en Anchura (BFS) comienza en un nodo raíz y explora todos sus vecinos inmediatos. Luego, para cada uno de esos vecinos, explora sus vecinos no visitados, y así sucesivamente. BFS es excelente para encontrar el camino más corto entre dos nodos en un grafo no ponderado.

Por otro lado, la Búsqueda en Profundidad (DFS) sigue un camino hasta el final antes de retroceder y probar otro. Comienza en un nodo, explora uno de sus vecinos, luego uno de los vecinos de ese vecino, y continúa hasta que llega a un nodo sin vecinos no visitados. Luego retrocede y explora la siguiente rama. DFS es útil para tareas como la ordenación topológica o la detección de ciclos en un grafo.

Ahora, pongamos a prueba tus conocimientos sobre estas estructuras de datos.

Comprender los árboles y los grafos abre un nuevo mundo de resolución de problemas, permitiéndote modelar y manipular datos complejos de manera eficiente.