从二叉搜索树中删除节点，Haskell。

Question

我正在编写一个Haskell函数，用于从二叉搜索树中删除节点。 我知道根据目标父节点的子节点数量需要执行的操作规则。

没有孩子 - 删除， 1个孩子 - 用孩子替换， 2个孩子 - 在右子树中找到最小值并替换节点的值， - 然后递归地从右子树中删除最小值。

data BST = MakeNode BST String BST
              |  Empty

deleteNode :: String -> BST



treeBuilder :: [String] -> BST
treeBuilder = foldr add Empty

add :: String -> BST -> BST
add new Empty = (MakeNode Empty new Empty)
add string tree@(MakeNode left value right)
    | string > value = MakeNode left value (add string right)
    | string < value = MakeNode (add string left) value right
    | otherwise = tree

我无法弄清楚为什么treeBuilder也不能正确工作。它只是将字符串斜向右下打印出来。

- user1204349

---

你目前的代码是什么？你有哪些特别的问题？那些二叉搜索树问题非常像作业，所以我犹豫着回答。（不是我们不回答作业题，而是应该用不同的方式回答以帮助学习。） - Daniel Fischer

我真的不知道从哪里开始。 - user1204349

如果当前节点为空，您是否想要删除前一个节点？ - user1204349

不行。如果你到达了空节点，那意味着你从未“找到”想要删除的节点。想象一下，你有一棵树[1, 0, 2]，然后你说“删除3树”。你会到达2的右侧的“空”节点，但这是否意味着你应该删除2？ - So8res

我明白你的意思。 - user1204349

Answer 1

在这些情况下，最好不要考虑从树中删除节点；更好的做法是思考如何将你拥有的树转换为一个没有所需删除节点的树。

让我们进行一些案例分析：

如果树为空，则结果为空，无论键是什么：

delete _ Empty = Empty

如果树非空，我们需要查看键是否与节点匹配。如果不匹配，则需要根据键是大于还是小于节点来转换左子树或右子树：

delete key (MakeNode l key' r) | key < key' = MakeNode (delete key l) key' r
delete key (MakeNode l key' r) | key > key' = MakeNode l key' (delete key r)

如果匹配成功 (这必须是如此，因为所有的不匹配情况都已经处理完毕)，那么我们就需要想办法创建一个没有根节点的新树。从您的描述中可以看出，如果该节点没有子节点，则只需将其删除:

delete _ (MakeNode Empty _ Empty) = Empty

如果节点只有一个子节点，就使用它：

delete _ (MakeNode l _ Empty) = l
delete _ (MakeNode Empty _ r) = r

否则，在右子树中找到并删除最小的键，将其用作新根节点的键：

delete _ (MakeNode l _ r) = MakeNode l key r' -- make a new root with min key and new r
  where key = minKey r    -- find the minimum key in the right subtree
        r' = delete key r -- new right subtree with min key removed

        -- a helper function to find the minimum key in a tree
        -- !! does not work on Empty tree !!
        minKey (MakeNode Empty key _) = key
        minKey (MakeNode l _ _) = minKey l

- pat

---

谢谢你的帖子，伙计。 你们在这里真的很有帮助，我很感激。 - user1204349

@pat 如果我观察这棵树并想要删除其中的6，会发生什么情况呢？如下所示： 2 /
1 6 /
4 7 \ /
5 3 8它将从右子树中找到最小值并将其分配给目标节点位置，但在下面的情况下不起作用。如果我想要删除6，会发生什么？它将从右子树返回3作为最小值，如果我将其放置在6的目标节点位置上，那么在该级别上的4会发生什么？因为BST属性保持较小元素在左侧和较大元素在右侧，这是否仍然有效？ - Sniper

假设初始树符合BST属性，则右子树中的最小节点必须大于左子树中的所有节点，并且小于右子树中的所有其他节点。因此，以该节点为根节点的树，其原始左子树作为其左子树，而将原始右子树中的该节点删除后作为其右子树，仍将具有BST属性。 - pat

Answer 2

不行！一切都是不可变的！

你可以做的是创建一个新的树，它与旧树完全相同，只是删除了一个节点。（别担心，你的编译器不需要复制太多内存。记住，一切都是不可变的。这意味着实现可以安全地重用公共部分！）

因此，你的deleteNode函数将不是类型为String -> BST，而是类型为String -> BST -> BST。第一个BST是输入树，第二个BST是输出树，String是你想要删除的标签。

正如@Ingo所提到的，你可以通过实现以下函数来递归地实现删除：

deleteNode :: String -> BST -> BST
deleteNode _ Empty = ...                          -- Handle the empty case
deleteNode x (BST left a right) | x == a    = ... -- Delete the node
                                | x < a     = ... -- Recurse on the lesser node
                                | otherwise = ... -- Recurse on the greater node

如果你想在可遍历的数据结构（树、列表等）中进行一些除删除之外的通用操作（插入、更改等），我建议你阅读一下zippers。它们会对你有很大帮助。

一旦你有了二叉树的zipper，你就可以使用zipper函数来删除树中的节点。如果你需要帮助为你的二叉搜索树数据结构实现zipper，请告诉我，我会扩展这个内容。现在可能有点过度设计。

请注意，zipper不会为你重新平衡二叉搜索树。如果你想从二叉搜索树中删除一个节点并保持其平衡，那就是一个全新的问题。

有许多number常见的平衡算法可供选择，具体取决于你的喜好。我建议先让它以不平衡的方式工作，然后如果你在平衡方面遇到问题，再提出单独的问题。

当然，如果你想要一个高效、开箱即用、已经实现的平衡二叉搜索树在Haskell中 - 只需导入Data.Map！

- So8res

---

取决于情况。出了什么问题？将二叉树转换为列表会失去许多优点，如果您利用树结构的优势，算法将更快（O(log n)而不是O(n)）。这毕竟是树结构的全部意义所在。 - So8res

是的，我明白，但这是我能想到的最快的方法，哈哈。 它应该查看列表，将第一个元素放在树的顶部，第二个元素根据与第一个元素的比较分支，依此类推。我认为我的算法有问题。 - user1204349

你的树转列表、列表删除、列表转树方法很可能会导致一棵非常不平衡的树（除非你非常小心）。 - pat

为什么会这样？为什么会不平衡？ - user1204349

如果您的插入函数没有重新平衡树，则将插入折叠在排序列表上将创建一个完全向左（或向右）平衡的树，其高度与列表的长度相同。 - danr

Answer 3

这是一个使用互递归在Haskell中实现的删除函数。

树的类型为：

type Key = Int
data BST = Nil | Node Key BST BST deriving (Show, Eq)

这里是删除函数：

delete :: Key -> BST -> BST
delete k Nil = Nil
delete k x@(Node a l r)
  | (k < a) = Node a (delete k l) r
  | (k > a) = Node a l (delete k r)
  | (k == a) = delete' k x

delete' :: Key -> BST -> BST
delete' k (Node a l r)
  | (l == Nil)  = r
  | (r == Nil)  = l
  | otherwise    = let (k,t) = maxAndDelete l
                    in Node k t r

-- This function finds the maximum and then deletes the node as well
maxAndDelete :: BST -> (Key,BST)
maxAndDelete t = let m = treeMaximum t
                  in (m,delete m t)

- Abhiroop Sarkar

---

需要将“Key”带到“delete”函数中吗？因为已经找到了这个键。 - Woden

treeMaximum已经定义了吗？ - Woden