Deletion by merging in binary search tree
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: Deletion by merging in binary search tree

Hybrid View

  1. #1
    Join Date
    Jul 2009
    Location
    Poland
    Posts
    28

    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);
    ?

  2. #2
    Join Date
    Jul 2013
    Posts
    305

    Re: Deletion by merging in binary search tree

    Quote Originally Posted by Quentin026 View Post
    I don't get it, why is it necessary to have 4 if-clauses?
    Well, it certainly looks suspicious. Still what you suggest is not equivalent to the original code.

    In the original code if node is neither root nor prev->left then deleteByMerging(prev->right) will be called, whereas in your suggestion deleteByMerging(node) would be called.

    It may be significant, I cannot say.
    Last edited by razzle; July 23rd, 2013 at 02:27 AM.

  3. #3
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,591

    Re: Deletion by merging in binary search tree

    I didn't look at the original code, but I guess the parameter passed to deleteByMerging() is a non-const reference. In this case, even if prev->left == node, it does matter which of the two is passed: It determines which object gets modified by the function call.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center