Ancestro común más bajo

PorJosé A. Alonso 9-junio-201725-abril-2021

El tipo de los árboles binarios se define por

   data Arbol = H Int
              | N Int Arbol Arbol

1 2	data Arbol = H Int \| N Int Arbol Arbol

Por ejemplo, el árbol

        5
       / \
      /   \
     3     7
    / \   / \
   1   4 6   9

/ \

3 7

/ \ / \

1 4 6 9

se define por

   ejArbol :: Arbol
   ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

1 2	ejArbol :: Arbol ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

Un árbol ordenado es un árbol binario tal que para cada nodo, los elementos de su subárbol izquierdo son menores y los de su subárbol derecho son mayores. El árbol anterior es un árbol ordenado.

Los ancestros de un nodo x son los nodos y tales que x está en alguna de las ramas de x. Por ejemplo, en el árbol anterior los ancestros de 9 son 5 y 7.

El ancestro común más bajo de dos elementos x e y de un árbol a es el ancestro de x e y de menor profundidad. Por ejemplo, en el árbol anterior el ancestro común más bajo de 6 y 9 es 7.

Definir la función

   ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

1	ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

tal que (ancestroComunMasBajo a x y) es el ancestro de menor profundidad de los nodos x e y en el árbol ordenado a, donde x e y son dos elementos distintos del árbol a. Por ejemplo,

   ancestroComunMasBajo ejArbol 4 1  ==  3
   ancestroComunMasBajo ejArbol 1 6  ==  5
   ancestroComunMasBajo ejArbol 6 9  ==  7

ancestroComunMasBajo ejArbol 4 1 == 3

ancestroComunMasBajo ejArbol 1 6 == 5

ancestroComunMasBajo ejArbol 6 9 == 7

Soluciones

[schedule expon=’2017-06-16′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 16 de junio.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-06-16′ at=»06:00″]

data Arbol = H Int
           | N Int Arbol Arbol

ejArbol :: Arbol
ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

-- 1ª definición
-- =============

ancestroComunMasBajo1 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo1 a x y =
  head [u | u <- xs, u `elem` ys]
  where xs = ancestros a x
        ys = ancestros a y

-- (ancestros a x) es la lista de los ancestros de x en el árbol
-- ordenado a, ordenada por profundidad. Por ejemplo,
--    ancestros ejArbol 1 ==  [3,5]
--    ancestros ejArbol 3 ==  [5]
--    ancestros ejArbol 5 ==  []
--    ancestros ejArbol 9 ==  [7,5]
ancestros :: Arbol -> Int -> [Int]
ancestros a y = aux a y []
  where aux (H _)     _ zs = zs
        aux (N x i d) y zs 
          | x == y    = zs
          | y < x     = aux i y (x:zs)
          | otherwise = aux d y (x:zs)

-- 2ª definición
-- =============

ancestroComunMasBajo2 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo2 (N z i d) x y 
  | x < z && y < z = ancestroComunMasBajo2 i x y 
  | x > z && y > z = ancestroComunMasBajo2 d x y 
  | otherwise      = z

data Arbol = H Int

| N Int Arbol Arbol

ejArbol :: Arbol

ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

-- 1ª definición

-- =============

ancestroComunMasBajo1 :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo1 a x y =

head [u | u <- xs, u `elem` ys]

where xs = ancestros a x

ys = ancestros a y

-- (ancestros a x) es la lista de los ancestros de x en el árbol

-- ordenado a, ordenada por profundidad. Por ejemplo,

-- ancestros ejArbol 1 == [3,5]

-- ancestros ejArbol 3 == [5]

-- ancestros ejArbol 5 == []

-- ancestros ejArbol 9 == [7,5]

ancestros :: Arbol -> Int -> [Int]

ancestros a y = aux a y []

where aux (H _) _ zs = zs

aux (N x i d) y zs

| x == y = zs

| y < x = aux i y (x:zs)

| otherwise = aux d y (x:zs)

-- 2ª definición

-- =============

ancestroComunMasBajo2 :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo2 (N z i d) x y

| x < z && y < z = ancestroComunMasBajo2 i x y

| x > z && y > z = ancestroComunMasBajo2 d x y

| otherwise = z

[/schedule]

7 Comentarios

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo (N a b c) x y | x < a && y < a = ancestroComunMasBajo b x y
                                   | a < x && a < y = ancestroComunMasBajo c x y
                                   | otherwise = a

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo (N a b c) x y | x < a && y < a = ancestroComunMasBajo b x y

| a < x && a < y = ancestroComunMasBajo c x y

| otherwise = a

Responder

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo a x y = last ( intersect (ramaCon x a) (ramaCon y a))

ramaCon x a = head [ xs |  xs <- ramas a, x `elem` xs]

ramas :: Arbol -> [[Int]]

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo a x y = last ( intersect (ramaCon x a) (ramaCon y a))

ramaCon x a = head [ xs | xs <- ramas a, x `elem` xs]

ramas :: Arbol -> [[Int]]

ramas (H x) = [[x]]
ramas (N x i d) = [x:ys | ys <- ramas i ++ ramas d]

Responder

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo a x y = last ( intersect (ramaCon x a) (ramaCon y a))

ramaCon x a = head [ xs |  xs <- ramas a, x `elem` xs]

ramas :: Arbol -> [[Int]]
ramas (H x)     = [[x]]
ramas (N x i d) = [x:ys | ys <- ramas i ++ ramas d]

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo a x y = last ( intersect (ramaCon x a) (ramaCon y a))

ramaCon x a = head [ xs | xs <- ramas a, x `elem` xs]

ramas :: Arbol -> [[Int]]

ramas (H x) = [[x]]

ramas (N x i d) = [x:ys | ys <- ramas i ++ ramas d]

Responder

import qualified Data.Map.Lazy as M (intersectionWith, empty, map, toList, insert)
import Data.List (sort)

data Arbol = H Int
           | N Int Arbol Arbol

ejArbol :: Arbol
ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))
              
ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo (H _) x y = error "no existe ACMB"
ancestroComunMasBajo ar x y = encuentra $
                              M.intersectionWith (+)
                              (aux ar x M.empty)
                              (aux ar y M.empty)
  where aux (H a) x ac | a == x = ac
                       | otherwise = error "uno de los números dados no pertenece al árbol"
        aux (N a i d) x ac | a == x    = ac
                           | a <  x    = aux d x (M.insert a 0 ac')
                           | otherwise = aux i x (M.insert a 0 ac')
          where ac' = M.map (+1) ac
        encuentra = snd
                  . head
                  . sort
                  . map (\(x,y) -> (y,x))
                  . M.toList

import qualified Data.Map.Lazy as M (intersectionWith, empty, map, toList, insert)

import Data.List (sort)

data Arbol = H Int

| N Int Arbol Arbol

ejArbol :: Arbol

ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo (H _) x y = error "no existe ACMB"

ancestroComunMasBajo ar x y = encuentra $

M.intersectionWith (+)

(aux ar x M.empty)

(aux ar y M.empty)

where aux (H a) x ac | a == x = ac

| otherwise = error "uno de los números dados no pertenece al árbol"

aux (N a i d) x ac | a == x = ac

| a < x = aux d x (M.insert a 0 ac')

| otherwise = aux i x (M.insert a 0 ac')

where ac' = M.map (+1) ac

encuentra = snd

. head

. sort

. map (\(x,y) -> (y,x))

. M.toList

Responder

caminosHastaNodo :: Arbol -> Int -> [[Int]]
caminosHastaNodo (H x) n | x == n = [[x]]
                         | otherwise = []
caminosHastaNodo (N x i d) n | x == n = [[x]]
                             | otherwise = [x:ys | ys <- (caminosHastaNodo i n) ++ (caminosHastaNodo d n)]


ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo a x y = last ((head (caminosHastaNodo a x)) `intersect` (head (caminosHastaNodo a y)))

caminosHastaNodo :: Arbol -> Int -> [[Int]]

caminosHastaNodo (H x) n | x == n = [[x]]

| otherwise = []

caminosHastaNodo (N x i d) n | x == n = [[x]]

| otherwise = [x:ys | ys <- (caminosHastaNodo i n) ++ (caminosHastaNodo d n)]

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo a x y = last ((head (caminosHastaNodo a x)) `intersect` (head (caminosHastaNodo a y)))

Responder

import Data.List

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo a x y = head (intersect (ancestros x a) (ancestros y a))

ancestros :: Int -> Arbol -> [Int]
ancestros x xs = aux x xs []
          where aux a (H b) ys     | a == b    = ys
                                   | otherwise = []
                aux a (N b i d) ys | a == b    = ys
                                   | otherwise = aux a i (b:ys) ++ aux a d (b:ys)

import Data.List

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo a x y = head (intersect (ancestros x a) (ancestros y a))

ancestros :: Int -> Arbol -> [Int]

ancestros x xs = aux x xs []

where aux a (H b) ys | a == b = ys

| otherwise = []

aux a (N b i d) ys | a == b = ys

| otherwise = aux a i (b:ys) ++ aux a d (b:ys)

Responder

La definición utilizada sugiere que siempre existe tal ancestro, en tal caso, ni siquiera hace falta recorrer el árbol completamente hasta los nodos en cuestión, de hecho, es suficiente recorrer hasta el propio común de ambos (dado que podemos asumir que existe):

ancestroComunMasBajo :: Arbol ->Integer ->Integer ->Integer
ancestroComunMasBajo t u v = s t
  where s (N c a b) | u < c && v < c = s a
                    | u > c && v > c = s b
                    | otherwise     = c
        s (H c)                     = c





-- Por ejemplo, podemos construir árboles enormes donde
-- los nodos van del 1 al 2^n-1
construir :: Integer ->Arbol
construir size = m 1 (2^size - 1)
  where m a b | a == b     = H a
              | otherwise = let c = (a + b) `div` 2
                            in  N c (m a (c - 1)) (m (c + 1) b)


-- El nodo común entre 1 y 2^1234-1 es siempre el mismo para
-- cualquiera de los árboles como el anterior (de tamaño >= 1234)
--
-- Por ejemplo:
--
-- ancestroComunMasBajo (construir 1123) 1 (2^1123-1)
-- 56971169535859552651673922053729860865637486561612038919884150448180453661914876030559524836165804222520296002620373895898888826700892439717737601036402048250720345388614220594158194211326497047778268169743779974140336530352787765291564289626013508853409292148309539883979412357803110031516333770537681167444722944096508010537063813218304
-- ancestroComunMasBajo (construir 1123) 1 (2^1124-1)
-- 56971169535859552651673922053729860865637486561612038919884150448180453661914876030559524836165804222520296002620373895898888826700892439717737601036402048250720345388614220594158194211326497047778268169743779974140336530352787765291564289626013508853409292148309539883979412357803110031516333770537681167444722944096508010537063813218304

ancestroComunMasBajo :: Arbol ->Integer ->Integer ->Integer

ancestroComunMasBajo t u v = s t

where s (N c a b) | u < c && v < c = s a

| u > c && v > c = s b

| otherwise = c

s (H c) = c

-- Por ejemplo, podemos construir árboles enormes donde

-- los nodos van del 1 al 2^n-1

construir :: Integer ->Arbol

construir size = m 1 (2^size - 1)

where m a b | a == b = H a

| otherwise = let c = (a + b) `div` 2

in N c (m a (c - 1)) (m (c + 1) b)

-- El nodo común entre 1 y 2^1234-1 es siempre el mismo para

-- cualquiera de los árboles como el anterior (de tamaño >= 1234)

-- Por ejemplo:

-- ancestroComunMasBajo (construir 1123) 1 (2^1123-1)

-- 56971169535859552651673922053729860865637486561612038919884150448180453661914876030559524836165804222520296002620373895898888826700892439717737601036402048250720345388614220594158194211326497047778268169743779974140336530352787765291564289626013508853409292148309539883979412357803110031516333770537681167444722944096508010537063813218304

-- ancestroComunMasBajo (construir 1123) 1 (2^1124-1)

Responder

Ancestro común más bajo

Soluciones

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico