-
June 24th, 2013, 09:36 AM
#1
Deletion by merging in binary search tree
Hi there,
I'm reading about a technique known as deletion by merging in context of binary search trees. Here's the PDF:
http://www.cs.mun.ca/av/old/teaching...rees2_quad.pdf
and the code for 2 related functions: deleteByMerging and findAndDeleteByMerging, is on page 4-5. The book, from which the PDF comes from, says that:
Using search() in function findAndDeleteByMerging() is a treacherous simplification. search() returns a pointer to the node containing el. In findAndDeleteByMerging(), it is important to have this pointer stored specifically in one of the pointers of the node's parent. In other words, a caller to search() is satisfied if it can access the node from any direction, whereas findAndDeleteByMerging() wants to access it from either its parent's left or right pointer data member. Otherwise, access to the entire subtree having this node as its root would be lost.
This quote pertains probably to this snippet on page 5:
Code:
if(node != 0 && node->el == el)
if(node == root)
deleteByMerging(root);
else if(prev->left == node)
deleteByMerging(prev->left);
else
deleteByMerging(prev->right);
I don't get it, why is it necessary to have 4 if-clauses? Wouldn't one, the outer, be sufficient? I mean, if prev->left == node or if prev->right == node then one way or another, we pass node in the call to deleteByMerging.
Wouldn't it be much simpler to just write:
Code:
if(node != 0 && node->el == el)
deleteByMerging(node);
?
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|