Homework SourseThere is BinarySearchTree class When removing a node from a
There is BinarySearchTree class. When removing a node from a BST, we can replace it with either its predecessor or its successor. Complete the predecessor() method
so that it returns the node that comes immediately before e. Hint: the work needed to find the predecessor is a mirror image of what is required to find a node\'s
successor, so use successor() as a resource.
BinarySearchTree class:
Solution
package edu.buffalo.cse116;
import java.util.AbstractSet;
import java.util.Iterator;
public class BinarySearchTree<E extends Comparable<E>> extends AbstractSet<E> {
protected BTNode<E> root;
protected int size;
/**
* Initializes this BinarySearchTree object to be empty, to contain only
* elements of type E, to be ordered by the Comparable interface, and to
* contain no duplicate elements.
*/
public BinarySearchTree() {
root = null;
size = 0;
}
/**
* Initializes this BinarySearchTree object to contain a shallow copy of a
* specified BinarySearchTree object. The worstTime(n) is O(n), where n is the
* number of elements in the specified BinarySearchTree object.
*
* @param otherTree - the specified BinarySearchTree object that this
* BinarySearchTree object will be assigned a shallow copy of.
*/
public BinarySearchTree(BinarySearchTree<? extends E> otherTree) {
root = copy(otherTree.root, null);
size = otherTree.size;
}
protected BTNode<E> copy(BTNode<? extends E> p, BTNode<E> parent) {
if (p != null) {
BTNode<E> q = new BTNode<E>(p.element, parent);
q.left = copy(p.left, q);
q.right = copy(p.right, q);
return q;
}
return null;
} // method copy
/**
* Finds the predecessor of a specified BTNode object in this BinarySearchTree. The worstTime(n) is O(n) and
* averageTime(n) is constant.
*
* @param e - the BTNode object whose successor is to be found.
* @return the successor of e, if e has a successor; otherwise, return null.
*/
protected BTNode<E> predecessor(BTNode<E> e) {
}
@SuppressWarnings(\"unchecked\")
@Override
public boolean equals(Object obj) {
if (!(obj instanceof BinarySearchTree)) {
return false;
}
return equals(root, ((BinarySearchTree<? extends E>) obj).root);
} // method 1-parameter equals
public boolean equals(BTNode<E> p, BTNode<? extends E> q) {
if ((p == null) || (q == null)) {
return p == q;
}
if (!p.element.equals(q.element)) {
return false;
}
if (equals(p.left, q.left) && equals(p.right, q.right)) {
return true;
}
return false;
}
/**
* Returns the size of this BinarySearchTree object.
*
* @return the size of this BinarySearchTree object.
*/
@Override
public int size() {
return size;
}
/**
* Iterator method will be implemented for a future
*
* @return an iterator positioned at the smallest element in this
* BinarySearchTree object.
*/
@Override
public Iterator<E> iterator() {
// Skipped in preparation for next week
throw new UnsupportedOperationException(\"Not implemented yet!\");
}
/**
* Determines if there is at least one element in this BinarySearchTree object
* that equals a specified element. The worstTime(n) is O(n) and
* averageTime(n) is O(log n).
*
* @param obj - the element sought in this BinarySearchTree object.
* @return true - if there is an element in this BinarySearchTree object that
* equals obj; otherwise, return false.
* @throws ClassCastException - if obj cannot be compared to the elements in
* this BinarySearchTree object.
* @throws NullPointerException - if obj is null.
*/
@Override
public boolean contains(Object obj) {
return getBTNode(obj) != null;
}
/**
* Ensures that this BinarySearchTree object contains a specified element. The
* worstTime(n) is O(n) and averageTime(n) is O(log n).
*
* @param element - the element whose presence is ensured in this
* BinarySearchTree object.
* @return true - if this BinarySearchTree object changed as a result of this
* method call (that is, if element was actually inserted); otherwise,
* return false.
* @throws ClassCastException - if element cannot be compared to the elements
* already in this BinarySearchTree object.
* @throws NullPointerException - if element is null.
*/
@Override
public boolean add(E element) {
if (root == null) {
if (element == null) {
throw new NullPointerException();
}
root = new BTNode<E>(element, null);
size++ ;
return true;
}
else {
BTNode<E> temp = root;
int comp;
while (true) {
comp = element.compareTo(temp.element);
if (comp == 0) {
return false;
}
if (comp < 0) {
if (temp.left != null) {
temp = temp.left;
} else {
temp.left = new BTNode<E>(element, temp);
size++ ;
return true;
} // temp.left == null
} else if (temp.right != null) {
temp = temp.right
} else {
temp.right = new BTNode<E>(element, temp);
size++ ;
return true;
} // temp.right == null
} // while
} // root not null
} // method add
/**
* Ensures that this BinarySearchTree object does not contain a specified
* element. The worstTime(n) is O(n) and averageTime(n) is O(log n).
*
* @param obj - the object whose absence is ensured in this BinarySearchTree
* object.
* @return true - if this BinarySearchTree object changed as a result of this
* method call (that is, if obj was actually removed); otherwise,
* return false.
* @throws ClassCastException - if obj cannot be compared to the elements
* already in this BinarySearchTree object.
* @throws NullPointerException - if obj is null.
*/
@Override
public boolean remove(Object obj) {
BTNode<E> e = getBTNode(obj);
if (e == null) {\\
return false;
}
deleteBTNode(e);
return true;
}
/**
* Finds the BTNode object that houses a specified element, if there is such an BTNode. The worstTime(n) is
O(n), and
* averageTime(n) is O(log n).
*
* @param obj - the element whose BTNode is sought.
* @return the BTNode object that houses obj - if there is such an BTNode; otherwise, return null.
* @throws ClassCastException - if obj is not comparable to the elements already in this BinarySearchTree
object.
* @throws NullPointerException - if obj is null.
*/
@SuppressWarnings(\"unchecked\")
protected BTNode<E> getBTNode(Object obj) {
int comp;
if (obj == null) {
throw new NullPointerException();
}
if (!(obj instanceof Comparable)) {
return null;
}
Comparable<E> compObj = (Comparable<E>) obj;
BTNode<E> e = root;
while (e != null) {
comp = compObj.compareTo(e.element);
if (comp == 0) {
return e;
} else if (comp < 0) {
e = e.left;
} else {
e = e.right;
}
} // while
return null;
}
/**
* Deletes the element in a specified BTNode object from this BinarySearchTree.
*
* @param p - the BTNode object whose element is to be deleted from this BinarySearchTree object.
* @return the BTNode object that was actually deleted from this BinarySearchTree object.
*/
protected BTNode<E> deleteBTNode(BTNode<E> p) {
size-- ;
// If p has two children, replace p\'s element with p\'s successor\'s
// element, then make p reference that successor.
if ((p.left != null) && (p.right != null)) {
BTNode<E> s = successor(p);
p.element = s.element;
p = s;
} // p had two children
// At this point, p has either no children or one child.
BTNode<E> replacement;
if (p.left != null) {
replacement = p.left;
} else {
replacement = p.right;
}
// If p has at least one child, link replacement to p.parent.
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null) {
root = replacement;
} else if (p == p.parent.left) {
p.parent.left = replacement;
} else {
p.parent.right = replacement;
}
} // p has at least one child
else if (p.parent == null) {
root = null;
} else {
if (p == p.parent.left) {
p.parent.left = null;
} else {
p.parent.right = null;
}
} // p has a parent but no children
return p;
} // method deleteBTNode
/**
* Finds the successor of a specified BTNode object in this BinarySearchTree. The worstTime(n) is O(n) and
* averageTime(n) is constant.
*
* @param e - the BTNode object whose successor is to be found.
* @return the successor of e, if e has a successor; otherwise, return null.
*/
protected BTNode<E> successor(BTNode<E> e) {
if (e == null) {
return null;
} else if (e.right != null) {
// successor is leftmost BTNode in right subtree of e
BTNode<E> p = e.right;
while (p.left != null) {
p = p.left;
}
return p;
} // e has a right child
else {
// go up the tree to the left as far as possible, then go up
// to the right.
BTNode<E> p = e.parent;
BTNode<E> ch = e;
while ((p != null) && (ch == p.right)) {
ch = p;
p = p.parent;
} // while
return p;
} // e has no right child
} // method successor
protected static class BTNode<E> {
protected E element;
protected BTNode<E> left = null, right = null, parent;
/**
* Initializes this BTNode object. This default constructor is defined for the sake of subclasses of the
* BinarySearchTree class.
*/
public BTNode() {}
/**
* Initializes this BTNode object from element and parent.
*/
public BTNode(E element, BTNode<E> parent) {
this.element = element;
this.parent = parent;
} // constructor
} // class BTNode
} // class BinarySearchTre
