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.
