Á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 |
Podemos implementar la función balanceado utilizando recursión. Primero, debemos calcular el número de nodos en cada subárbol izquierdo y derecho de cada nodo. Luego, podemos comparar la diferencia entre el número de nodos de cada subárbol y verificar si es menor o igual a uno.
Aquí está una posible implementación de la función balanceado:
La función balanceado recorre el árbol en profundidad y verifica si cada nodo cumple con la condición de balanceado. La función nodos cuenta el número de nodos en un subárbol dado.
Para probar la función balanceado, podemos utilizar los ejemplos que has proporcionado: