Results 1 to 4 of 4
  1. #1
    hoosierfan24 is offline Member
    Join Date
    Oct 2010
    Posts
    45
    Rep Power
    0

    Default FindMin and Max in a BST after Lazy deletion

    Ive been working on this problem for two days now and cant seem to figure it out. I can do it by hand and know it has to be a recursive solution but I just cant get my recursion to work the way I want it to. When I say lazy deletion I mean the node is still
    in the tree it just has a boolean called deleted that gets set to true if it is deleted

    this is what I currently have

    Java Code:
    private BinaryNode<E> findMin(BinaryNode<E> t) 
    	{
    		BinaryNode<E> r = t;
    	
    		if(t==null)
    			return null;
    		//found deleted node
    		if(t.deleted && t.left!=null)
    		{	
    			return findMin(t.left);
    		}
    		if(t.deleted && t.left==null)
    		{
    			if(t.right==null)
    			{
    				return findMin(r);
    			}
    			return findMin(t.right);
    		}
    		
    		//found real node
    		if(t.left ==null && !t.deleted)
    		{
    			return t;
    		}
    		if(t.left !=null && !t.deleted)
    		{
    			return findMin(t.left);
    		}
    		
    		return null;
    	}
    it returns the minimum though only ifW the actual minimum has not been lazily deleted from the tree. New update to the code allows it to get the minimum even if the smallest is deleted but the second smallest can only be one level higher than it
    Last edited by hoosierfan24; 02-22-2013 at 05:22 AM. Reason: code update

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,453
    Blog Entries
    7
    Rep Power
    20

    Default Re: FindMin and Max in a BST after Lazy deletion

    I think you're over complicating things: you want to find the leftmost node that is not deleted; the following will do the job:

    Java Code:
    private BinaryNode<E> findMin(BinaryNode<E> t) {
    
       if (t == null) return null;
    
       BinaryNode<E> tmp= findMin(t.left);
    
       if (tmp != null) return tmp;
    
       if (!t.deleted) return t;
    
       return findMin(t.right);
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    hoosierfan24 is offline Member
    Join Date
    Oct 2010
    Posts
    45
    Rep Power
    0

    Default Re: FindMin and Max in a BST after Lazy deletion

    The left most node might not necessarily be the smallest node in the tree tho. For example if the root of the bst is
    77 and you insert 34, 7, 50, 28, 75, 20, 71, 15 and say you lazilly delete all the odd numbers your code would return 34 when the answer is actually 20

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,453
    Blog Entries
    7
    Rep Power
    20

    Default Re: FindMin and Max in a BST after Lazy deletion

    Quote Originally Posted by hoosierfan24 View Post
    The left most node might not necessarily be the smallest node in the tree tho. For example if the root of the bst is
    77 and you insert 34, 7, 50, 28, 75, 20, 71, 15 and say you lazilly delete all the odd numbers your code would return 34 when the answer is actually 20
    That's why my algorithm also checks the right subtree if a (root) node were deleted and nothing could be found in the left subtree.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Lazy Initialization
    By onegcr in forum New To Java
    Replies: 1
    Last Post: 08-14-2007, 03:29 PM

Tags for this Thread

Posting Permissions

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