Haskll, сбалансированная по высоте проверка

Question

Есть ли способ конвертировать это, чтобы он проверял баланс в зависимости от высоты? (Предполагается, что это то, что проблема есть.)

size :: Tree a -> Int 
size (Leaf n) = 1 
size (Node x z) = size x + size z + 1 

isBalanced :: Tree a -> Bool 
isBalanced (Leaf _) = True 
isBalanced (Node l r) = 
    let diff = abs (size l - size r) in 
    diff <= 1 && isBalanced l && isBalanced r 

Например:

isBalanced (Node (Node (Leaf 1)(Leaf 3)) (Leaf 2))) = True (Currently returns False) 
isBalanced (Node (Node (Leaf 1)(Node (Leaf 1)(Leaf 3))) (Leaf 2))) = False 

Answer 1

Кажется, что size подсчитывает общее количество узлов. Если вы хотите, чтобы вычислить (максимальную) высоту вместо этого, вы хотите что-то вроде этого:

height :: Tree x -> Int 
height (Leaf _) = 1 
height (Node x y) = 1 + (height x `max` height y) 

Если вы просто замените size с height, то isBalanced код должен работать, как и раньше.

ли это исправляет ваш проблема еще предстоит увидеть, конечно ...