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.