Relaciones arbóreas
Como se explica en el ejercicio Relación definida por un árbol, cada árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y.
Una relación binaria es arbórea si
- hay exactamente un elemento que no tiene ningún (la raíz del árbol) y
- todos los elementos tienen dos hijos (los nodos internos) o ninguno (las hojas del árbol).
Definir la función
1 |
arborea :: Eq a => [(a,a)] -> Bool |
tal que (arborea r) se verifica si la relación r es arbórea. Por ejemplo,
1 2 3 |
arborea [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] == True arborea [(8,3),(8,5),(10,2),(2,2),(2,0)] == False arborea [(10,8),(8,3),(8,5),(10,2),(8,2),(2,0)] == False |
Soluciones
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 34 35 36 37 38 39 40 41 42 43 |
import Data.List ((\\), elemIndices, isPrefixOf, nub, sort) -- 1ª solución -- =========== arborea :: Eq a => [(a,a)] -> Bool arborea r = length [x | x <- nodos r, null (padres r x)] == 1 && all (`elem` [0,2]) [length (hijos r x) | x <- nodos r] -- (nodos r) es el conjunto de los nodos de la relación r. Por ejemplo, -- λ> nodos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] -- [10,8,3,5,2,0] nodos :: Eq a => [(a,a)] -> [a] nodos r = nub (concat [[x,y] | (x,y) <- r]) -- (padres r x) es la lista de los padres de x en la relación r. Por -- ejemplo, -- padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 8 == [10] -- padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10 == [] padres :: Eq a => [(a,a)] -> a -> [a] padres r x = [y | (y,x') <- r, x' == x] -- (hijos r x) es la lista de los hijos de x en la relación r. Por -- ejemplo, -- hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10 == [8,2] -- hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 5 == [] hijos :: Eq a => [(a,a)] -> a -> [a] hijos r x = [y | (x',y) <- r, x' == x] -- 2ª solución -- =========== arborea2 :: Eq a => [(a,a)] -> Bool arborea2 xs = length (nub padres \\ nub hijos) == 1 && and [cuenta x padres == 2 | x <- nub padres] where (padres, hijos) = unzip xs -- (cuenta x ys) es el número de ocurrencias de x en ys. Por ejemplo, -- cuenta 7 [7,2,7,7,5] == 3 cuenta :: Eq a => a -> [a] -> Int cuenta i = length . elemIndices i |
Una solución que creo sirve para cualquier árbol (se repita o no la raíz o cualquier elemento).
Para comprobar la función podemos usar la función relacionDelArbol (definida en Relación definida por un árbol) y un generado de árboles y definir la propiedad de que toda relación dada por un árbol debe ser arbórea.
También podemos definir otra propuesta que sirve exclusivamente para árboles con padres como suma de hijos, como el del ejemplo, pero con un código bastante más simple.