adu0404a
asked on
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;
}
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.)
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.
Also, if a node knows who it's parent is, you could do it that way too.
ASKER
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.
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.
So when the left and right of 'this' are both exceptions (EmptyTree) then you want 'this' to be an EmptyTree too? Is this C++?
ASKER
Yes that is exactly what I want to do. This is in Java.
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.
I think I see the problem.
Right now you are doing this
if(key.compareTo(this.key)
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)
//It's the root. Delete the whole tree
else if(key.compareTo(this.righ
// here actually delete this.right and recreate it as an EmptyTree if you want
else if(key.compareTo(this.left
//delete it
//Now do
else if(key.compareTo(this.key)
this.right.delete(key);
else if(key.compareTo(this.key)
this.left.delete(key);
//All possibilities have been checked, no else is needed.
Right now you are doing this
if(key.compareTo(this.key)
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)
//It's the root. Delete the whole tree
else if(key.compareTo(this.righ
// here actually delete this.right and recreate it as an EmptyTree if you want
else if(key.compareTo(this.left
//delete it
//Now do
else if(key.compareTo(this.key)
this.right.delete(key);
else if(key.compareTo(this.key)
this.left.delete(key);
//All possibilities have been checked, no else is needed.
ASKER
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
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.
My idea is just to return something useful that can tell it that it needs to be deleted.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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).
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).
ASKER
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.
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.
I am currently doing a project like this too
If you are here from UMD, Make sure you actually do the work. It is easy, follow the thread and try to find out where your code does not work. line 3 in the code above is not recursing properly, so is line 5. Apart from that, everything else seems fine. Remember DO NOT JUST COPY. Read and Understand, compare it with your code and figure out where you are going wrong. As earlier mentioned., testing the objects defeats the purpose of inheritance