3

我有定义的类型：数据树 = 节点树树 | 叶诠释 | 无。我想创建一个方法delete :: Tree -> Int -> Tree使用第二个参数中给出的特定 Int 删除所有 Leaf。

4

2 回答 2

4

如果你的树没有任何特定的结构，你可以这样做

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是否要删除节点。如果我们这样做，我们将其替换为空的三个，NIL。否则，我们就不管它。

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

你不会最终得到一大堆NILs吗？

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

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左边、右边或两边的 a，第四行留下两片叶子。

仅当该节点的左子树或右子树之一本身就是节点时，才调用第五行。为什么prune是三遍？也许当你prune left和prune right他们中的一个或多个结束时NIL。

prune t = t处理两者并NIL在Leaf i一个整洁的模式匹配中。

于 2013-06-01T19:34:46.010 回答
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 所指出的，在执行多次删除后，我们可能会得到一棵包含很多NILs 的树。为了解决这个问题，我们可以以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
于 2013-06-03T22:51:05.147 回答