Árboles balanceados
Los árboles binarios con valores en los nodos se pueden definir por
|
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
9 / \ / \ 8 6 / \ / \ 3 2 4 5 |
se puede representar por
|
1 |
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H)) |
Diremos que un árbol está balanceado si para cada nodo la diferencia entre el número de nodos de sus subárboles izquierdo y derecho es menor o igual que uno.
Definir la función
|
1 |
balanceado :: Arbol a -> Bool |
tal que (balanceado a) se verifica si el árbol a está balanceado. Por ejemplo,
|
1 2 3 4 |
λ> balanceado (N 5 H (N 3 H H)) True λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H)))) 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 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) balanceado :: Arbol a -> Bool balanceado H = True balanceado (N _ i d) = abs (numeroNodos i - numeroNodos d) <= 1 && balanceado i && balanceado d -- (numeroNodos a) es el número de nodos del árbol a. Por ejemplo, -- numeroNodos (N 5 H (N 3 H H)) == 2 numeroNodos :: Arbol a -> Int numeroNodos H = 0 numeroNodos (N _ i d) = 1 + numeroNodos i + numeroNodos d |
|
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 |
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): pass @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def numeroNodos(a: Arbol[A]) -> int: match a: case H(): return 0 case N(_, i, d): return 1 + numeroNodos(i) + numeroNodos(d) assert False def balanceado(a: Arbol[A]) -> bool: match a: case H(): return True case N(_, i, d): return abs(numeroNodos(i) - numeroNodos(d)) <= 1 \ and balanceado(i) and balanceado(d) assert False |