從二叉搜索樹中刪除節點，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)