4 Replies - 1207 Views - Last Post: 19 March 2012 - 12:01 PM Rate Topic: -----

#1 SilverMage  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 43
  • Joined: 11-October 10

How to delete the minimum element from a binary search tree

Posted 19 March 2012 - 11:23 AM

Hello,

I'm having trouble removing nodes from a binary search tree that I'm implementing. In the particular method below, I made it so that the node that I want to get rid of is overridden by its child. In this case, I'm trying to get rid of the minimum, so either there is one child or none. However, when I view all the elements of the tree after doing one deletion, the element I deleted is still showing up. What am I doing wrong here?

if(r.left != null)
        {
            return deleteMin(r.left);
        }
        
if(r.right != null)
        {
            AnyType data = (AnyType) r.items.data;
            r = r.right;
            return data;
        }
        
        AnyType data = (AnyType) r.items.data;
        r = null;
        return data;



Is This A Good Question/Topic? 0
  • +

Replies To: How to delete the minimum element from a binary search tree

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10363
  • View blog
  • Posts: 38,355
  • Joined: 27-December 08

Re: How to delete the minimum element from a binary search tree

Posted 19 March 2012 - 11:55 AM

When you say r = null; you are just telling the variable not to point to an Object in memory. If you want to remove a Node, you have to make sure its parent is no longer pointing to it. So if parent.left = null, then the Object parent.left points to in memory will be garbage collected.
Was This Post Helpful? 1
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5757
  • View blog
  • Posts: 12,571
  • Joined: 16-October 07

Re: How to delete the minimum element from a binary search tree

Posted 19 March 2012 - 11:57 AM

Your minimum node would be the left most node. You'd find the node that's the parent of the left most node and then just make left=null. There would be a loop or recursive call to get to that node. It's unclear from your code that you're actually going there. Or why you're messing about with right.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10363
  • View blog
  • Posts: 38,355
  • Joined: 27-December 08

Re: How to delete the minimum element from a binary search tree

Posted 19 March 2012 - 11:58 AM

Quote

Or why you're messing about with right.

If the far-left Node has a right child, that child has to be handled somehow.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5757
  • View blog
  • Posts: 12,571
  • Joined: 16-October 07

Re: How to delete the minimum element from a binary search tree

Posted 19 March 2012 - 12:01 PM

Agreed. It's just unclear we've gotten that far. :P
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1