在haskell中的二叉搜索树中删除函数

如何实现删除二叉搜索树中的元素的函数？这是我的树：在haskell中的二叉搜索树中删除函数

data Tree a = Leaf 
      | Node a (Tree a) (Tree a)

我知道，如果我的树是叶

delete :: (Ord a) => a -> Tree a -> Tree a 
delete _ Leaf = Leaf

，并在情况下，左和右是不是空的，我不得不删除权利的最低限度（或最大值从左），它成为根。但是，我该如何实现它？

来源

2012-02-22 Marco Sero

这个功课？ – 2012-02-22 12:10:07

@ MatveyB.Aksenov是啊 – 2012-02-22 14:59:25

然后请在下次标记它。这是常见的做法。 – 2012-02-22 15:47:11

您应该实现的功能

delMin :: Tree a -> (Tree a, a)

从树上删除最小元素和返回两个修改后的树和最小元素。然后删除算法变为：找到具有要删除项目的节点并致电

-- delete' n deletes the node n and returns a modified BST 
delete' :: Ord a => Tree a -> Tree a 
delete' (Node _ l Leaf) = l 
delete' (Node _ Leaf r) = r 
delete' (Node _ l r)  = let (r', min) = delMin r in 
           Node min l r'

来源

2012-02-22 11:18:39

如果'delMin'是顶级的，那么使用'delMin :: Tree a - > Maybe（Tree a，a）'来处理'Leaf'可能是个好主意。 – 2012-02-22 14:23:39

@DanielFischer：'delMin'，至少在当前不应该从BST模块中导出。它可能隐藏在“where”子句中。 – 2012-02-22 14:36:59

虽然它可能被认为通常很有用，但是如果它暴露出来，我宁愿安全地处理'Leaf'。如果它只是一个地方，那当然是不必要的混乱。 – 2012-02-22 14:45:27

在haskell中的二叉搜索树中删除函数

回答

相关问题