License	Creative Commons
Maintainer	José A. Alonso
Safe Haskell	Safe
Language	Haskell2010

I1M.Monticulo

Description

TAD (tipo abstracto de datos) de los montículos.

Este módulo contiene el código del TAD de los montículos estudiado en el tema 20 del curso.

Un montículo es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo, 1 / / 2 6 3 8 9 7 es un montículo, pero 1 / / 3 6 4 2 9 7 no lo es.

Synopsis

data Monticulo a
vacio :: Ord a => Monticulo a
inserta :: Ord a => a -> Monticulo a -> Monticulo a
menor :: Ord a => Monticulo a -> a
resto :: Ord a => Monticulo a -> Monticulo a
esVacio :: Ord a => Monticulo a -> Bool
valido :: Ord a => Monticulo a -> Bool

Documentation

data Monticulo a Source #

El tipo de dato de los montículos.

Instances

Ord a => Eq (Monticulo a) Source #
Instance details Defined in I1M.Monticulo Methods (==) :: Monticulo a -> Monticulo a -> Bool # (/=) :: Monticulo a -> Monticulo a -> Bool #
Show a => Show (Monticulo a) Source #
Instance details Defined in I1M.Monticulo Methods showsPrec :: Int -> Monticulo a -> ShowS # show :: Monticulo a -> String # showList :: [Monticulo a] -> ShowS #

vacio :: Ord a => Monticulo a Source #

vacio es el montículo vacío.

inserta :: Ord a => a -> Monticulo a -> Monticulo a Source #

(inserta x m) es el montículo obtenido añadiendo el elemento x al montículo m. Por ejemplo,

ghci> inserta 3 (foldr inserta vacio [6,1,4,8])
M 1 2 
  (M 4 1 (M 8 1 Vacio Vacio) Vacio) 
  (M 3 1 (M 6 1 Vacio Vacio) Vacio)

menor :: Ord a => Monticulo a -> a Source #

(menor m) es el menor elemento del montículo m. Por ejemplo,

menor (foldr inserta vacio [6,1,4,8])  ==  1
menor (foldr inserta vacio [7,5])      ==  5

resto :: Ord a => Monticulo a -> Monticulo a Source #

(resto m) es el montículo obtenido eliminando el menor elemento del montículo m. Por ejemplo,

ghci> resto (foldr inserta vacio [6,1,4,8])
M 4 2 (M 8 1 Vacio Vacio) (M 6 1 Vacio Vacio)

esVacio :: Ord a => Monticulo a -> Bool Source #

(esVacio m) se verifica si m es el montículo vacío.

valido :: Ord a => Monticulo a -> Bool Source #

(valido m) se verifica si m es un montículo; es decir, es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo,

valido (foldr inserta vacio [6,1,4,8])    ==  True
valido (foldr inserta vacio [7,5])        ==  True
valido (M 3 5 (M 2 1 Vacio Vacio) Vacio)  ==  False