haskell - 在 BST Haskell 中删除最小值

Question

如何删除 BST 中的最小值？我似乎找不到保留这棵树的方法

data BST = EmptyT
         | Node Float BST BST
           deriving (Eq, Show, Read)

deleteMin :: BST -> Maybe BST
deleteMin EmptyT  = Nothing
deleteMin (Node x left right)
    |left == EmptyT = ? 
    |otherwise = ?

我需要 getter 和 setter 吗？

Answer 1

Haskell 没有 OOP 意义上的“getters 和 setter”，尽管你可以提出类似的概念。如果你想删除二进制文件中的一个值tree，你必须构建一棵缺少值的新树。你就是这样“保留这棵树。”

假设您使用的是标准 BST，那么树中最左边的节点将包含最小元素。所以，通过向左遍历你的树，您最终应该会遇到类似 Node x EmptyT r 的情况。任何其他节点，您只需在左侧分支上递归调用 deleteMin。

这给出了一个看起来像的函数

deleteMin :: BST -> Maybe BST
deleteMin EmptyT                = Nothing
deleteMin (Node x EmptyT right) = Just right
deleteMin (Node x left right)   =
    case deleteMin left of
         Nothing -> Nothing
         Just nl -> Just $ Node x nl right

您必须检查每次调用 deleteMin 的结果以检查无。我不认为你真的需要返回一个 Maybe BST，除非你确实需要指明没有要删除的元素。它使更多感觉(至少对我来说)如果没有什么可以返回一棵空树删除。

我想大多数人也会考虑使用模式匹配，而不是使用具有相等性检查的守卫。