Ir al contenido principal

Actualización de «Inserción en árboles binarios de búsqueda»

He actualizado las soluciones del ejercicio Inserción en árboles binarios de búsqueda cuyo enunciado es


Un árbol binario de búsqueda (ABB) es un árbol binario tal que el cada nodo es mayor que los valores de su subárbol izquierdo y menor que los valores de su subárbol derecho y, además, ambos subárboles son árboles binarios de búsqueda. Por ejemplo, al almacenar los valores de [8,4,2,6,3] en un ABB se puede obtener el siguiente ABB:

   3
  / \
 /   \
2     6
     / \
    4   8

Los ABB se pueden representar como tipo de dato algebraico:

data ABB = V
  | N Int ABB ABB
  deriving (Eq, Show)

Por ejemplo, la definición del ABB anteriore es

ej :: ABB
ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

Definir la función

inserta :: Int -> ABB -> ABB

tal que (inserta v a) es el árbol obtenido añadiendo el valor v al ABB a, si no es uno de sus valores. Por ejemplo,

λ>  inserta 5 ej
N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V))
λ>  inserta 1 ej
N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V))
λ>  inserta 2 ej
N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

Comprobar con QuickCheck que al insertar un valor en un ABB se obtiene otro ABB.