如何从多叶二叉树(Haskell)中删除元素 [英] How to delete an element from a Leafy Binary Tree (Haskell)

问题描述

因此，此树不是二进制搜索树.它没有特定的顺序，只是以这种顺序可以快速访问特定索引(第n个元素)，而不是元素是否存在.

So, this tree is NOT a Binary Search Tree. It is in no particular order, and is just in this order for quick access to specific indices (nth element), rather than whether an element exists or not.

树的形式如下:

data Tree a = Leaf a | Node Int (Tree a) (Tree a) deriving Show

对于这棵特定的树，Node构造函数中的"Int"是该节点下的元素数(或叶数).

For this specific tree, the "Int" from the Node constructor is the number of elements underneath that node (or number of leaves).

使用这种结构，我复制了网上找到的一个演讲中可用的Tree函数的某些部分(在尝试理解时稍作修改):

Using this structure, I copied parts of the Tree functions available in a lecture I found online (that I slightly modified when trying to understand):

buildTree :: [a] -> Tree a
buildTree = growLevel . map Leaf
    where
    growLevel [node]   = node
    growLevel l        = growLevel $ inner l

    inner []           = []
    inner (e1:e2:rest) = e1 <> e2 : inner rest
    inner xs = xs

    join l@(Leaf _)       r@(Leaf _)       = Node 2 l r
    join l@(Node ct _ _)  r@(Leaf _)       = Node (ct+1) l r
    join l@(Leaf _)       r@(Node ct _ _)  = Node (ct+1) l r
    join l@(Node ctl _ _) r@(Node ctr _ _) = Node (ctl+ctr) l r

我能够创建一些基本功能来移动一棵树.我做了一个找到第n个元素并返回它的元素.我还制作了Path数据类型，并实现了一个将路径(左右方向)返回到特定索引的函数，以及一个可以通过路径并返回该Node/Leaf的函数.

And I was able to create some basic functions for moving through a tree. I made one that finds the nth element and returns it. I also made a Path datatype and implemented a function to return the path (in left and rights) to a specific index, and one function that can travel through a path and return that Node/Leaf.

现在，我想做的是删除功能.这里的问题在于树是多叶的"，或者至少这是给我造成麻烦的原因.

Now, what I would like to make is a delete function. The problem here is with the fact that the tree is "leafy", or at least that is what is causing me difficulties.

如果我最终在删除路径中使用了Leaf，则没有"Null"或等效项替换它.另外，如果我尝试停在最后一条路径(如[L])，并检查是否为Node，那么如果是叶子，则用相反的一面替换整个节点，等等，我遇到了更改问题整个树以反映该变化，而不仅仅是返回删除的结尾，并更改树中的所有数字以反映叶子的变化.

If I end up with a Leaf at the deletion path, there is no "Null" or equivalent item to replace it with. Additionally, if I try to stop at the last path (like [L]), and check if that's a Node or not, then if it's a leaf replace the whole node with the opposite side etc., I run into the problem of changing the whole tree to reflect that change, not just return the end of the deletion, and change all the numbers from the tree to reflect the change in leaves.

我希望在删除项目时保留顺序，例如，如果要使用列表作为简单示例:

I would like order to be preserved when deleting an item, like if you were to use a list as a simpler example:

del 4 [1, 2, 3, 4, 5, 6, 7] = [1, 2, 3, 4, 6, 7]

如果有一种更简单的方法来构造树(仍然可以包含重复的元素并保留顺序)，那是什么?

If there is a simpler way to structure the Tree (that still can contain duplicate elements and preserve order) what is it?

是否可以使用此方法删除元素?

Is there some way to delete an element using this method?

推荐答案

如果我...用相反的一面替换整个节点...我遇到了更改整个树以反映该更改的问题，而不仅仅是返回删除的末尾，并更改反映叶子变化的树.

If I ... replace the whole node with the opposite side ... I run into the problem of changing the whole tree to reflect that change, not just return the end of the deletion, and change all the numbers from the tree to reflect the change in leaves.

不是整个树，而是从删除的节点到根的路径.那不是您想要的吗?

Well, not the whole tree - just the path from the deleted node back to the root. And isn't that exactly what you want?

我想第一步是定义删除"的含义.删除后未删除节点的索引应该保持不变，还是应该将删除节点之后的节点的索引减少一?也就是说，给定:

I guess the first step would be, define what you mean by "delete". Should the indexes of undeleted nodes remain the same after deletion, or should nodes after the deleted node have their indexes reduced by one? That is, given:

tree :: [a] -> Tree a
-- get and del both 0-indexed, as in your example
get :: Int -> Tree a -> Maybe a
del :: Int -> Tree a -> Tree a

然后当然

get 5 $ tree [1..7]

应产生Just 6.但是

get 5 . del 4 $ tree [1..7]

?我想，如果您希望它仍然产生Just 6(树中有一个空白"点，以前是5)，那是一个相当棘手的概念.如果定义Leaf (Maybe a)而不是Leaf a，则可以放空任何内容以留出空间，但这只能解决问题:插入仍会在索引周围移位.

? If you want this to still yield Just 6 (there is a "blank" spot in your tree where 5 used to be), that is a rather tricky concept, I think. You can put Nothings in to make space, if you define Leaf (Maybe a) instead of Leaf a, but this only papers over the problem: inserts will still shift indices around.

我认为用Just 7代替tree [1,2,3,4,6,7]更容易.如果这是您的目标，那么您仅需对从已删除节点到根的路径上的所有节点重新编号:就不会出现这样的事实:它们现在都拥有一个更少的叶子后代.但是树中的其他节点可以保持不变.

I think it is much simpler for this to yield Just 7 instead, making del 4 $ tree [1..7] the same as tree [1,2,3,4,6,7]. If this is your goal, then you simply must renumber all the nodes on the path from the deleted node back to the root: there is no getting around the fact that they all have one fewer leaf descendant now. But the other nodes in the tree can remain untouched.

作为参考，del的一种可能的实现:

For reference, one possible implementation of del:

count :: Tree a -> Int
count (Leaf _) = 1
count (Node s _ _) = s

del :: Int -> Tree a -> Maybe (Tree a)
del n t | n < 0 || n >= size || size <= 1 = Nothing
        | otherwise = go n t
  where size = count t
        go n (Leaf _) = Nothing
        go n (Node s l r) | n < size = reparent flip l r
                          | otherwise = reparent id r l
          where reparent k c o = pure . maybe o (k (Node (s - 1)) o) $ go n c
                size = count l

这篇关于如何从多叶二叉树(Haskell)中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！