Проверка сбалансированности бинарного дерева в Haskell

Question

как еще один способ проверить, сбалансировано ли двоичное дерево, кроме рекурсивного вызова функции размера в левом и правом поддеревьях.abs (размер слева - размер справа) <= 1 для сбалансированного дерева.Я должен написать эффективную функцию для удовлетворения требований, но, как я уже сказал, рекурсивно не вызывать функцию размера в левом и правом поддеревьях. </p>

Answer 1

Так что с рекурсией это довольно просто, не так ли?

import Data.Maybe (isJust)

getBalancedSize :: (Monad m, Num b, Ord b) => BinaryTree a -> m b
getBalancedSize Empty = return 0
getBalancedSize (Node _ l r) = do
    sizeL <- getBalancedSize l
    sizeR <- getBalancedSize r
    if abs (sizeL - sizeR) <= 1
        then return $ sizeL + sizeR + 1
        else fail "tree is not balanced"

isBalanced :: BinaryTree a -> Bool
isBalanced = isJust . getBalancedSize

Теперь предположим, что у вас есть

fold :: (a -> b -> b -> b) -> b -> Tree a -> b
fold _ b Empty = b
fold f b (Node a l r) = f a (fold f b l) (fold f b r)

Существует очевидный способ реорганизовать getBalancedSize в один вызов fold.

getBalancedSize = fold f (return 0) where
    f _ l r = do
        sizeL <- getBalancedSize l
        sizeR <- getBalancedSize r
        if abs (sizeL - sizeR) <= 1
            then return $ sizeL + sizeR + 1
            else fail "tree is not balanced"

Но вам нужна некоторая рекурсивная функция для обхода рекурсивной древовидной структуры.

Answer 2

Вы можете использовать гарантированный тип Красно-Черное дерево .Нет необходимости проверять, сбалансирован ли он, потому что типы гарантируют это.

isBalanced = const True

Answer 3

Это зависит от того, как ваше двоичное дерево представлено в Haskell. Если это рекурсивная структура данных, рекурсия - ваше единственное оружие ...

Answer 4

Эффективное определение того, сбалансировано ли дерево, не обращая внимания на его размер , заключается в том, что если вы знаете, что правая ветвь на несколько уровней глубже левой ветви не имеет значения, насколько он глубже. 2 уровня глубже? 3? 100? Нам все равно, и это может быть признано неэффективным, чтобы выяснить только, чтобы отбросить результат.

isBalanced :: BinaryTree a -> Bool
isBalanced = and . treeToBalanceSize

treeToBalanceSize :: BinaryTree a -> BalanceSize
treeToBalanceSize Empty      = []
treeToBalanceSize (Node l r) = True : mergeBalanceSizes (treeToBalanceSize l) (treeToBalanceSize r)

mergeBalanceSizes :: BalanceSize -> BalanceSize -> BalanceSize
mergeBalanceSizes []       []       = []
mergeBalanceSizes [x]      []       = [x]
mergeBalanceSizes []       [y]      = [y]
mergeBalanceSizes (x : xs) (y : ys) = (x && y) : mergeBalanceSizes xs ys
mergeBalanceSizes _        _        = [False]

type BalanceSize = [Bool]

Удовлетвори себя, что

1. Если tree сбалансирован и имеет размер size, то treeToBalanceSize tree = replicate size True.
2. Если tree неуравновешен, то treeToBalanceSize tree заканчивается False.
3. Оценка mergeBalanceSizes [True] list не приводит к оценке list за пределами третьего элемента.

Answer 5

Вы можете определить новое двоичное дерево, которое хранит его глубину. Глубина обновляется при вставке и удалении, и вы можете определить ее баланс, посмотрев на сохраненное значение глубины.

Это лучшее решение для рекурсивного вычисления в зависимости от того, как часто вы обновляете дерево. Все равно чище.