Polymorphic binary search tree deletion

I'm not sure how to delete a leaf. The methods min() and max() will throw a TreeIsEmptyException if the left or right tree is empty. If a second TreeIsEmptyException is caught, that means that 'this' has no children and I want to get rid of it. For example, say I have {0,1,2,3,4,5,6,7,8,9}  and I want to delete 8, the tree returned is {0,1,2,3,4,5,6,6,7,9} so I need to figure out how to get rid of the extra 6. I am not allowed to use null.
public Tree<K, V> delete(K key) {
  if(key.compareTo(this.key) > 0){
     this.right.delete(key);
  }else if(key.compareTo(this.key) < 0){
     this.left.delete(key);
  }else{
       try{
	  this.value = this.search(this.left.max());
	  this.key = this.left.max();
	  this.left.delete(this.key);	
       }catch(TreeIsEmptyException e){
	    try{this.value =this.search(this.right.min());
		this.key = this.right.min();
		this.right.delete(this.key);
	    }catch(TreeIsEmptyException f){
		//remove 'this' 
	    }
	}
    }
    return this;
}

Open in new window

adu0404aAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

peprCommented:
How the tree is represented?  The lists say nothing about the real structure.  Why do you use exceptions in the case? What is the bigger view of the task? (I assume it is a homework. You can get some advice, but you have to create and understand YOUR solution.)
0
TommySzalapskiCommented:
You have to delete the node from it's parent. You could use null but then make a CleanUp function that goes through and deletes all the null children until it doesn't find any. That may be the easiest solution to implement.
Also, if a node knows who it's parent is, you could do it that way too.
0
adu0404aAuthor Commented:
Sorry for not providing information.
I'm not sure how to describe how the tree is represented, but here it goes...
So the 'nodes' in the tree are represented by objects "NonEmptyTree" and "EmptyTree". NonEmptyTree and Empty tree implement a "Tree" interface. Empty tree is implemented as a singleton. NonEmptyTree has instance variables for the key, the value, and left and right subtrees of type "Tree". So the key represents the 'root' of that specific tree. The lists are just me doing an inorder traversal of the tree and putting the elements in a list. The whole using the exceptions thing is just a requirement of the project. I am also not allowed to add any helper methods. The only things a Tree can do is search, insert, delete, get size, get min and max values, add elements to a collection, and get a subtree. Also, I cannot make any comparisons to null or use anything like getClass etc. I think this is to force using exceptions to handle the difference between a NonEmptyTree and an EmptyTree. I know that I somehow need to set the 'Tree' I want to delete to be an EmptyTree, but I can't think of how to do this. Hope that clarified my question a bit. Thank you.
0
Exploring ASP.NET Core: Fundamentals

Learn to build web apps and services, IoT apps, and mobile backends by covering the fundamentals of ASP.NET Core and  exploring the core foundations for app libraries.

TommySzalapskiCommented:
So when the left and right of 'this' are both exceptions (EmptyTree) then you want 'this' to be an EmptyTree too? Is this C++?
0
adu0404aAuthor Commented:
Yes that is exactly what I want to do. This is in Java.
0
peprCommented:
In my opinion, the "get size" operation can be used as the predicate that makes difference between EmptyTree and NonEmptyTree. Moreover, if EmptyTree is a singleton, then the reference or pointer can be used for comparison instead of the null constant.  Actually, the EmptyTree singleton shoul probably be used wherever the simpler implementation would use null. I still believe that "forced usage of exceptions" is a wrong deduction.
0
TommySzalapskiCommented:
I think I see the problem.
Right now you are doing this
  if(key.compareTo(this.key) > 0){
     this.right.delete(key);

If they delete the root, then you kill the whole tree. Otherwise, you want to delete from the parent. So delete should check if the root is being deleted then check
  if(key.compareTo(this.key) == 0)
    //It's the root. Delete the whole tree
  else if(key.compareTo(this.right.key) == 0)
     // here actually delete this.right and recreate it as an EmptyTree if you want
  else if(key.compareTo(this.left.key) == 0)
    //delete it
  //Now do
  else if(key.compareTo(this.key) > 0)
    this.right.delete(key);
  else if(key.compareTo(this.key) < 0)
    this.left.delete(key);
  //All possibilities have been checked, no else is needed.
0
adu0404aAuthor Commented:
Sorry, I think I'm still being clear on what I am trying to accomplish. I don't want to delete a key along with its left and right subtrees, I only want to delete the key itself.
Say I have this tree:
                        4
        1                              5
0            2                                8
                    3                 7               9
                                 6

Say I want to delete 8, i want get:
                       4
          1                          5
   0           2                           7
                     3               6           9

But right now I get:
                      4
         1                         5
   0          2                         7
                    3             6            9
                             6

So far my method will delete the key it is supposed to in every case, just I still have (in this case) an extra six. I need that leaf 6 to be an EmptyTree. So I somehow need to get set the left subtree of the previous 6 to an EmptyTree.
0
TommySzalapskiCommented:
Try this. When you get to the final node to delete (that last 6) return 0. I think it would be that part that has the
// remove this
line. Change it so that it returns 0 if it gets there and 1 (or this) otherwise. Then, in the parent, if the delete call returns 0, delete it.
Something like
  if(key.compareTo(this.key) > 0){ //this is your line 2
     if(this.right.delete(key) == 0) //this is to replace your line 3
       this.right = new EmptyTree //or however Java would do it.

Open in new window

And then you would do the same thing for left of course too.
Then your lines 15-16 could look like
	    }catch(TreeIsEmptyException f){
	       return 0;

Open in new window

Or if you don't like having returns in the middle, just set up a bool or a variable for the return.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
adu0404aAuthor Commented:
Ok, I'm starting to get how to do this. But I can't return 0, can I?  Because the return type is a tree. So I was thinking maybe I return an emptyTree and use your line 2 but instead of 0, compare the return value to an emptyTree.....but  I am not allowed to do that.
0
TommySzalapskiCommented:
If you are returning 'this' then you are returning a pointer, not a tree. It would actually return a pointer to a tree. So you actually can use 0 since it's a valid pointer value.
My idea is just to return something useful that can tell it that it needs to be deleted.
0
peprCommented:
As far as I know Java has no pointers.  The null is also the singleton -- a possible value of a reference variable.  In C++, the 0 is (mostly) equal to NULL (the new standard tends to make a difference because of type checking, anyway...).

If the Java code should return a (sub)tree/node refrerence in this case, it can never return 0.  If it should return the indication of nothing in the tree, it should return the reference to the EmptyTree object (singleton).

See http://en.wikipedia.org/wiki/Binary_tree#Deletion for the pictures on how to delete the node. The mentioned "unambiguous" deletion of the node means that there is more possibilities how to attach the rest under the deleted node.

As you need the binary SEARCH tree, each node value in the left subtree has to be smaller than the node value, and each node value in the right subtree has to be bigger than the node value. This must be reflected also in the insert/delete operations. Also, you usually want to build the "most efficient" binary search tree, which means the "ballanced" binary search tree.  Any operation of insertion/deletion can corrupt the ballance. Also the definition of "balanced" is a tradeoff (unless the tree has a special number of nodes). See pictures and explanation here http://en.wikipedia.org/wiki/Binary_search_tree#Deletion

For the polymorphic behaviour, the EmptyTree and NonEmptyTree has to have the common base class, or the EmptyTree is the base class for NonEmptyTree.
0
peprCommented:
The examples of implementation of operations on the last referenced page are in a symbolic language.  Think about replacing "self" by "this", the "None" is your "null" or better the reference to the EmptyTree singleton instance in your case.

The "def something(self, ..."   is the definition of the method of the class.  Actually, it is not "a symbolic language", it is written in the Python language.  The explicit self as the first argument of the functions is just needed in Python.  In Python, there is no problem with types of references as all references are untyped -- the type is bound to the referenced instance, not to the reference itself.  Because of that you may need to be more carefull with the algorithms.

I am not fluent in Java as I do not use it.  However, the book "Thinking in Java" by Bruce Eckel is said to be very good source of information -- available also in the electronic form form for free (http://www.mindview.net/Books/TIJ/).

By the way, he has written also "Thinking in C++" -- just excellent (http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html).
0
adu0404aAuthor Commented:
Thank you both so much for your help. I was able to figure out a solution.

Tommy: Your suggestion about returning 0 pointed me in the right direction and really got the ball rolling. Except instead of returning 0, I returned an EmptyTree in the last else block (line 16).

Pepr: I had looked at those references you posted (many times) before I posted my question, but I did not understand how to apply them to my specific case. However, once you posted the links I went back through them again and this time something clicked. Everywhere I said this.right.delete(key) or this.left.delete(key), I really needed to say this.right = this.right.delete(key) and this.left = this.left.delete(key).

I'm still on the trail membership as of now, but I will more than likely continue my membership after the free trial is over, thanks to how helpful you both were.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.