Árbol binario de búsqueda

Instrucciones

Inserta y busca números en un árbol binario.

Cuando necesitamos representar datos ordenados, un array no es una buena estructura de datos.

Supongamos que tenemos el array [1, 3, 4, 5] y le agregamos 2, así que ahora es [1, 3, 4, 5, 2]. ¡Ahora tenemos que volver a ordenar todo el array! Podemos mejorar esto si nos damos cuenta de que solo necesitamos hacer espacio para el nuevo elemento [1, nil, 3, 4, 5] y luego agregarlo en el espacio que hicimos. Pero esto todavía nos obliga a desplazar muchos elementos una posición.

Los árboles binarios de búsqueda, sin embargo, pueden operar con datos ordenados de manera mucho más eficiente.

Un árbol binario de búsqueda consiste en una serie de nodos conectados. Cada nodo contiene una pieza de datos (por ejemplo, el número 3), una variable llamada left y una variable llamada right. Las variables left y right apuntan a nil o a otros nodos. Como esos otros nodos a su vez tienen otros nodos debajo de ellos, decimos que las variables left y right apuntan a subárboles. Todos los datos del subárbol izquierdo son menores o iguales que los datos del nodo actual, y todos los datos del subárbol derecho son mayores que los datos del nodo actual.

Por ejemplo, si tuviéramos un nodo que contiene el dato 4 y le agregáramos el dato 2, nuestro árbol se vería así:

  4
 /
2

Si luego agregáramos 6, se vería así:

  4
 / \
2   6

Si luego agregáramos 3, se vería así

   4
 /   \
2     6
 \
  3

Y si luego agregáramos 1, 5 y 7, se vería así

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

Pistas

Para completar este ejercicio necesitas crear el tipo de dato BST, con instancias de Eq y Show, e implementar las funciones:

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

Encontrarás ya en su lugar una declaración de datos ficticia y las firmas de tipo, pero depende de ti definir las funciones y crear un tipo de dato, un newtype o un sinónimo de tipo con sentido.