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

I1M.ArbolBin

Description

TAD (tipo abstracto de datos) de los árboles binarios de búsqueda.

Este módulo contiene el código del TAD de los árboles binarios estudiado en el tema 19 del curso.

Un árbol binario de búsqueda (ABB) 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

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

En los ejemplos se usarán los siguientes ABB:

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])

Synopsis

data ABB a
vacio :: ABB a
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

Documentation

data ABB a Source #

El tipo de dato de los ABB,

Instances

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

vacio :: ABB a Source #

vacio es el ABB vacío. Por ejemplo,

ghci> vacio
 -

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

(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 - -))))

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

(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 - -))))

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

(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 Source #

(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 - -))

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

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

menor abb1  ==  2

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

(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]

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

(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

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

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

valido abb1 == True