如何从多叶二叉树中删除元素 (Haskell)

Question

所以，这棵树不是二叉搜索树。它没有特定的顺序，只是为了快速访问特定索引（第 n 个元素）而不是元素是否存在。

树的形式是这样的：

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

对于这个特定的树，Node 构造函数中的 "Int" 是该节点下的元素数（或叶子数）。

使用这个结构，我复制了我在网上找到的讲座中可用的部分 Tree 函数（为了理解我稍微修改了一下）：

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 个元素并 returns 的。我还制作了一个 Path 数据类型并实现了一个函数 return 到特定索引的路径（左侧和右侧），以及一个可以通过路径和 return Node/Leaf 的函数.

现在，我想做的是一个删除功能。这里的问题是树是 "leafy"，或者至少这是给我造成困难的原因。

如果我最终在删除路径中看到一片叶子，则没有 "Null" 或等效项可以替换它。此外，如果我尝试在最后一条路径（如 [L]）处停下来，并检查它是否是一个节点，如果它是一个叶子，则将整个节点替换为另一侧等，我运行进入改变整个树以反映该变化的问题，而不仅仅是 return 删除的结尾，并改变树中的所有数字以反映叶子的变化。

我希望在删除项目时保留顺序，就像您要使用列表作为更简单的示例一样：

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

如果有更简单的方法来构造树（仍然可以包含重复元素并保持顺序），那是什么？

有什么方法可以使用这种方法删除元素吗？

Answer 1

If I end up with a Leaf at the deletion path, there is no "Null" or equivalent item to replace it with.

好吧，做一个:)。这就是 Maybe 的用途：当您从 Tree 中删除一个元素时，您不能期望得到 Tree 回来，因为 Tree 被定义为非空的。您需要通过包装在 Maybe 中来明确添加空的可能性。删除也可能因越界错误而失败，我用 Either Int 表示并合并到逻辑中。

delete :: Int -> Tree a -> Either Int (Maybe (Tree a))
delete i t | i >= max = Left (i - max) where max = count t
delete _ (Leaf _) = Right Nothing
delete i (Node n l r) = case delete i l of
  Left i' -> Just <$> maybe l (Node (n - 1) l) <$> delete i' r
  Right l' -> Right $ Just $ maybe r (\x -> Node (n - 1) x r) l'

其中 count 是我在评论中推荐的：

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

Answer 2

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.

好吧，不是整棵树 - 只是从已删除节点回到根的路径。这不正是你想要的吗？

我想第一步是，定义 "delete" 的意思。删除后未删除节点的索引应该保持不变，还是删除节点后的节点索引减一？即，给定：

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（在你的树中有一个 "blank" 点，而 5 曾经是），我认为这是一个相当棘手的概念。如果定义 Leaf (Maybe a) 而不是 Leaf a，则可以将 Nothings 放入 space，但这只是解决了问题：插入仍会移动索引。

我认为生成 Just 7 更简单，使 del 4 $ tree [1..7] 与 tree [1,2,3,4,6,7] 相同。如果这是您的目标，那么您只需对从已删除节点到根的路径上的所有节点重新编号：无法回避这样一个事实，即它们现在都少了一个叶子后代。但是树中的其他节点可以保持不变。

供参考，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)

How to delete an element from a Leafy Binary Tree (Haskell)

recursion

binary-tree

haskell