El tipo abstracto de datos de los árboles binarios de búsqueda en Haskell

Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los árboles binarios de búsqueda.

Un árbol binario de búsqueda (ABB) (binary search tree en inglés) es un árbol binario tal que el valor de cada nodo es mayor que los valores de su subárbol izquierdo y es 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 [2,3,4,5,6,8,9] en un ABB se puede obtener los siguientes ABB:

    5                     5
  /   \                 /   \
 2     6               3     8
  \     \             / \   / \
   4     8           2   4 6   9
  /       \
 3         9

5 5

/ \ / \

2 6 3 8

\ \ / \ / \

4 8 2 4 6 9

/ \

3 9

El objetivo principal de los ABB es reducir el tiempo de acceso a los valores.

El contenido del resto del artículo es el siguiente:

la signatura del TAD de los árboles binarios de búsqueda;
las propiedades del TAD de los árboles binarios de búsqueda;
la implementación, en Haskell, de los árboles binarios de búsqueda mediante tipos de datos algebraicos.
la comprobación con QuickCheck de sus propiedades.

La signatura del TAD de los árboles binarios de búsqueda

Las signatura de las operaciones del TAD de los árboles binarios de búsqueda son las siguientes:

vacio     :: ABB 
inserta   :: (Ord a,Show a) => a -> ABB a -> ABB a
elimina   :: (Ord a,Show a) => a -> ABB a -> ABB a
crea      :: (Ord a,Show a) => [a] -> ABB a
menor     :: Ord a => ABB a -> a
elementos :: (Ord a,Show a) => ABB a -> [a]
pertenece :: (Ord a,Show a) => a -> ABB a -> Bool
valido    :: (Ord a,Show a) => ABB a -> Bool

vacio :: ABB

inserta :: (Ord a,Show a) => a -> ABB a -> ABB a

elimina :: (Ord a,Show a) => a -> ABB a -> ABB a

crea :: (Ord a,Show a) => [a] -> ABB a

menor :: Ord a => ABB a -> a

elementos :: (Ord a,Show a) => ABB a -> [a]

pertenece :: (Ord a,Show a) => a -> ABB a -> Bool

valido :: (Ord a,Show a) => ABB a -> Bool

con el siguiente significado

vacio es el ABB vacío.
(pertenece v a) se verifica si v es el valor de algún nodo del ABB a.
(inserta v a) es el árbol obtenido añadiendo el valor v al ABB a, si no es uno de sus valores.
(crea vs) es el ABB cuyos valores son vs.
(elementos a) es la lista de los valores de los nodos del ABB en el recorrido inorden.
(elimina v a) es el ABB obtenido eliminando el valor v del ABB a.
(menor a) es el mínimo valor del ABB a.
(valido a) se verifica si a es un ABB correcto.

Propiedades del TAD de los árboles binarios de búsqueda

Las propiedades son las siguientes:

valido vacio
valido (inserta v a)
inserta x a /= vacio
pertenece x (inserta x a)
not (pertenece x vacio)
pertenece y (inserta x a) == (x == y) || pertenece y a
valido (elimina v a)
elimina x (inserta x a) == elimina x a
valido (crea xs)
elementos (crea xs) == sort (nub xs)
pertenece v a == elem v (elementos a)
Para todo x de elementos a, (menor a <= x)

Implementación de los árboles binarios de búsqueda mediante tipos de datos algebraicos

module ArbolBin
    (ABB,
     vacio,     -- ABB 
     inserta,   -- (Ord a,Show a) => a -> ABB a -> ABB a
     elimina,   -- (Ord a,Show a) => a -> ABB a -> ABB a
     crea,      -- (Ord a,Show a) => [a] -> ABB a
     crea',     -- (Ord a,Show a) => [a] -> ABB a
     menor,     -- Ord a => ABB a -> a
     elementos, -- (Ord a,Show a) => ABB a -> [a]
     pertenece, -- (Ord a,Show a) => a -> ABB a -> Bool
     valido     -- (Ord a,Show a) => ABB a -> Bool
    ) where

-- Los ABB como tipo de dato algebraico.
data Ord a => ABB a = Vacio
                    | Nodo a (ABB a) (ABB a)
                    deriving Eq

-- Procedimiento de escritura de árboles binarios de búsqueda.
instance (Show a, Ord a) => Show (ABB a) where
    show Vacio        = " -"
    show (Nodo x i d) = " (" ++ show x ++ show i ++ show d ++ ")"

-- Ejemplos de ABB
--    ghci> abb1
--     (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -))))
--    ghci> abb2
--     (5 (2 - (4 (3 - -) -)) (8 (6 - (7 - -)) (10 (9 - -) (11 - -))))
abb1, abb2 :: ABB Int
abb1 = crea (reverse [5,2,6,4,8,3,9])
abb2 = foldr inserta vacio (reverse [5,2,4,3,8,6,7,10,9,11])

-- vacio es el ABB vacío. Por ejemplo,
--    ghci> vacio
--     -
vacio :: ABB a
vacio = Vacio

-- (pertenece v' a) se verifica si v' es el valor de algún nodo del ABB
-- a. Por ejemplo, 
--   pertenece 3 abb1  ==  True
--   pertenece 7 abb1  ==  False
pertenece :: (Ord a,Show a) => a -> ABB a -> Bool
pertenece v' Vacio                = False
pertenece v' (Nodo v i d) | v==v' = True  
                          | v'<v  = pertenece v' i
                          | v'>v  = pertenece v' d

-- (inserta v a) es el árbol obtenido añadiendo el valor v al ABB a, si
-- no es uno de sus valores. Por ejemplo, 
--    ghci> inserta 7 abb1
--     (5 (2 - (4 (3 - -) -)) (6 - (8 (7 - -) (9 - -))))
inserta :: (Ord a,Show a) => a -> ABB a -> ABB a
inserta v' Vacio = Nodo v' Vacio Vacio
inserta v' (Nodo v i d) 
    | v' == v   = Nodo v i d
    | v' < v    = Nodo v (inserta v' i) d
    | otherwise = Nodo v i (inserta v' d)

-- (crea vs) es el ABB cuyos valores son vs. Por ejemplo,
--    ghci> crea [3,7,2]
--     (2 - (7 (3 - -) -))
crea :: (Ord a,Show a) => [a] -> ABB a
crea = foldr inserta Vacio

-- (crea' vs) es el ABB de menor profundidad cuyos valores son los de
-- la lista ordenada vs. Por ejemplo, 
--    ghci> crea' [2,3,7]
--     (3 (2 - -) (7 - -))
crea' :: (Ord a,Show a) => [a] -> ABB a
crea' [] = Vacio
crea' vs = Nodo x (crea' l1) (crea' l2)
    where n      = length vs `div` 2
          l1     = take n vs
          (x:l2) = drop n vs 

-- (elementos a) es la lista de los valores de los nodos del ABB en el
-- recorrido inorden. Por ejemplo,          
--   elementos abb1  ==  [2,3,4,5,6,8,9]
--   elementos abb2  ==  [2,3,4,5,6,7,8,9,10,11]
elementos :: (Ord a,Show a) => ABB a -> [a]
elementos Vacio        = []
elementos (Nodo v i d) = elementos i ++ [v] ++ elementos d

-- (elimina v a) es el ABB obtenido borrando el valor v del ABB a. Por
-- ejemplo, 
--    ghci> abb1
--     (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -))))
--    ghci> elimina 3 abb1
--     (5 (2 - (4 - -)) (6 - (8 - (9 - -))))
--    ghci> elimina 2 abb1
--     (5 (4 (3 - -) -) (6 - (8 - (9 - -))))
--    ghci> elimina 5 abb1
--     (6 (2 - (4 (3 - -) -)) (8 - (9 - -)))
--    ghci> elimina 7 abb1
--     (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -))))
elimina  :: (Ord a,Show a) => a -> ABB a -> ABB a
elimina v' Vacio = Vacio 
elimina v' (Nodo v i Vacio) | v'==v = i 
elimina v' (Nodo v Vacio d) | v'==v = d
elimina v' (Nodo v i d)
    | v'<v  = Nodo v (elimina v' i) d 
    | v'>v  = Nodo v i (elimina v' d)  
    | v'==v = Nodo k i (elimina k d)
              where k = menor d 

-- (menor a) es el mínimo valor del ABB a. Por ejemplo,
--   menor abb1  ==  2
menor :: Ord a => ABB a -> a
menor (Nodo v Vacio _) = v
menor (Nodo _ i _)        = menor i 

-- (menorTodos v a) se verifica si v es menor que todos los elementos
-- del ABB a.
menorTodos :: (Ord a, Show a) => a -> ABB a -> Bool
menorTodos v Vacio = True 
menorTodos v a        = v < minimum (elementos a)

-- (mayorTodos v a) se verifica si v es mayor que todos los elementos
-- del ABB a.
mayorTodos :: (Ord a, Show a) => a -> ABB a -> Bool
mayorTodos v Vacio = True 
mayorTodos v a = v > maximum (elementos a)

-- (valido a) se verifica si a es un ABB correcto. Por ejemplo,
--    valido abb1 == True
valido :: (Ord a, Show a) => ABB a -> Bool
valido Vacio        = True
valido (Nodo v a b) = mayorTodos v a && menorTodos v b && 
                      valido a && valido b

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

module ArbolBin

(ABB,

vacio, -- ABB

inserta, -- (Ord a,Show a) => a -> ABB a -> ABB a

elimina, -- (Ord a,Show a) => a -> ABB a -> ABB a

crea, -- (Ord a,Show a) => [a] -> ABB a

crea', -- (Ord a,Show a) => [a] -> ABB a

menor, -- Ord a => ABB a -> a

elementos, -- (Ord a,Show a) => ABB a -> [a]

pertenece, -- (Ord a,Show a) => a -> ABB a -> Bool

valido -- (Ord a,Show a) => ABB a -> Bool

) where

-- Los ABB como tipo de dato algebraico.

data Ord a => ABB a = Vacio

| Nodo a (ABB a) (ABB a)

deriving Eq

-- Procedimiento de escritura de árboles binarios de búsqueda.

instance (Show a, Ord a) => Show (ABB a) where

show Vacio = " -"

show (Nodo x i d) = " (" ++ show x ++ show i ++ show d ++ ")"

-- Ejemplos de ABB

-- ghci> abb1

-- (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -))))

-- ghci> abb2

-- (5 (2 - (4 (3 - -) -)) (8 (6 - (7 - -)) (10 (9 - -) (11 - -))))

abb1, abb2 :: ABB Int

abb1 = crea (reverse [5,2,6,4,8,3,9])

abb2 = foldr inserta vacio (reverse [5,2,4,3,8,6,7,10,9,11])

-- vacio es el ABB vacío. Por ejemplo,

-- ghci> vacio

-- -

vacio :: ABB a

vacio = Vacio

-- (pertenece v' a) se verifica si v' es el valor de algún nodo del ABB

-- a. Por ejemplo,

-- pertenece 3 abb1 == True

-- pertenece 7 abb1 == False

pertenece :: (Ord a,Show a) => a -> ABB a -> Bool

pertenece v' Vacio = False

pertenece v' (Nodo v i d) | v==v' = True

| v'<v = pertenece v' i

| v'>v = pertenece v' d

-- (inserta v a) es el árbol obtenido añadiendo el valor v al ABB a, si

-- no es uno de sus valores. Por ejemplo,

-- ghci> inserta 7 abb1

-- (5 (2 - (4 (3 - -) -)) (6 - (8 (7 - -) (9 - -))))

inserta :: (Ord a,Show a) => a -> ABB a -> ABB a

inserta v' Vacio = Nodo v' Vacio Vacio

inserta v' (Nodo v i d)

| v' == v = Nodo v i d

| v' < v = Nodo v (inserta v' i) d

| otherwise = Nodo v i (inserta v' d)

-- (crea vs) es el ABB cuyos valores son vs. Por ejemplo,

-- ghci> crea [3,7,2]

-- (2 - (7 (3 - -) -))

crea :: (Ord a,Show a) => [a] -> ABB a

crea = foldr inserta Vacio

-- (crea' vs) es el ABB de menor profundidad cuyos valores son los de

-- la lista ordenada vs. Por ejemplo,

-- ghci> crea' [2,3,7]

-- (3 (2 - -) (7 - -))

crea' :: (Ord a,Show a) => [a] -> ABB a

crea' [] = Vacio

crea' vs = Nodo x (crea' l1) (crea' l2)

where n = length vs `div` 2

l1 = take n vs

(x:l2) = drop n vs

-- (elementos a) es la lista de los valores de los nodos del ABB en el

-- recorrido inorden. Por ejemplo,

-- elementos abb1 == [2,3,4,5,6,8,9]

-- elementos abb2 == [2,3,4,5,6,7,8,9,10,11]

elementos :: (Ord a,Show a) => ABB a -> [a]

elementos Vacio = []

elementos (Nodo v i d) = elementos i ++ [v] ++ elementos d

-- (elimina v a) es el ABB obtenido borrando el valor v del ABB a. Por

-- ejemplo,

-- ghci> abb1

-- (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -))))

-- ghci> elimina 3 abb1

-- (5 (2 - (4 - -)) (6 - (8 - (9 - -))))

-- ghci> elimina 2 abb1

-- (5 (4 (3 - -) -) (6 - (8 - (9 - -))))

-- ghci> elimina 5 abb1

-- (6 (2 - (4 (3 - -) -)) (8 - (9 - -)))

-- ghci> elimina 7 abb1

-- (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -))))

elimina :: (Ord a,Show a) => a -> ABB a -> ABB a

elimina v' Vacio = Vacio

elimina v' (Nodo v i Vacio) | v'==v = i

elimina v' (Nodo v Vacio d) | v'==v = d

elimina v' (Nodo v i d)

| v'<v = Nodo v (elimina v' i) d

| v'>v = Nodo v i (elimina v' d)

| v'==v = Nodo k i (elimina k d)

where k = menor d

-- (menor a) es el mínimo valor del ABB a. Por ejemplo,

-- menor abb1 == 2

menor :: Ord a => ABB a -> a

menor (Nodo v Vacio _) = v

menor (Nodo _ i _) = menor i

-- (menorTodos v a) se verifica si v es menor que todos los elementos

-- del ABB a.

menorTodos :: (Ord a, Show a) => a -> ABB a -> Bool

menorTodos v Vacio = True

menorTodos v a = v < minimum (elementos a)

-- (mayorTodos v a) se verifica si v es mayor que todos los elementos

-- del ABB a.

mayorTodos :: (Ord a, Show a) => a -> ABB a -> Bool

mayorTodos v Vacio = True

mayorTodos v a = v > maximum (elementos a)

-- (valido a) se verifica si a es un ABB correcto. Por ejemplo,

-- valido abb1 == True

valido :: (Ord a, Show a) => ABB a -> Bool

valido Vacio = True

valido (Nodo v a b) = mayorTodos v a && menorTodos v b &&

valido a && valido b

Propiedades de los árboles binarios de búsqueda

{-# LANGUAGE FlexibleInstances #-}

import ArbolBin

import Data.List
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Generador de ABB                                                   --
-- ---------------------------------------------------------------------

-- genABB es un generador de árboles binarios de búsqueda. Por ejemplo,
--    ghci> sample genABB
--     -
--     (1 (-1 - -) -)
--     (1 - -)
--     (-1 (-3 - -) (1 - (4 - -)))
--     -
--     (10 (-7 - -) -)
--     (1 (-9 - -) (7 (5 - -) (10 - -)))
--     ...
genABB :: Gen (ABB Int)
genABB = do xs <- listOf arbitrary
            return (foldr inserta vacio xs)

-- Los árboles binarios de búsqueda son concreciones de la clase
-- arbitraria. 
instance Arbitrary (ABB Int) where
    arbitrary = genABB

-- Propiedad. Todo los elementos generados por genABB son árboles binarios
-- de búsqueda.
prop_genABB_correcto :: ABB Int -> Bool
prop_genABB_correcto = valido 

-- Comprobación.
--    ghci> quickCheck prop_genABB_correcto
--    +++ OK, passed 100 tests.

-- listaOrdenada es un generador de listas ordenadas de números
-- enteros. Por ejemplo,
--    ghci> sample listaOrdenada
--    [1]
--    [1]
--    [-2,-1,0]
--    [-1,0,1]
--    [-8,-5,-4,-3,3,4,8]
--    [-6,-3,8]
--    [-14,-13]
--    [-31,-23,-16,-13,-11,-5,1,4,11,14,15,21,26,29]
--    []
--    []
--    []
listaOrdenada :: Gen [Int]
listaOrdenada = 
    frequency [(1,return []),
               (4,do xs <- orderedList
                     n <- arbitrary
                     return (nub ((case xs of
                                     []  -> n
                                     x:_ -> n `min` x)
                                  :xs)))]

-- (ordenada xs) se verifica si xs es una lista ordenada creciente. Por
-- ejemplo, 
--    ordenada [3,5,9]  ==  True
--    ordenada [3,9,5]  ==  False
ordenada :: [Int] -> Bool
ordenada xs = and [x<y | (x,y) <- zip xs (tail xs)]

-- Propiedad. El generador listaOrdenada produce listas ordenadas. 
prop_listaOrdenada_correcta :: [Int] -> Property
prop_listaOrdenada_correcta xs = 
    forAll listaOrdenada ordenada

-- Comprobación:
--    ghci> quickCheck prop_listaOrdenada_correcta
--    +++ OK, passed 100 tests.

-- Propiedad. Al eliminar las repeticiones en las listas producidas por el
-- generador orderedList se obtienen listas ordenadas.  
prop_orderedList_correcta :: [Int] -> Property
prop_orderedList_correcta xs = 
    forAll orderedList (ordenada . nub)

-- Comprobación:
--    ghci> quickCheck prop_orderedList_correcta
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Propiedades                                                        --
-- ---------------------------------------------------------------------

-- Propiedades de vacio
-- --------------------

-- Prop. vacio es un ABB.
prop_vacio_es_ABB :: Bool
prop_vacio_es_ABB =
    valido (vacio :: ABB Int)

-- Comprobación:
--    ghci> quickCheck prop_vacio_es_ABB
--    +++ OK, passed 100 tests.

-- Propiedades de inserta
-- ----------------------

-- Propiedad. Si a es un ABB, entonces (inserta v a) también lo es.
prop_inserta_es_valida :: Int -> ABB Int -> Bool
prop_inserta_es_valida v a =
    valido (inserta v a)

-- Comprobación:
--    ghci> quickCheck prop_inserta_es_valida
--    +++ OK, passed 100 tests.

-- Propiedad. El árbol que resulta de añadir un elemento a un ABB es no
-- vacío. 
prop_inserta_es_no_vacio :: Int -> ABB Int -> Bool
prop_inserta_es_no_vacio x a =
    inserta x a /= vacio

-- Comprobación.
--    ghci> quickCheck prop_inserta_es_no_vacio
--    +++ OK, passed 100 tests.

-- Propiedad. Para todo x y a, x es un elemento de (inserta x a). 
prop_elemento_de_inserta :: Int -> ABB Int -> Bool
prop_elemento_de_inserta x a =
    pertenece x (inserta x a)

-- Comprobación:
--    ghci> quickCheck prop_elemento_de_inserta
--    +++ OK, passed 100 tests.

-- Propiedades de pertenece
-- ------------------------

-- Propiedad. En en árbol vacio no hay ningún elemento.
prop_vacio_sin_elementos :: Int -> Bool
prop_vacio_sin_elementos x =
    not (pertenece x vacio)

-- Comprobación:
--    ghci> quickCheck prop_vacio_sin_elementos
--    +++ OK, passed 100 tests.

-- Propiedad. Los elementos de (inserta x a) son x y los elementos de
-- a. 
prop_elementos_de_inserta :: Int -> Int -> ABB Int -> Bool
prop_elementos_de_inserta x y a =
    pertenece y (inserta x a) == (x == y) || pertenece y a

-- Comprobación.
--    ghci> quickCheck prop_elementos_de_inserta
--    +++ OK, passed 100 tests.

-- Propiedades de elimina
-- ----------------------

-- Propiedad. Si a es un ABB, entonces (elimina v a) también lo es.
prop_elimina_es_valida :: Int -> ABB Int -> Bool
prop_elimina_es_valida v a = 
    valido (elimina v a)

-- Comprobación:
--    ghci> quickCheck prop_elimina_es_valida
--    +++ OK, passed 100 tests.

-- Prop. El resultado de eliminar el elemento x en (inserta x a) es
-- (elimina x a). 
prop_elimina_agrega :: Int -> ABB Int -> Bool
prop_elimina_agrega x a =
    elimina x (inserta x a) == elimina x a

-- Comprobación
--    ghci> quickCheck prop_elimina_agrega
--    +++ OK, passed 100 tests.

-- Propiedades de crea
-- -------------------

-- Propiedad. (crea xs) es un ABB.
prop_crea_es_valida :: [Int] -> Bool
prop_crea_es_valida xs =
    valido (crea xs)

-- Comprobación:
--    ghci> quickCheck prop_crea_es_valida
--    +++ OK, passed 100 tests.

-- Propiedades de crea'
-- --------------------

-- Propiedad. Para todas las listas ordenadas xs, se tiene que (crea' xs)
-- es un ABB.
prop_crea'_es_valida :: [Int] -> Property
prop_crea'_es_valida xs =
    forAll listaOrdenada (valido . crea')

-- Comprobación:
--    ghci> quickCheck prop_crea'_es_valida
--    +++ OK, passed 100 tests.

-- Propiedades de elementos
-- ------------------------

-- Propiedad. (elementos (crea xs)) es igual a la lista xs ordenada y
-- sin repeticiones. 
prop_elementos_crea :: [Int] -> Bool
prop_elementos_crea xs =
    elementos (crea xs) == sort (nub xs)

-- Comprobación
--    ghci> quickCheck prop_elementos_crea
--    +++ OK, passed 100 tests.

-- Propiedad. Si ys es una lista ordenada sin repeticiones, entonces
-- (elementos (crea' ys)) es igual ys. 
prop_elementos_crea' :: [Int] -> Bool
prop_elementos_crea' xs =
    elementos (crea' ys) == ys
    where ys = sort (nub xs)

-- Comprobación
--    ghci> quickCheck prop_elementos_crea'
--    +++ OK, passed 100 tests.

-- Propiedad. Un elemento pertenece a (elementos a) syss es un valor de a.
prop_en_elementos :: Int -> ABB Int -> Bool
prop_en_elementos v a =
    pertenece v a == elem v (elementos a)

-- Comprobación:
--    ghci> quickCheck prop_enElementos''
--    +++ OK, passed 100 tests.

-- Propiedades de menor
-- --------------------

-- Propiedad. (menor a) es menor o igual que todos los elementos de ABB
-- a. 
prop_menoresMinimo ::Int -> ABB Int -> Bool
prop_menoresMinimo v a =
    and [menor a <= v | v <- elementos a]

-- Comprobación.
--    ghci> quickCheck prop_menoresMinimo
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

{-# LANGUAGE FlexibleInstances #-}

import ArbolBin

import Data.List

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- Generador de ABB --

-- ---------------------------------------------------------------------

-- genABB es un generador de árboles binarios de búsqueda. Por ejemplo,

-- ghci> sample genABB

-- -

-- (1 (-1 - -) -)

-- (1 - -)

-- (-1 (-3 - -) (1 - (4 - -)))

-- -

-- (10 (-7 - -) -)

-- (1 (-9 - -) (7 (5 - -) (10 - -)))

-- ...

genABB :: Gen (ABB Int)

genABB = do xs <- listOf arbitrary

return (foldr inserta vacio xs)

-- Los árboles binarios de búsqueda son concreciones de la clase

-- arbitraria.

instance Arbitrary (ABB Int) where

arbitrary = genABB

-- Propiedad. Todo los elementos generados por genABB son árboles binarios

-- de búsqueda.

prop_genABB_correcto :: ABB Int -> Bool

prop_genABB_correcto = valido

-- Comprobación.

-- ghci> quickCheck prop_genABB_correcto

-- +++ OK, passed 100 tests.

-- listaOrdenada es un generador de listas ordenadas de números

-- enteros. Por ejemplo,

-- ghci> sample listaOrdenada

-- [1]

-- [-2,-1,0]

-- [-1,0,1]

-- [-8,-5,-4,-3,3,4,8]

-- [-6,-3,8]

-- [-14,-13]

-- [-31,-23,-16,-13,-11,-5,1,4,11,14,15,21,26,29]

-- []

listaOrdenada :: Gen [Int]

listaOrdenada =

frequency [(1,return []),

(4,do xs <- orderedList

n <- arbitrary

return (nub ((case xs of

[] -> n

x:_ -> n `min` x)

:xs)))]

-- (ordenada xs) se verifica si xs es una lista ordenada creciente. Por

-- ejemplo,

-- ordenada [3,5,9] == True

-- ordenada [3,9,5] == False

ordenada :: [Int] -> Bool

ordenada xs = and [x<y | (x,y) <- zip xs (tail xs)]

-- Propiedad. El generador listaOrdenada produce listas ordenadas.

prop_listaOrdenada_correcta :: [Int] -> Property

prop_listaOrdenada_correcta xs =

forAll listaOrdenada ordenada

-- Comprobación:

-- ghci> quickCheck prop_listaOrdenada_correcta

-- +++ OK, passed 100 tests.

-- Propiedad. Al eliminar las repeticiones en las listas producidas por el

-- generador orderedList se obtienen listas ordenadas.

prop_orderedList_correcta :: [Int] -> Property

prop_orderedList_correcta xs =

forAll orderedList (ordenada . nub)

-- Comprobación:

-- ghci> quickCheck prop_orderedList_correcta

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Propiedades --

-- ---------------------------------------------------------------------

-- Propiedades de vacio

-- --------------------

-- Prop. vacio es un ABB.

prop_vacio_es_ABB :: Bool

prop_vacio_es_ABB =

valido (vacio :: ABB Int)

-- Comprobación:

-- ghci> quickCheck prop_vacio_es_ABB

-- +++ OK, passed 100 tests.

-- Propiedades de inserta

-- ----------------------

-- Propiedad. Si a es un ABB, entonces (inserta v a) también lo es.

prop_inserta_es_valida :: Int -> ABB Int -> Bool

prop_inserta_es_valida v a =

valido (inserta v a)

-- Comprobación:

-- ghci> quickCheck prop_inserta_es_valida

-- +++ OK, passed 100 tests.

-- Propiedad. El árbol que resulta de añadir un elemento a un ABB es no

-- vacío.

prop_inserta_es_no_vacio :: Int -> ABB Int -> Bool

prop_inserta_es_no_vacio x a =

inserta x a /= vacio

-- Comprobación.

-- ghci> quickCheck prop_inserta_es_no_vacio

-- +++ OK, passed 100 tests.

-- Propiedad. Para todo x y a, x es un elemento de (inserta x a).

prop_elemento_de_inserta :: Int -> ABB Int -> Bool

prop_elemento_de_inserta x a =

pertenece x (inserta x a)

-- Comprobación:

-- ghci> quickCheck prop_elemento_de_inserta

-- +++ OK, passed 100 tests.

-- Propiedades de pertenece

-- ------------------------

-- Propiedad. En en árbol vacio no hay ningún elemento.

prop_vacio_sin_elementos :: Int -> Bool

prop_vacio_sin_elementos x =

not (pertenece x vacio)

-- Comprobación:

-- ghci> quickCheck prop_vacio_sin_elementos

-- +++ OK, passed 100 tests.

-- Propiedad. Los elementos de (inserta x a) son x y los elementos de

-- a.

prop_elementos_de_inserta :: Int -> Int -> ABB Int -> Bool

prop_elementos_de_inserta x y a =

pertenece y (inserta x a) == (x == y) || pertenece y a

-- Comprobación.

-- ghci> quickCheck prop_elementos_de_inserta

-- +++ OK, passed 100 tests.

-- Propiedades de elimina

-- ----------------------

-- Propiedad. Si a es un ABB, entonces (elimina v a) también lo es.

prop_elimina_es_valida :: Int -> ABB Int -> Bool

prop_elimina_es_valida v a =

valido (elimina v a)

-- Comprobación:

-- ghci> quickCheck prop_elimina_es_valida

-- +++ OK, passed 100 tests.

-- Prop. El resultado de eliminar el elemento x en (inserta x a) es

-- (elimina x a).

prop_elimina_agrega :: Int -> ABB Int -> Bool

prop_elimina_agrega x a =

elimina x (inserta x a) == elimina x a

-- Comprobación

-- ghci> quickCheck prop_elimina_agrega

-- +++ OK, passed 100 tests.

-- Propiedades de crea

-- -------------------

-- Propiedad. (crea xs) es un ABB.

prop_crea_es_valida :: [Int] -> Bool

prop_crea_es_valida xs =

valido (crea xs)

-- Comprobación:

-- ghci> quickCheck prop_crea_es_valida

-- +++ OK, passed 100 tests.

-- Propiedades de crea'

-- --------------------

-- Propiedad. Para todas las listas ordenadas xs, se tiene que (crea' xs)

-- es un ABB.

prop_crea'_es_valida :: [Int] -> Property

prop_crea'_es_valida xs =

forAll listaOrdenada (valido . crea')

-- Comprobación:

-- ghci> quickCheck prop_crea'_es_valida

-- +++ OK, passed 100 tests.

-- Propiedades de elementos

-- ------------------------

-- Propiedad. (elementos (crea xs)) es igual a la lista xs ordenada y

-- sin repeticiones.

prop_elementos_crea :: [Int] -> Bool

prop_elementos_crea xs =

elementos (crea xs) == sort (nub xs)

-- Comprobación

-- ghci> quickCheck prop_elementos_crea

-- +++ OK, passed 100 tests.

-- Propiedad. Si ys es una lista ordenada sin repeticiones, entonces

-- (elementos (crea' ys)) es igual ys.

prop_elementos_crea' :: [Int] -> Bool

prop_elementos_crea' xs =

elementos (crea' ys) == ys

where ys = sort (nub xs)

-- Comprobación

-- ghci> quickCheck prop_elementos_crea'

-- +++ OK, passed 100 tests.

-- Propiedad. Un elemento pertenece a (elementos a) syss es un valor de a.

prop_en_elementos :: Int -> ABB Int -> Bool

prop_en_elementos v a =

pertenece v a == elem v (elementos a)

-- Comprobación:

-- ghci> quickCheck prop_enElementos''

-- +++ OK, passed 100 tests.

-- Propiedades de menor

-- --------------------

-- Propiedad. (menor a) es menor o igual que todos los elementos de ABB

-- a.

prop_menoresMinimo ::Int -> ABB Int -> Bool

prop_menoresMinimo v a =

and [menor a <= v | v <- elementos a]

-- Comprobación.

-- ghci> quickCheck prop_menoresMinimo

-- +++ OK, passed 100 tests.

El objetivo de la serie es la elaboración de los temas de TAD del curso de Informática del Grado en Matemáticas.

La signatura del TAD de los árboles binarios de búsqueda

Propiedades del TAD de los árboles binarios de búsqueda

Implementación de los árboles binarios de búsqueda mediante tipos de datos algebraicos

Propiedades de los árboles binarios de búsqueda

Se puede imprimir o compartir con

Like this: