En Haskell, los árboles son estructuras de datos fundamentales que se definen mediante tipos de datos algebraicos. Un árbol binario de búsqueda es una estructura donde cada elemento apunta a otros dos: uno a la izquierda, que contiene valores menores, y otro a la derecha, con valores mayores.
Definición y construcción de árboles
Podemos definir un árbol como un tipo que es o bien un árbol vacío o bien un nodo que contiene un valor y dos sub-árboles. Un árbol binario puede estar vacío o no vacío, donde Empty indica un árbol vacío. En lugar de construir manualmente un árbol, podemos crear una función que tome un elemento y un árbol e inserte dicho elemento en su posición adecuada dentro del árbol.
En lenguajes como C, realizaríamos esta tarea modificando punteros, pero en Haskell, al ser inmutables, creamos un nuevo sub-árbol cada vez que decidimos movernos a la izquierda o a la derecha. La declaración de tipo de nuestra función de inserción será a -> Tree a -> Tree a.
Ejemplo de implementación básica
- Caso base: Si alcanzamos un sub-árbol vacío, insertamos un árbol unitario con el elemento.
- Búsqueda: Si el elemento es menor que la raíz, vamos a la izquierda; si es mayor, a la derecha.
- Construcción: Podemos usar un pliegue (foldr) para construir un árbol a partir de una lista, usando treeInsert como función de pliegue y EmptyTree como valor inicial.
Operaciones comunes en árboles
A continuación se presenta una tabla comparativa sobre cómo procesar la información en estructuras arbóreas:
| Operación | Descripción |
|---|---|
| Contar nodos | Suma recursiva de los nodos en sub-árboles izquierdo y derecho más uno por la raíz. |
| Pertenencia | Comprueba si un elemento existe comparándolo con la raíz y descendiendo recursivamente. |
| Árboles N-arios | Permiten cualquier número de hijos; la suma de nodos se realiza mediante map y sum. |
El concepto de Zipper para navegación
Cuando queremos modificar elementos de forma repetida, navegar desde la raíz es ineficiente. Aquí es donde entra el Zipper. Un zipper nos permite recorrer el árbol paso a paso, recordando el camino tomado mediante un "rastro" o lista de direcciones. Básicamente, cada rastro es como un sub-árbol cojo que nos permite reconstruir el nodo padre mientras nos desplazamos.
Lea también: IVA 21% Excel
Al mantener esta información en lugar de desecharla, somos capaces de movernos de arriba a abajo, a la izquierda o a la derecha, manteniendo siempre el contexto. Si queremos volver por el camino tomado, el zipper nos permite subir hacia el padre del sub-árbol actual. Esta técnica es especialmente potente cuando necesitamos realizar modificaciones profundas sin perder la estructura original del árbol.
Lea también: Guía IVA reducido
Lea también: ¿Cómo localizar tus XML del SAT?