如何检查二叉搜索树是否有效？

Question

如何使用BST的定义和BST的广义fold版本来检查BST是否有效？

data(Ord a, Show a, Read  a) => BST a = Void | Node {
    val :: a,
    left, right :: BST a
} deriving (Eq,  Ord,  Read, Show)


fold :: (Read a, Show a, Ord a) => (a -> b -> b ->  b) -> b -> BST a -> b
fold _ z Void         = z
fold f z (Node x l r) = f x (fold f z l) (fold f z r)

这个想法是检查节点值是否大于左子树中所有值，并小于其右子树中所有值。这必须对树中的所有节点都成立。函数bstList只需输出BST中（有序）值的列表。

当然，像这样的东西是行不通的：

--isBST :: (Read a, Show a, Ord a) => BST a -> Bool
isBST t = fold (\x l r -> all (<x) (bstList l) && all (>x) (bstList r)) (True) t

举个例子，将fold函数应用于节点19会得到all (<19) (bstList True) && all (>19) (bstList True)。

- gremo

Answer 1

请不要在data类型上放置typeclass的约束。

当且仅当二叉搜索树BST的中序遍历单调递增时，它才是有效的。

flatten tree = fold (\a l r -> l . (a:) . r) id tree []

ordered list@(_:rest) = and $ zipWith (<) list rest
ordered _ = True

isBST = ordered . flatten

- ephemient

Answer 2

您的问题似乎是因为您的函数仅在检查左右子树时返回布尔值而导致信息丢失。因此，将其更改为还返回子树的最小和最大值。（这可能更有效率，因为您不再需要使用bslist来检查所有元素）

当然，在完成后要创建一个包装函数来忽略这些“辅助”值。

- hugomg

---

当将fold应用于'Void'时，我该如何处理？我的意思是，最小值和最大值... - gremo

初始值 z 也必须更改为非布尔值。使其返回 (True, (+inf, -inf)) 或类似的内容。 无论如何，将树转换为列表的其他解决方案似乎更符合您实际需要的内容。 - hugomg

Answer 3

一种很好的编码方式是利用Data.Foldable提供的遍历功能。

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
import Data.Foldable
import Data.Monoid

我们可以使用扩展自动导出它的实例，但是我们需要重新排列Node构造函数的字段，以提供我们一个按顺序遍历。

另外，我们应该消除数据类型本身的约束。它们实际上没有任何好处，在Haskell 2011中已经从语言中删除。（当您想要使用这样的约束时，应将它们放在类的实例上，而不是放在数据类型上。）

data BST a 
  = Void
  | Node
    { left :: BST a
    , val :: a
    , right :: BST a 
    } deriving (Eq, Ord, Read, Show, Foldable)

首先，我们定义什么是严格排序的列表。

sorted :: Ord a => [a] -> Bool
sorted [] = True
sorted [x] = True
sorted (x:xs) = x < head xs && sorted xs 
-- head is safe because of the preceeding match.

然后我们可以使用由提供的方法和上述辅助程序。

isBST :: Ord a => BST a -> Bool
isBST = sorted . toList

我们也可以更直接地实现这一点，就像你所要求的那样。由于我们移除了数据类型上的不必要限制，因此我们可以简化您的折叠定义。

cata :: (b -> a -> b -> b) -> b -> BST a -> b
cata _ z Void         = z
cata f z (Node l x r) = f (cata f z l) x (cata f z r)

现在我们需要一种数据类型来模拟我们的catamorphism的结果，即我们要么没有节点（Z），要么有一系列严格递增的节点（T），或者失败了（X）。

data T a = Z | T a a | X deriving Eq

然后我们可以直接实现isBST

isBST' :: Ord a => BST a -> Bool
isBST' b = cata phi Z b /= X where
  phi X _ _ = X
  phi _ _ X = X
  phi Z a Z = T a a
  phi Z a (T b c) = if a < b then T a c else X
  phi (T a b) c Z = if b < c then T a c else X
  phi (T a b) c (T d e) = if b < c && c < d then T a e else X

这有点繁琐，也许最好把我们组合中间状态的方式分解一下：

cons :: Ord a => a -> T a -> T a
cons _ X = X
cons a Z = T a a
cons a (T b c) = if a < b then T a c else X

instance Ord a => Monoid (T a) where
  mempty = Z
  Z `mappend` a = a
  a `mappend` Z = a
  X `mappend` _ = X
  _ `mappend` X = X
  T a b `mappend` T c d = if b < c then T a d else X

isBST'' :: Ord a => BST a -> Bool
isBST'' b = cata phi Z b /= X where
  phi l a r = l `mappend` cons a r

个人而言，我可能只会使用可折叠实例。

- Edward Kmett

Answer 4

如果您不坚持使用折叠，可以这样做：

ord Void = True
ord (Node v l r) = every (< v) l && every (> v) r && ord l && ord r where
    every p Void = True
    every p (Node v l r) = p v && every p l && every p r

- Daniel