从二叉搜索树中删除节点,haskell

Question

我正在使用Haskell函数从二进制搜索树中删除节点.我知道有关采取行动的规则取决于目标父母的子女数量.

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

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也无法正常工作.它只是向右对角打印字符串.

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

Answer 2

你不能！一切都是一成不变的！

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

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

正如@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。他们会给你很大的帮助。

一旦有了二叉树的拉链，就可以使用拉链函数来删除树中的节点。如果您需要帮助为您的二叉搜索树数据结构实现拉链，请告诉我，我将扩展它。现在看来可能有些过分了。

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

您可以根据您的喜好使用多种常见的平衡算法。我建议首先让它以不平衡的方式工作，然后如果你在平衡它时遇到困难，再提出单独的问题。

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