Autor: Diego Peña Sadornil

Imaginémonos que te encuentras en un bosque, un bosque un poco peculiar. Su espesura no es relativamente homogénea como suele ser el caso normalmente, sino que va por hileras. La primera hilera tiene 1 árbol del que nacen dos caminos que conducen cada uno a un árbol de la segunda hilera, como si fuesen 2 hijos. 4 caminos conducen a la tercera hilera y a sus 4 árboles y, como ya te podrás imaginar, 8 caminos conducen a la cuarta que tiene 8 árboles “descendientes”. Cada camino une únicamente dos árboles en una línea recta y hay un total de 15 árboles, todos de alturas distintas que varían desde 1 hasta 15 metros.

En este bosque se te propone un juego. Debes encontrar el árbol de 11 metros de altura iniciando en la hilera con tan solo un árbol. Debido a la frondosidad de las hojas, no puedes ver el cartel que dice la altura del árbol al que pertenece desde lejos, únicamente desde abajo del propio árbol, para moverte entre árboles no puedes volver por los caminos ni moverte entre árboles hermanos, solo puedes ir desde tu árbol por los nuevos caminos disponibles. En caso de que quieras comprobar otros árboles que se encuentren detrás o a tus lados, debes empezar desde el inicio.

Si tuvieses que inspeccionar cada árbol, habría que hacer un total de 8 viajes en el peor de los casos, pero esto no solo es lento, sino que involuntariamente visitarías el primer árbol 8 veces, cada uno de los 2 siguientes 4 veces y así consecutivamente.

 Esta tarea puede parecer difícil y tediosa, sin embargo, este bosque se rige por una norma más, el hijo derecho del árbol en el que te encuentras será más alto que este y que su hijo de la izquierda y cualquiera de sus descendientes, y lo mismo para el descendiente izquierdo que será más pequeño que su padre, su hermano y los descendientes de su hermano. Esto podremos aprovecharlo para encontrar nuestro objetivo mucho más rápido.

Esto se usa en la informática más de lo que te puedes imaginar y tiene un nombre: árboles binarios. Son nodos que pueden tener uno, dos o ningún descendiente, y que además por lo general se rigen por normas como la comentada, que nos permiten manipular y leer datos de manera más rápida y eficaz si nos sabemos “las normas del bosque” pero, por lo contrario, si no las usamos a nuestro favor, puede ser altamente perjudicial porque, como se comentó al inicio, se debe volver a iniciar desde el primer árbol causándonos una gran pérdida de recursos y tiempo.

Estos árboles y sus caminos (o nodos y punteros) forman lo que llamamos una estructura de datos, que si entiendes y utilizas sabiamente te guiará hasta tu destino, de lo contrario podrías perderte en el bosque y encontrarte con un bicho también conocido como “bug” que te hará llegar erróneamente a tu destino o desorientarte hasta encontrarte en un bucle infinito.

En búsqueda de la victoria:

Ahora veremos cómo podemos ganar el juego anterior en un solo viaje. Nos encontramos en el nodo inicial, veamos que en su “cartel” pone que su valor es de 8, al ser el valor buscado 11, tomaremos el camino de la derecha.

El nuevo nodo tiene efectivamente un valor mayor, esta vez 12, entendiendo ya las normas de este bosque cambiaremos la dirección para ir a la izquierda, es decir, los nodos con menor valor.

En este nodo el valor es de 10. Una vez más, gracias a nuestra comprensión nos guiaremos por el camino derecho para llegar a nuestro destino.

Finalmente hemos llegado a nuestro destino. Gracias a las normas iniciales hemos aprendido a dominar el bosque y llegar a nuestro destino rápidamente.

Esta cosa tan simple que hemos hecho también tiene un nombre y es conocida como búsqueda en un árbol binario de búsqueda (BST, acrónimo del inglés Binary Search Tree). Este método de exploración nos ha permitido encontrar nuestro destino en unos pocos pasos. El juego nos ha mostrado por qué los árboles binarios son una estructura clave en el mundo de la informática, pero, aunque el juego ha terminado, nuestra curiosidad continúa y hay un mundo de bosques que investigar.

Ejemplos de aplicación:

Gracias al ejercicio y ejemplo anterior, podemos ver la utilidad de estas estructuras, pero antes de avanzar hemos de explicar un par de cosas. Hemos visto que son de realmente prácticas para encontrar datos específicos rápidamente. Sin embargo, nos hemos encontrado un caso bastante ideal, esto se debe a que todos los padres tenían 2 hijos y no solo eso, el árbol estaba balanceado, que significa que el árbol tenía aproximadamente (en este caso exactamente) el mismo número de nodos por ambos caminos. Esto preferiblemente será así pero no siempre lo es, es un concepto que tenemos que tener en cuenta, ya que el balance de árboles juega a nuestro favor para movernos más rápidamente por el bosque. También hay que entender que normalmente los árboles se representan con la raíz arriba del todo, en nuestro caso ha sido al revés para ayudar a la visualización de toma de decisiones de aquellos que se estén enfrentando al bosque por primera vez.

En el ejemplo de la figura 6, podemos ver un árbol que se rige por las normas de antes y que para acceder al nodo con el valor 13 tenemos que pasar por más nodos que en el ejemplo anterior aun habiendo menos nodos en el sistema. Si la naturaleza lo pone todo en su sitio, por qué no hacerla caso.

Lo último que cabe destacar es que normalmente al primer nodo le llamamos raíz, ya que no tiene nada antes de él, mientras que a los nodos sin descendencia se les llama hojas puesto que igual que en un árbol real marcan los límites superiores de la estructura del árbol.

Ahora que hemos aprendido a orientarnos y entender el bosque es momento de ver cómo estos árboles nos ayudan. Hoy en día, casi cualquier programa se usan árboles binarios, pero ¿de qué serviría poner ejemplos en los que se usan para tareas con conceptos complejos si no se comprendería la utilidad? Por eso veremos dos ejemplos de uso cotidiano. Quién no ha oído o incluso creado archivos en formato ZIP, JPEG o MP3. Aunque parecen ser muy distintos porque ZIP se usa para la compresión de carpetas, JPEG para la de imágenes y MP3 para la de audios, los tres comparten su sistema de codificación, están basadas en el algoritmo de compresión de Huffman. Esto significa que a los caracteres mas comunes se les asigna el valor de uno de los primeros nodos y a los menos de los últimos. Por ejemplo, la compresión de “ABRACADABRA” sería como a continuación:

La A al ser la más común tendrá el valor de la raíz para más fácil acceso luego B y R y finalizando con C y D.

Estos árboles binarios son parte de algo mucho más grande conocido como grafos donde hay distintos tipos de árboles y otras estructuras. No es un concepto exclusivo de la informática, sino que también se aplica en muchas otras áreas. Veamos cómo tu calculadora procesa la operación (2+3) x 3.

La solución se busca de arriba a abajo, pero si uno de los nodos hijos es un símbolo lo que se hace es calcular la operación de sus hijos usando su símbolo. Primero encontraríamos la x veríamos que un hijo es otro símbolo (+) y haríamos la suma 2 + 3 = 5 y devolveríamos el valor para finalizar haciendo 5 x 3 = 15.

De concepto a código:

Hemos jugado a encontrar de nuestro destino, pero, si ya es difícil expresarse con humanos, a veces más aún puede ser hacerlo para que nos entienda un ordenador. Pero ahora veremos cómo con unas pocas líneas de código podemos hacer que un ordenador nos entienda y ayuda a resolver el problema.

Programar para algunos puede ser un poco pesado pero para ayudarnos existe Python un lenguaje de programación que con unos pequeños conocimientos de inglés y correcto nombramiento de variables será realmente fácil entender el código.

Tan simple como lo ves es iniciarse en el mundo de los árboles en la informática, pero recuerda: no todos los bosques se rigen por las mismas normas. Antes de adentrarte en uno, aprende a leer sus señales y comprender su estructura, porque el tiempo es oro y en el mundo de los datos no perderse lo es todo.

Aquí puedes leer la continuación de este artículo: Árboles binarios (2). Cómo cultivarlos y sembrar sus frutos.

Referencias

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

2. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.

3. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley.

4. Lafore, R. (2002). Data Structures and Algorithms in Java (2nd ed.). Sams Publishing.

 Artículo participante del VIII Concurso de Artículos de Divulgación Científica de la Universidad de Burgos.

Imagen inicial creada con herramientas de IA por la UCC+i UBU.