Inserción en árboles binarios de búsqueda

PorJosé A. Alonso 17-julio-20141-mayo-2015

-- Un árbol binario de búsqueda (ABB) es un árbol binario tal que el 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 [8,4,2,6,3] en un ABB se puede obtener el
-- siguiente ABB:
-- 
--       5 
--      / \
--     /   \ 
--    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 binario de búsqueda 
-- obtenido añadiendo el valor v al ABB a, si no es uno 
-- de sus valores. Por ejemplo, 
--    ghci>  inserta 5 ej
--    N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V))
--    ghci>  inserta 1 ej
--    N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V))
--    ghci>  inserta 2 ej
--    N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

-- Un árbol binario de búsqueda (ABB) es un árbol binario tal que el 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 [8,4,2,6,3] en un ABB se puede obtener el

-- siguiente ABB:

--

-- 5

-- / \

-- / \

-- 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 binario de búsqueda

-- obtenido añadiendo el valor v al ABB a, si no es uno

-- de sus valores. Por ejemplo,

-- ghci> inserta 5 ej

-- N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V))

-- ghci> inserta 1 ej

-- N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V))

-- ghci> inserta 2 ej

-- N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

Soluciones

data ABB = V
         | N Int ABB ABB
         deriving (Eq, Show)

ej :: ABB 
ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

inserta :: Int -> ABB -> ABB
inserta v1 V = N v1 V V
inserta v1 (N v i d) 
    | v1 == v   = N v i d
    | v1 < v    = N v (inserta v1 i) d
    | otherwise = N v i (inserta v1 d)

1

2

3

4

5

6

7

8

9

10

11

12

13

data ABB = V

| N Int ABB ABB

deriving (Eq, Show)

ej :: ABB

ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

inserta :: Int -> ABB -> ABB

inserta v1 V = N v1 V V

inserta v1 (N v i d)

| v1 == v = N v i d

| v1 < v = N v (inserta v1 i) d

| otherwise = N v i (inserta v1 d)

4 Comentarios

inserta n (N x i d) | pertenece n (N x i d) = (N x i d)
                    | otherwise             = aux n (N x i d)
    where
      aux n (N x V V) | n < x = (N x (N n V V) V)
                      | n > x = (N x V (N n V V))
      aux n (N x i d) | n > x = (N x i (aux n d))
                      | n < x = (N x (aux n i) d) 

pertenece n (N x V V) = n == x
pertenece n (N x i d) | n == x    = True
                      | otherwise = pertenece n i || pertenece n d

1

2

3

4

5

6

7

8

9

10

11

inserta n (N x i d) | pertenece n (N x i d) = (N x i d)

| otherwise = aux n (N x i d)

where

aux n (N x V V) | n < x = (N x (N n V V) V)

| n > x = (N x V (N n V V))

aux n (N x i d) | n > x = (N x i (aux n d))

| n < x = (N x (aux n i) d)

pertenece n (N x V V) = n == x

pertenece n (N x i d) | n == x = True

| otherwise = pertenece n i || pertenece n d

La solución no es correcta porque le falta el caso base. Por ejemplo,

ghci> inserta 3 V
*** Exception: Non-exhaustive patterns in function inserta

1 2	ghci> inserta 3 V *** Exception: Non-exhaustive patterns in function inserta

y su valor es N 3 V V

Además, al considerar dicho caso la definición se puede simplificar.

Corrección:

inserta n (N x i d) | pertenece n (N x i d) = (N x i d)
                    | otherwise = aux n (N x i d)
    where
      aux n V = N n V V
      aux n (N x i d) | n > x = N x i (aux n d)
                      | n < x = N x (aux n i) d

pertenece n (N x V V) = n == x
pertenece n (N x i d) | n == x = True
                      | otherwise = pertenece n i || pertenece n d

1

2

3

4

5

6

7

8

9

10

inserta n (N x i d) | pertenece n (N x i d) = (N x i d)

| otherwise = aux n (N x i d)

where

aux n V = N n V V

aux n (N x i d) | n > x = N x i (aux n d)

| n < x = N x (aux n i) d

pertenece n (N x V V) = n == x

pertenece n (N x i d) | n == x = True

| otherwise = pertenece n i || pertenece n d

data ABB = V
         | N Int ABB ABB
         deriving (Eq, Show)

ej :: ABB
ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

inserta :: Int -> ABB -> ABB
inserta v V = N v V V
inserta v (N x i d)| v==x  = N x i d 
                   | v < x = N x (inserta v i) d
                   | otherwise = N x i (inserta v d)

1

2

3

4

5

6

7

8

9

10

11

12

data ABB = V

| N Int ABB ABB

deriving (Eq, Show)

ej :: ABB

ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

inserta :: Int -> ABB -> ABB

inserta v V = N v V V

inserta v (N x i d)| v==x = N x i d

| v < x = N x (inserta v i) d

| otherwise = N x i (inserta v d)

Escribe tu soluciónCancel reply