在Haskell中删除带有特定Int的树叶子

Question

我有定义的类型:数据树=节点树树|叶子Int | NIL。我想创建一个方法delete:: Tree -> Int -> Tree，它删除了第二个参数中给定的特定Int的所有叶子。

Answer 1

如果您的树没有任何特定的结构，您可以

delete NIL _ = NIL
delete (Leaf i) int | i == int = NIL
                    | otherwise = Leaf i
delete (Node left right) int = Node (delete left int) (delete right int)

为什么?

delete NIL _ = NIL因为我们要处理所有的情况，甚至是末端的空树。_代表我们不关心的任何值

delete (Leaf i) int | i == int = NIL
                    | otherwise = Leaf i

，因为我们需要先检查| i== int，看看是否要删除节点。如果我们这样做，我们用空的3,NIL代替它。否则，我们不管它。

delete (Node left right) int = Node (delete left int) (delete right int)，因为如果我们在一个节点上，我们需要从left和right子树中删除int。

你最后不会得到一大堆的NIL吗?

是的，我想那是可能发生的。你可以用

prune (Node  NIL      NIL    ) = NIL
prune (Node (Leaf i)  NIL    ) = Leaf i 
prune (Node  NIL     (Leaf i)) = Leaf i 
prune (Node (Leaf i) (Leaf j)) = Node (Leaf i) (Leaf j)
prune (Node  left     right  ) = prune (Node (prune left) (prune right))
prune t = t

前三行去掉左边、右边或两边的NIL，第四行只留下两个叶子。

只有当该节点的左子树或右子树之一本身是节点时才调用第五行。为什么是prune三次?也许当你把prune left和prune right变成一个或多个NIL。

prune t = t处理NIL和Leaf i在一个简洁的模式匹配。

Answer 2

我建议对AndrewC的回答做一些改进。虽然他的解决方案是绝对正确的，但它有一些潜在的性能问题。

问题是:delete和prune函数在每次调用时都会创建整个树的新副本。无论元素是否被删除，都会发生这种情况。

最坏的情况是删除一个不存在的元素。

假设我们有一个非常大的树，里面有1M个整数。由于整数只存储在叶子中，所以整个树至少包含2M-1个节点。(如果树还没有被修剪，因此包含NIL节点，甚至更多)。

当我们试图从这样一个巨大的树中删除一个不存在的元素时，我们的delete函数除了复制所有2M的节点外什么也不做。(prune将再次复制它们!)

删除一个已经存在的元素只是稍微好一点。在这种情况下，delete删除一个叶子，更新它的父节点，并复制树的其余部分。prune可能会删除更多的节点，但会复制其余的节点。

为什么会这样?

有两个地方发生了复制。

这一行创建了一个与参数完全相同的新树:

delete (Leaf i) int | ...
                    | otherwise = Leaf i

同样，即使元素在左右分支中都不存在，这一行也会创建一个新的树:

delete (Node left right) int = Node (delete left int) (delete right int)

有可能避免不必要的重复吗?

当然可以。如果不修改实参，只需要返回它。

这是我的版本:

delete t i = fst $ delete' t i
  where delete' NIL _ = (NIL, True)
        delete' t@(Leaf i) int | i == int = (NIL, False)
                               | otherwise = (t, True)
        delete' t@(Node left right) int =
            let (left', unchangedLeft) = delete' left int
                (right', unchangedRight) = delete' right int
            in
              if unchangedLeft && unchangedRight
                then (t, True)
                else (Node left' right', False)

如您所见，我使用了一个辅助函数delete'，它返回一对(Tree, Bool)，其中如果树没有改变，第二个元素为True，否则为False。

该函数构建一个新树，该树与原树共享大部分节点。它只改变从根到被删除元素的路径上的节点。

prune呢?

以上版本不删除NIL元素。正如AndrewC所指出的，在执行多次删除之后，我们可能会得到一个有很多NIL的树。为了解决这个问题，我们可以以类似的方式修改prune，或者我们可以仅仅将其集成到delete中:

delete t i = fst $ delete'' t i
  where delete'' NIL _ = (NIL, True)
        delete'' t@(Leaf i) int | i == int = (NIL, False)
                                | otherwise = (t, True)
        delete'' t@(Node left right) int =
            let (left', unchangedLeft) = delete'' left int
                (right', unchangedRight) = delete'' right int
            in
              if unchangedLeft && unchangedRight
                then (t, True)
                else (newNode left' right', False)
        newNode NIL r = r
        newNode l NIL = l
        newNode l r = Node l r