Á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 añadimos 2, de modo que pasa a ser [1, 3, 4, 5, 2]. ¡Ahora tenemos que volver a ordenar el array entero! Podemos mejorar esto si nos damos cuenta de que solo necesitamos hacer sitio para el nuevo elemento [1, nil, 3, 4, 5] y luego añadir el elemento en el hueco que hemos creado. Pero esto sigue obligándonos a desplazar muchos elementos una posición hacia abajo.

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

Un árbol binario de búsqueda consta de una serie de nodos conectados. Cada nodo contiene un dato (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 tienen, a su vez, otros nodos debajo, decimos que las variables left and 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 añadiéramos el dato 2, nuestro árbol tendría este aspecto:

  4
 /
2

Si después añadiéramos 6, tendría este aspecto:

  4
 / \
2   6

Si después añadiéramos 3, tendría este aspecto

   4
 /   \
2     6
 \
  3

Y si después añadiéramos 1, 5 y 7, tendría este aspecto

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

Pistas

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

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

Encontrarás ya en su sitio una declaración de datos de prueba y las firmas de tipo, pero depende de ti definir las funciones y crear un tipo de datos, un newtype o un sinónimo de tipo que tenga sentido.