El árbol binario
se puede representar por
N 9 (N 3 (H 2) (H 4)) (H 7) |
N 9 (N 3 (H 2) (H 4)) (H 7)
El tipo de los árboles binarios se puede definir por
data Arbol a = H a
| N a (Arbol a) (Arbol a)
deriving (Show, Eq) |
data Arbol a = H a
| N a (Arbol a) (Arbol a)
deriving (Show, Eq)
Definir las funciones
repeatArbol :: a -> Arbol a
replicateArbol :: Int -> a -> Arbol a |
repeatArbol :: a -> Arbol a
replicateArbol :: Int -> a -> Arbol a
tales que
repeatArbol x
es es árbol con infinitos nodos x
. Por ejemplo,
takeArbol 0 (repeatArbol 3) == H 3
takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)
takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3)) |
takeArbol 0 (repeatArbol 3) == H 3
takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)
takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))
replicate n x
es el árbol de profundidad n
cuyos nodos son x
. Por ejemplo,
replicateArbol 0 5 == H 5
replicateArbol 1 5 == N 5 (H 5) (H 5)
replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5)) |
replicateArbol 0 5 == H 5
replicateArbol 1 5 == N 5 (H 5) (H 5)
replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))
Comprobar con QuickCheck que el número de hojas de replicateArbol n x
es 2^n
, para todo número natural n
.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Soluciones en Haskell
import Test.QuickCheck
data Arbol a = H a
| N a (Arbol a) (Arbol a)
deriving (Show, Eq)
repeatArbol :: a -> Arbol a
repeatArbol x = N x t t
where t = repeatArbol x
replicateArbol :: Int -> a -> Arbol a
replicateArbol n = takeArbol n . repeatArbol
-- (takeArbol n t) es el subárbol de t de profundidad n. Por ejemplo,
-- takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
-- takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
-- takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
-- takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
takeArbol :: Int -> Arbol a -> Arbol a
takeArbol _ (H x) = H x
takeArbol 0 (N x _ _) = H x
takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)
-- Generador para las comprobaciones
-- =================================
-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
-- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
-- N 0 (H 0) (H 0)
-- N 1 (N (-2) (H (-1)) (H 1)) (H 2)
-- N 3 (H 1) (H 2)
-- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))
-- H 7
-- N (-8) (H (-8)) (H 9)
-- H 2
-- N (-1) (H 7) (N 9 (H (-2)) (H (-8)))
-- H (-3)
-- N 0 (N 16 (H (-14)) (H (-18))) (H 7)
-- N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario 0 = H <$> arbitrary
arbolArbitrario n =
oneof [H <$> arbitrary,
N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]
-- Arbol es subclase de Arbitrary
instance Arbitrary a => Arbitrary (Arbol a) where
arbitrary = sized arbolArbitrario
-- Función auxiliar para la comprobación
-- =====================================
-- (nHojas x) es el número de hojas del árbol x. Por ejemplo,
-- nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3
nHojas :: Arbol a -> Int
nHojas (H _) = 1
nHojas (N _ i d) = nHojas i + nHojas d
-- Comprobación de la propiedad
-- ============================
-- La propiedad es
prop_replicateArbol :: Int -> Int -> Property
prop_replicateArbol n x =
n >= 0 ==> nHojas (replicateArbol n x) == 2^n
-- La comprobación es
-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol
-- +++ OK, passed 100 tests. |
import Test.QuickCheck
data Arbol a = H a
| N a (Arbol a) (Arbol a)
deriving (Show, Eq)
repeatArbol :: a -> Arbol a
repeatArbol x = N x t t
where t = repeatArbol x
replicateArbol :: Int -> a -> Arbol a
replicateArbol n = takeArbol n . repeatArbol
-- (takeArbol n t) es el subárbol de t de profundidad n. Por ejemplo,
-- takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
-- takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
-- takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
-- takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
takeArbol :: Int -> Arbol a -> Arbol a
takeArbol _ (H x) = H x
takeArbol 0 (N x _ _) = H x
takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)
-- Generador para las comprobaciones
-- =================================
-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
-- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
-- N 0 (H 0) (H 0)
-- N 1 (N (-2) (H (-1)) (H 1)) (H 2)
-- N 3 (H 1) (H 2)
-- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))
-- H 7
-- N (-8) (H (-8)) (H 9)
-- H 2
-- N (-1) (H 7) (N 9 (H (-2)) (H (-8)))
-- H (-3)
-- N 0 (N 16 (H (-14)) (H (-18))) (H 7)
-- N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario 0 = H <$> arbitrary
arbolArbitrario n =
oneof [H <$> arbitrary,
N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]
-- Arbol es subclase de Arbitrary
instance Arbitrary a => Arbitrary (Arbol a) where
arbitrary = sized arbolArbitrario
-- Función auxiliar para la comprobación
-- =====================================
-- (nHojas x) es el número de hojas del árbol x. Por ejemplo,
-- nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3
nHojas :: Arbol a -> Int
nHojas (H _) = 1
nHojas (N _ i d) = nHojas i + nHojas d
-- Comprobación de la propiedad
-- ============================
-- La propiedad es
prop_replicateArbol :: Int -> Int -> Property
prop_replicateArbol n x =
n >= 0 ==> nHojas (replicateArbol n x) == 2^n
-- La comprobación es
-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol
-- +++ OK, passed 100 tests.
Soluciones en Python
from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar
from hypothesis import given
from hypothesis import strategies as st
A = TypeVar("A")
@dataclass
class Arbol(Generic[A]):
pass
@dataclass
class H(Arbol[A]):
x: A
@dataclass
class N(Arbol[A]):
x: A
i: Arbol[A]
d: Arbol[A]
def replicateArbol(n: int, x: A) -> Arbol[A]:
match n:
case 0:
return H(x)
case n:
t = replicateArbol(n - 1, x)
return N(x, t, t)
assert False
# Generador para las comprobaciones
# =================================
# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
# >>> arbolArbitrario(4)
# N(x=2, i=H(x=1), d=H(x=9))
# >>> arbolArbitrario(4)
# H(x=10)
# >>> arbolArbitrario(4)
# N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))
def arbolArbitrario(n: int) -> Arbol[int]:
if n <= 1:
return H(randint(0, 10))
m = n // 2
return choice([H(randint(0, 10)),
N(randint(0, 10),
arbolArbitrario(m),
arbolArbitrario(m))])
# Función auxiliar para la comprobación
# =====================================
# nHojas(x) es el número de hojas del árbol x. Por ejemplo,
# nHojas(N(9, N(3, H(2), H(4)), H(7))) == 3
def nHojas(a: Arbol[A]) -> int:
match a:
case H(_):
return 1
case N(_, i, d):
return nHojas(i) + nHojas(d)
assert False
# Comprobación de la propiedad
# ============================
# La propiedad es
@given(st.integers(min_value=1, max_value=10),
st.integers(min_value=1, max_value=10))
def test_nHojas(n: int, x: int) -> None:
assert nHojas(replicateArbol(n, x)) == 2**n
# La comprobación es
# src> poetry run pytest -q arbol_de_profundidad_n_con_nodos_iguales.py
# 1 passed in 0.20s |
from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar
from hypothesis import given
from hypothesis import strategies as st
A = TypeVar("A")
@dataclass
class Arbol(Generic[A]):
pass
@dataclass
class H(Arbol[A]):
x: A
@dataclass
class N(Arbol[A]):
x: A
i: Arbol[A]
d: Arbol[A]
def replicateArbol(n: int, x: A) -> Arbol[A]:
match n:
case 0:
return H(x)
case n:
t = replicateArbol(n - 1, x)
return N(x, t, t)
assert False
# Generador para las comprobaciones
# =================================
# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
# >>> arbolArbitrario(4)
# N(x=2, i=H(x=1), d=H(x=9))
# >>> arbolArbitrario(4)
# H(x=10)
# >>> arbolArbitrario(4)
# N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))
def arbolArbitrario(n: int) -> Arbol[int]:
if n <= 1:
return H(randint(0, 10))
m = n // 2
return choice([H(randint(0, 10)),
N(randint(0, 10),
arbolArbitrario(m),
arbolArbitrario(m))])
# Función auxiliar para la comprobación
# =====================================
# nHojas(x) es el número de hojas del árbol x. Por ejemplo,
# nHojas(N(9, N(3, H(2), H(4)), H(7))) == 3
def nHojas(a: Arbol[A]) -> int:
match a:
case H(_):
return 1
case N(_, i, d):
return nHojas(i) + nHojas(d)
assert False
# Comprobación de la propiedad
# ============================
# La propiedad es
@given(st.integers(min_value=1, max_value=10),
st.integers(min_value=1, max_value=10))
def test_nHojas(n: int, x: int) -> None:
assert nHojas(replicateArbol(n, x)) == 2**n
# La comprobación es
# src> poetry run pytest -q arbol_de_profundidad_n_con_nodos_iguales.py
# 1 passed in 0.20s