-- |
-- Module      : ArbolBin
-- Description : TAD de los árboles binarios de búsqueda.
-- License     : Creative Commons
-- Maintainer  : José A. Alonso
-- 
-- == 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 <http://bit.ly/1F5RFgF 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])

module I1M.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

-- | El tipo de dato de los ABB,
data ABB a = Vacio
           | Nodo a (ABB a) (ABB a)
  deriving ABB a -> ABB a -> Bool
(ABB a -> ABB a -> Bool) -> (ABB a -> ABB a -> Bool) -> Eq (ABB a)
forall a. Eq a => ABB a -> ABB a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ABB a -> ABB a -> Bool
$c/= :: forall a. Eq a => ABB a -> ABB a -> Bool
== :: ABB a -> ABB a -> Bool
$c== :: forall a. Eq a => ABB a -> ABB a -> Bool
Eq

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

-- 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 :: ABB a
vacio = ABB a
forall a. ABB a
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 :: a -> ABB a -> Bool
pertenece a
_  ABB a
Vacio = Bool
False
pertenece a
v' (Nodo a
v ABB a
i ABB a
d)
  | a
v a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
v'   = Bool
True  
  | a
v' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
v    = a -> ABB a -> Bool
forall a. (Ord a, Show a) => a -> ABB a -> Bool
pertenece a
v' ABB a
i
  | Bool
otherwise = a -> ABB a -> Bool
forall a. (Ord a, Show a) => a -> ABB a -> Bool
pertenece a
v' ABB a
d

-- pertenece requiere O(n) paso en el peor caso O(n) y O(log n) en el mejor,
-- donde n es el número de nodos del ABB. 

-- | (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 :: a -> ABB a -> ABB a
inserta a
v' ABB a
Vacio = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
v' ABB a
forall a. ABB a
Vacio ABB a
forall a. ABB a
Vacio
inserta a
v' (Nodo a
v ABB a
i ABB a
d) 
  | a
v' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
v   = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
v ABB a
i ABB a
d
  | a
v' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
v    = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
v (a -> ABB a -> ABB a
forall a. (Ord a, Show a) => a -> ABB a -> ABB a
inserta a
v' ABB a
i) ABB a
d
  | Bool
otherwise = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
v ABB a
i (a -> ABB a -> ABB a
forall a. (Ord a, Show a) => a -> ABB a -> ABB a
inserta a
v' ABB a
d)

-- inserta requiere O(n) pasos en el peor caso y O(log n) en el mejor.
                                        
-- | (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 :: [a] -> ABB a
crea = (a -> ABB a -> ABB a) -> ABB a -> [a] -> ABB a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> ABB a -> ABB a
forall a. (Ord a, Show a) => a -> ABB a -> ABB a
inserta ABB a
forall a. ABB a
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' :: [a] -> ABB a
crea' [] = ABB a
forall a. ABB a
Vacio
crea' [a]
vs = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
x ([a] -> ABB a
forall a. (Ord a, Show a) => [a] -> ABB a
crea' [a]
l1) ([a] -> ABB a
forall a. (Ord a, Show a) => [a] -> ABB a
crea' [a]
l2)
  where n :: Int
n      = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
vs Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
        l1 :: [a]
l1     = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
n [a]
vs
        (a
x:[a]
l2) = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
n [a]
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 :: ABB a -> [a]
elementos ABB a
Vacio        = []
elementos (Nodo a
v ABB a
i ABB a
d) = ABB a -> [a]
forall a. (Ord a, Show a) => ABB a -> [a]
elementos ABB a
i [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
v] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ ABB a -> [a]
forall a. (Ord a, Show a) => ABB a -> [a]
elementos ABB a
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 :: a -> ABB a -> ABB a
elimina a
_ ABB a
Vacio = ABB a
forall a. ABB a
Vacio 
elimina a
v' (Nodo a
v ABB a
i ABB a
Vacio) | a
v'a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
v = ABB a
i 
elimina a
v' (Nodo a
v ABB a
Vacio ABB a
d) | a
v'a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
v = ABB a
d
elimina a
v' (Nodo a
v ABB a
i ABB a
d)
  | a
v' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
v    = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
v (a -> ABB a -> ABB a
forall a. (Ord a, Show a) => a -> ABB a -> ABB a
elimina a
v' ABB a
i) ABB a
d 
  | a
v' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
v    = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
v ABB a
i (a -> ABB a -> ABB a
forall a. (Ord a, Show a) => a -> ABB a -> ABB a
elimina a
v' ABB a
d)  
  | Bool
otherwise = a -> ABB a -> ABB a -> ABB a
forall a. a -> ABB a -> ABB a -> ABB a
Nodo a
k ABB a
i (a -> ABB a -> ABB a
forall a. (Ord a, Show a) => a -> ABB a -> ABB a
elimina a
k ABB a
d)
  where k :: a
k = ABB a -> a
forall a. Ord a => ABB a -> a
menor ABB a
d 

-- | (menor a) es el mínimo valor del ABB a. Por ejemplo,
-- 
-- > menor abb1  ==  2
menor :: Ord a => ABB a -> a
menor :: ABB a -> a
menor (Nodo a
v ABB a
Vacio ABB a
_) = a
v
menor (Nodo a
_ ABB a
i ABB a
_)     = ABB a -> a
forall a. Ord a => ABB a -> a
menor ABB a
i 
menor ABB a
Vacio            = String -> a
forall a. HasCallStack => String -> a
error String
"No tiene"

-- | (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 :: a -> ABB a -> Bool
menorTodos a
_ ABB a
Vacio = Bool
True 
menorTodos a
v ABB a
a        = a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum (ABB a -> [a]
forall a. (Ord a, Show a) => ABB a -> [a]
elementos ABB a
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 :: a -> ABB a -> Bool
mayorTodos a
_ ABB a
Vacio = Bool
True 
mayorTodos a
v ABB a
a = a
v a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum (ABB a -> [a]
forall a. (Ord a, Show a) => ABB a -> [a]
elementos ABB a
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 :: ABB a -> Bool
valido ABB a
Vacio = Bool
True
valido (Nodo a
v ABB a
a ABB a
b) =
  a -> ABB a -> Bool
forall a. (Ord a, Show a) => a -> ABB a -> Bool
mayorTodos a
v ABB a
a Bool -> Bool -> Bool
&&
  a -> ABB a -> Bool
forall a. (Ord a, Show a) => a -> ABB a -> Bool
menorTodos a
v ABB a
b Bool -> Bool -> Bool
&& 
  ABB a -> Bool
forall a. (Ord a, Show a) => ABB a -> Bool
valido ABB a
a Bool -> Bool -> Bool
&&
  ABB a -> Bool
forall a. (Ord a, Show a) => ABB a -> Bool
valido ABB a
b