Árboles con bordes iguales
Los árboles binarios con valores en las hojas se pueden definir por
|
1 2 3 |
data Arbol a = H a | N (Arbol a) (Arbol a) deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
árbol1 árbol2 árbol3 árbol4 o o o o / \ / \ / \ / \ 1 o o 3 o 3 o 1 / \ / \ / \ / \ 2 3 1 2 1 4 2 3 |
se representan por
|
1 2 3 4 5 |
arbol1, arbol2, arbol3, arbol4 :: Arbol Int arbol1 = N (H 1) (N (H 2) (H 3)) arbol2 = N (N (H 1) (H 2)) (H 3) arbol3 = N (N (H 1) (H 4)) (H 3) arbol4 = N (N (H 2) (H 3)) (H 1) |
Definir la función
|
1 |
igualBorde :: Eq a => Arbol a -> Arbol a -> Bool |
tal que igualBorde t1 t2 se verifica si los bordes de los árboles t1 y t2 son iguales. Por ejemplo,
|
1 2 3 |
igualBorde arbol1 arbol2 == True igualBorde arbol1 arbol3 == False igualBorde arbol1 arbol4 == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
data Arbol a = N (Arbol a) (Arbol a) | H a deriving Show arbol1, arbol2, arbol3, arbol4 :: Arbol Int arbol1 = N (H 1) (N (H 2) (H 3)) arbol2 = N (N (H 1) (H 2)) (H 3) arbol3 = N (N (H 1) (H 4)) (H 3) arbol4 = N (N (H 2) (H 3)) (H 1) igualBorde :: Eq a => Arbol a -> Arbol a -> Bool igualBorde t1 t2 = borde t1 == borde t2 -- (borde t) es el borde del árbol t; es decir, la lista de las hojas -- del árbol t leídas de izquierda a derecha. Por ejemplo, -- borde arbol4 == [2,3,1] borde :: Arbol a -> [a] borde (N i d) = borde i ++ borde d borde (H x) = [x] |
|
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 |
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): x: A @dataclass class N(Arbol[A]): i: Arbol[A] d: Arbol[A] arbol1: Arbol[int] = N(H(1), N(H(2), H(3))) arbol2: Arbol[int] = N(N(H(1), H(2)), H(3)) arbol3: Arbol[int] = N(N(H(1), H(4)), H(3)) arbol4: Arbol[int] = N(N(H(2), H(3)), H(1)) # borde(t) es el borde del árbol t; es decir, la lista de las hojas # del árbol t leídas de izquierda a derecha. Por ejemplo, # borde(arbol4) == [2, 3, 1] def borde(a: Arbol[A]) -> list[A]: match a: case H(x): return [x] case N(i, d): return borde(i) + borde(d) assert False def igualBorde(t1: Arbol[A], t2: Arbol[A]) -> bool: return borde(t1) == borde(t2) |
Para resolver este problema podemos recorrer los dos árboles de manera simultánea comparando cada uno de sus nodos a lo largo del borde. Si alguno de ellos difiere, entonces los bordes no son iguales y podemos devolver falso. Si llegamos al final del recorrido sin encontrar diferencias, entonces los bordes son iguales y podemos devolver verdadero.
A continuación te presento una posible implementación de la función igualBorde:
La primera línea de la función se aplica cuando ambos árboles son hojas y simplemente comparamos los valores de las hojas. La segunda línea se aplica cuando ambos árboles son nodos y comparamos sus hijos izquierdo y derecho de manera recursiva. La tercera línea se aplica cuando los árboles son de tipos diferentes, lo cual significa que sus bordes no pueden ser iguales, por lo que devolvemos falso.
Con esta implementación, podemos comprobar que los ejemplos que has proporcionado en la pregunta producen los resultados esperados:
Solución en Lean3
Aquí tienes la implementación de la función igualBorde en Lean:
Primero se define el tipo de dato arbol mediante la inductiva arbol, y luego se crea un espacio de nombres para las funciones que vayamos a definir sobre él.
La función borde se implementa recursivamente siguiendo el mismo esquema que en la solución anterior. La función igualBorde simplemente compara si ambos bordes son iguales usando el operador =.
Para poder usar el operador = es necesario que el tipo α tenga la estructura de tipo decidable_eq, que permite determinar si dos elementos son iguales.
Puedes probar la función de la siguiente manera: