删除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 = ?

我需要吸气剂和二传手吗？

Answer 1

Haskell在OOP意义上没有"getter and setter",尽管你可以提出类似的概念.如果要删除二叉树中的值,则必须构造一个缺少值的新树.这就是你"保持树"的方式.

假设您使用的是标准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进行检查 Nothing.我不认为你真的需要返回一个Maybe BST,除非你真的需要表明没有要删除的元素.如果没有什么可以删除的话,那么(至少对我来说)返回空树更有意义.

我认为大多数人也会考虑使用模式匹配,而不是使用带有相等性检查的警卫.