如何检查BST是否有效？-Java 学习之路

How can I check if a BST is a valid one, given its definition and using a generalized version of fold for 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)

idea 用于检查节点值是否大于left-subtree中的所有值，并且小于其右子树中的所有值 . 对于树中的所有节点，该值必须为 True . 函数 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

因为，例如，将折叠函数应用于节点 19 最终 all (<19) (bstList True) && all (>19) (bstList True) .

a BST

4 回答

4

你的问题似乎是你丢失了信息，因为你的函数在检查左右子树时只返回一个布尔值 . 所以 change it to also return the minimum and maximum values of the subtrees. （这可能也更有效，因为你不需要再使用 bslist 来检查所有元素）

当然，在完成后，使包装函数忽略这些“辅助”值 .

回复于 2024-04-20T16:24:56+08:00

（请不要在 data 类型上添加类型类约束 . ）

如果有序遍历单调递增，则BST有效 .

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

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

isBST = ordered . flatten

回复于 2024-04-20T16:24:56+08:00

对此进行编码的一种好方法是依靠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.

然后我们可以使用 Data.Foldable 提供的 toList 方法和上面的帮助器 .

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

就个人而言，我可能只是使用Foldable实例 .

回复于 2024-04-20T16:24:56+08:00

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

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

回复于 2024-04-20T16:24:56+08:00

如何检查BST是否有效？

4 回答

相关问题