Remove node from binary search tree, haskell
I am making a Haskell function to remove a node from a binary search tree. I know the rules for the action to be taken based on the number of children of the target parent.
no children - remove, 1 child - replace child, 2 children - find the minus in the right subtree and replace the node value with the value, - then, recursively remove the minimum value from the right subtree
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
can't figure out why treeBuilder doesn't work either. It just prints lines diagonally down to the right.
source to share
In these situations, it is best not to think about removing a node from the tree; it's better to think about how to transform the tree you have without the node you want to delete.
Analyze some of the cases:
If the tree is empty, then the result is empty, regardless of the key:
delete _ Empty = Empty
If the tree is not empty, we should see if the key matches node. If that doesn't match, we need to transform the left or right subtree based on whether the key is greater or less than node:
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)
If that matches (which is necessary since all non-matching cases have been addressed), then we need to figure out how to create a new tree without a root node. From your description, if the node has no children, then just remove it:
delete _ (MakeNode Empty _ Empty) = Empty
If node has one child then use it:
delete _ (MakeNode l _ Empty) = l
delete _ (MakeNode Empty _ r) = r
Otherwise, find and delete the minimum key in the right subtree and use it as your new root key:
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
source to share
You can not! Everything is unchanged!
What you can do is create a new tree which is exactly the same as the old one, except for one node removed. (Don't worry, your compiler won't need to duplicate a lot of memory. Remember, everything is immutable. This means that an implementation can safely reuse common parts!)
So your deleteNode function will not have a type String -> BST
, it will have a type String -> BST -> BST
. String
is the label you want to remove, the first BST
is the input tree, the second BST
is the output tree.
As @Ingo mentioned, you can implement deletion recursively by implementing a function:
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
If you want to make some general changes without deleting (inserts, changes, etc.) in a traceable data structure (trees, lists, etc.), I suggest you read the zippers . They will help you a lot.
Once you have a binary tree zipper, you can use the zipper functions to remove nodes in the tree. If you need help creating a zip for a binary data tree data structure, please let me know and I'll expand it. Right now, this is probably overkill.
Be warned, lightning won't rebalance your binary search tree. If you want to remove a node from your binary search tree and balance it, it might be a new worm from worms.
There are a number of general balancing algorithms that you can use, depending on your taste. I suggest working with an unbalanced way first and then asking separate questions if you have balancing issues.
And of course, if you want to create an efficient, out-of-the-box, already implemented balancing binary search tree in haskell - just import Data.Map
!
source to share
Here is a delete function implemented in Haskell using mutual recursion
Tree type:
type Key = Int
data BST = Nil | Node Key BST BST deriving (Show, Eq)
and here is the delete function:
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)
source to share