从二叉搜索树中删除节点，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工作不正常。它只是将字符串斜向下打印到右侧。

Answer 1

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

你可以做的是使一个新树是正是一样的旧的，除了除去了一个节点。 （别担心，你的编译器将不再需要重复多少内存。请记住，一切是不变。这意味着实现可以安全地重新使用公用部分！）

因此，您deleteNode功能将不是类型String -> BST，它将是String -> BST -> BST类型。 String是要删除的标签，第一个BST是输入树，第二个BST是输出树。

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 

如果你想在一笔画数据结构做超越缺失（插入，修改等）一些通用的改写（munging）（：

正如@Ingo提到的，你可以通过递归来实现函数执行删除树，名单等）我建议你阅读zippers。他们会非常帮助你。

一旦你有一个二叉树的拉链，你可以使用拉链函数来删除树中的节点。如果你想为你的二叉搜索树数据结构实现一个拉链的帮助，请告诉我，我将扩展它。现在它可能是矫枉过正。

被警告，拉链不会为您的二叉搜索树重新平衡。如果你想从你的二叉搜索树和中删除一个节点来保持平衡，那么这是一个全新的蠕虫罐。

有一个numbercommon您可以使用的平衡算法，取决于你的口味。我建议先让它以不平衡的方式工作，然后再问一些单独的问题，如果您在平衡时遇到问题。

而且，当然，如果您想在haskell中使用一个高效的开箱即用的平衡二叉搜索树，只需导入Data.Map即可！

Answer 2

在这些情况下，最好不要考虑从树中删除节点;最好考虑如何将没有节点的树变成一棵树。

让我们做一些案例分析：

如果树是空的，那么结果是空的，而不管键：

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 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) = delete k l 
    | (k > a) = 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)