I have to recursivly call the delete method and cannot use loops or comparison t
ID: 3532900 • Letter: I
Question
I have to recursivly call the delete method and cannot use loops or comparison to the null value. I am confused as to how I would do this. I am working with two classes an empty tree class and a non empty tree class. My code implementation is as follows. I am having trouble replacing the node I deleted. can someone point me in the right direction?
Algorithm
1. Perform search for value X
2. If X is a leaf, delete X
3. Else // must delete internal node
a) Replace with largest value Y on left subtree
OR smallest value Z on right subtree
b) Delete replacement value (Y or Z) from subtree
//CODE
public class EmptyTree<K extends Comparable<K>,V> implements Tree<K,V> {
private static EmptyTree SINGLETON = new EmptyTree();
public static <K extends Comparable<K>, V> EmptyTree<K,V> getInstance() {
return SINGLETON;
}
private EmptyTree() {
// Nothing to do
}
public Tree<K, V> delete(K key) {
return this;
}
}
public class NonEmptyTree<K extends Comparable<K>, V> implements Tree<K, V> {
K key;
V value;
Tree<K,V> left;
Tree<K,V> right;
public NonEmptyTree(K key, V value, Tree<K,V> left, Tree<K,V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
//????
public Tree<K, V> delete(K key) {
int compare = key.compareTo(this.key);
//if its empty
if(compare<0){
left = left.delete(key);
}
else if(compare>0){
right = right.delete(key);
}
else if(left.size() == 0)
return right;
else if(right.size() == 0)
return left;
else return this;
}
Explanation / Answer
Iterative Search of Binary Tree
Node *Find( Node *n, int key) {
while (n != NULL) {
if (n->data == key) // Found it
return n;
if (n->data > key) // In left subtree
n = n->left;
else // In right subtree
n = n->right;
}
return null;
}
Node * n = Find( root, 5);
Recursive Search of Binary Tree
Node *Find( Node *n, int key) {
if (n == NULL) // Not found
return( n );
else if (n->data == key) // Found it
return( n );
else if (n->data > key) // In left subtree
return Find( n->left, key );
else // In right subtree
return Find( n->right, key );
}
Node * n = Find( root, 5);