Crear un árbol binario con Haskell

En informática, los árboles crecen al revés. La raíz única está en la parte superior, y las hojas están en la parte inferior. En realidad depende como se lo vea. 

El árbol binario se usa a menudo para almacenar datos ordenados, para permitir una búsqueda eficiente, por ejemplo, un directorio telefónico.

Vamos a definir un tipo de datos Haskell para árboles, almacenando valores enteros.

data Tree = Leaf | Node Int Tree Tree deriving Show

Un valor de árbol puede ser una hoja o un nodo. Tenga en cuenta que este es un tipo de datos recursivo, ya que un Nodo almacena un árbol de enteros y tiene ramificaciones a dos subárboles (a veces llamados hijos). Como se ve definimos que un árbol es una hoja o un nodo con el dato y dos arboles. 

Aquí está el árbol más simple: es solo una hoja.

Leaf

Aquí hay un árbol con un Nodo que contiene el valor 3 y dos hojas.

Node 3 Leaf Leaf

Si escribe esto en ghci, verá los valores devueltos cuando construya estos árboles, siempre que su tipo de datos Tree derive la clase Show type.

El tipo de este valor es:

let l = Node 3 Leaf Leaf

:t l

El tipo del nodo constructor:

:t Node

Esta es una función: el nodo constructor toma tres argumentos y devuelve un resultado de árbol.

Ahora escribamos una función para calcular la profundidad de un árbol: esta es la cantidad máxima de ramas desde la raíz hasta cualquier hoja. Para escribir esta función, haremos coincidir patrones en los diferentes tipos de árbol, es decir, valores de hoja y nodo. Cada hoja es un caso base, pero para cada nodo, necesitamos procesar recursivamente los dos árboles secundarios.

treeDepth :: Tree -> Int

treeDepth Leaf = 0

treeDepth (Node _ leftSubtree rightSubtree) = 

  1 + max (treeDepth leftSubtree) (treeDepth rightSubtree)

Observe el _ en la línea 3, que es un valor de "don’t care" o "no me importa", ya que descartamos el entero en cada nodo.

¿Qué tal una función para verificar si un árbol está ordenado correctamente? La estructura de datos invariable que queremos es que, para cualquier valor de almacenamiento de Nodo x, todos los valores en su subárbol izquierdo sean <x, y todos los valores en su subárbol derecho sean> = x.

Entonces, esta función tomará un Árbol, un valor mínimo, un valor máximo y devolverá un Bool. isSortedTree :: Árbol -> Int -> Int -> Bool

Una hoja se ordena automáticamente, ya que no contiene un valor. Para cada nodo, tenemos que verificar que el valor entre los valores mínimo y máximo, que comienzan lo más lejos posible, luego se dividen en rangos más pequeños según el valor en el nodo.

isSortedTree :: Tree -> Int -> Int -> Bool

isSortedTree Leaf _ _ = True

isSortedTree (Node x leftSubtree rightSubtree) minVal maxVal =

    let leftSorted   = isSortedTree leftSubtree minVal x

        rightSorted = isSortedTree rightSubtree x maxVal

    in x >= minVal && x< maxVal && leftSorted && rightSorted

Hasta ahora, hemos estudiado las funciones de recorrido del árbol, donde revisamos la estructura de datos del árbol y hacemos algunos cálculos incrementales en cada nodo. Ahora queremos hacer una función de modificación del árbol. Esto genera un nuevo árbol que es una versión modificada del árbol de entrada.

La función particular que vamos a definir inserta un nuevo valor máximo. Pasamos por el árbol de entrada hasta encontrar el nodo de la derecha con una hoja a la derecha, luego reemplazamos esta hoja de la derecha con un nuevo nodo que contiene un nuevo valor máximo (uno más grande que el valor máximo anterior).

addNewMax :: Tree -> Tree

-- add a new max element to tree

addNewMax Leaf = Node 0 Leaf Leaf  -- input tree with no nodes

addNewMax (Node x t1 Leaf) = Node x t1 (Node (x+1) Leaf Leaf)  -- this is the rightmost Node

addNewMax (Node x t1 t2) = Node x t1 (addNewMax t2) -- intermediate node, go down right subtree

Esta función addNewMax toma un valor de entrada de árbol y devuelve un valor de salida de árbol.