5

I'm making a Haskell function to delete a node from a Binary Search Tree. I know the rules regarding the action needed to be taken depending on the number children the targeted parent has.

no children - delete, 1 child - replace with the child, 2 children - find the min in the right sub tree and replace the node with the value, - then, recursively delete the minimum value from the right sub-tree 

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 isn't working correctly either. It just prints Strings Diagonally down to the right.

Improve this question
7
  • What code have you so far? Where are your particular problems? That lot of BST questions smells much like homework, so I hesitate to answer. (Not that we don't answer homework questions at all, but they should be answered differently to help learning.) Commented Mar 8, 2012 at 23:06
  • I just don't really know where to begin. Commented Mar 8, 2012 at 23:16
  • Start with the eaiest case: deleteNode x Empty = ... What would go there in place of the ..., i.e. what would be the result when deleting anything from an empty tree? Commented Mar 8, 2012 at 23:38
  • wouldn't you want to delete the previous node if the one you're at now is empty? Commented Mar 8, 2012 at 23:45
  • Nope. If you get to the empty node that means you never found the one you want to delete. Imagine you had the tree [1, 0, 2] And you said "delete 3 tree". You'd get to "Empty" on the right side of 2, but does that mean you should delete the 2? Commented Mar 8, 2012 at 23:57

3 Answers 3

Reset to default
10

In these situations, it's best not to think about deleting a node from the tree; it's better to think of how to transform the tree you have into one without the node you want gone.

Let's do some case analysis:

If the tree is empty, then the result is empty, regardless of the key:

delete _ Empty = Empty

If the tree is non-empty, we have to see if the key matches the node. If it does not match, then we need to transform either the left or right subtree based upon whether the key is greater-than or less-than the 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 it does match (which it must, since all of the no-match cases have been dealt with), then we have to figure out how to create a new tree without the root node. From your description, if the node has no children, just delete it:

delete _ (MakeNode Empty _ Empty) = Empty

If the node has one child, use that:

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 the new root's 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
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

thanks for the post man. you guys are really helpful on here, I appreciate it
@pat what would happen if i observe this tree and want to delete 6 from this such as : 2 / \ 1 6 / \ 4 7 \ /\ 5 3 8 it will find minimum from the rightsub tree and assign it to the targeted node place whereas it will not work in bellow mentioned case what if i want to delete the 6 ? it will return 3 as min from right subtree and if a place it at the targeted node place of 6 then what would happen with 4 at that level? bcz then BST property of holding smaller elements at left and greater elements on right will stand valid?
Assuming the BST property holds in the initial tree, the minimum node in the right subtree must be greater than all nodes in the left subtree and less than all other nodes in the right subtree. Therefore, a tree with that node as the root with the original left subtree as its left subtree, and the original right subtree with that node removed as its right subtree will still have the BST property.
1

You can't! Everything is immutable!

What you can do is make a new tree that's exactly the same as the old one, except with one node removed. (Don't worry, your compiler won't need to duplicate much memory. Remember, everything is immutable. That means that the implementation can safely re-use the common parts!)

As such, your deleteNode function won't be of type String -> BST, it will be of type String -> BST -> BST. The String is the label you want removed, the first BST is the input tree, the second BST is the output tree.

As @Ingo mentioned, you can implement deletion recursively by implementing the 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 do some general munging beyond deletion (insertion, changes, etc.) in a traversable data structure (trees, lists, etc) I suggest you read up on zippers. They'll help you immensely.

Once you have a zipper for a binary tree, you can use zipper functions to delete nodes in the tree. If you'd like help implementing a zipper for your binary search tree data structure, let me know and I'll expand this. Right now it's probably overkill.

Be warned, a zipper won't re-balance your binary search tree for you. If you want to remove a node from your binary search tree and keep it balanced, that's a whole new can of worms.

There are a number of common balancing algorithms you could use, depending upon your taste. I suggest getting it working in an unbalanced fashion first, and then asking separate questions if you have trouble balancing it.

And, of course, if you want an efficient, out-of-the-box, already-implemented, balancing binary search tree in haskell -- just import Data.Map!

Improve this answer

7 Comments

thanks, i just used my own functions i made to reduce a tree into a list, delete the item, then use another function to put it back into a tree. My function to convert a list to a tree isnt working correctly though. Do you have any idea with that?
Depends. What's going wrong with it? You lose a lot of the benefits of a binary tree by converting to/from a list, your algorithm will be much faster (O(log n) instead of O(n)) if you use the tree structure to your advantage. That is, after all, the whole point of tree structure.
yeah, understand that, but it was the fastest thing i could think of lol. It's supposed to look at the list, put the first element at the top of the tree, the second element branches off according to its comparison to the first element and so on. I think that my algorithm is off
Probably. Either post what you have in the comments or post another question about it and I'll try to help out. That said, your easiest route is probably to implement deleteNode using the template in the answer above :-)
Your tree-to-list, list-delete, list-to-tree approach will most likely result in a horribly imbalanced tree (unless you are really careful).
|
0

Here is a deletion function implemented in Haskell using Mutual Recursion

The type of the tree is:

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) = 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)
Improve this answer

2 Comments

Is it necessary to bring the Key to delete' function? Since already found the key.
Has treeMaximum been defined?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.