| << Chapter < Page | Chapter >> Page > |
The algorithm to remove a particular data object from a binary search tree is more involved. When the element to be removed is not at a leaf node, we can replace it with the largest element of the left subtree (if it's not empty) or the smallest element of the right subtree (if it's not empty). In preparation, we write a visitor to find the subtree containing the largest element at the root.
package brs.visitor;
import brs.*;import ordering.*;/**
* Returns the subtree of the host with the max value in the root if the tree* is not empty, otherwise returns the host itself, assuming the tree satisfies
* the BST property.* @author DXN
*/public class MaxTreeFinder implements IVisitor {
public static final MaxTreeFinder Singleton = new MaxTreeFinder ();private MaxTreeFinder () {
}/*** The host tree is empty: the tree containing the max is the host itself.
* @param host satisfies the binary search tree property.* @param nu not used.
* @return BiTree the empty host itself.*/
public Object emptyCase(BiTree host, Object... nu) {return host;
}/*** Asks the right subtree of the host to find the max via an
* anomymous helper, passing to it the host as a parameter.* @param host satisfies the binary search tree property.
* @param nu not used.* @return BiTree the subtree with maximum root.
*/public Object nonEmptyCase (BiTree host, Object... nu) {
return host.getRightSubTree().execute (new IVisitor () {/**
* The BST parent of an empty right subtree contains the max* at the root.
* @param hp[0]a Bitree, the parent of h.
*/public Object emptyCase (BiTree h, Object... hp) {
return hp[0];
}/*** Keep going to the right looking for the max.
* @param hp[0]a Bitree, the parent of h.
*/public Object nonEmptyCase (BiTree h, Object... hp) {
return h.getRightSubTree ().execute (this, h);}
}, host);}
}
We are now ready to write the deletion algorithm for a binary search tree ordered according to a given Comparator. This algorithm also works for binary search tree containing Comparable objects.
package brs.visitor;
import brs.*;import java.util.*;/**
* Deletes the given input from the host tree. Returns TRUE if the input is in* the host tree, otherwise return FALSE.
Invariant: host contains unique objects and satisfies the BST property.Post: host does not contains the input.
Algorithm:Case host is empty:
returns FALSE because there is nothing to remove.Case host is not empty:
if input<root
return the result of asking the left subtree to delete the input;else if root<input
return the result of asking the right subtree to delete the input;else if host's left subtree is empty (at this point, input == root)
ask host to remove its root (and become its right subtree)returns TRUE
else {ask host to replace the root with the maximum value of its left subtree;
the subtree that contains the maximum must have an empty right subtree;thus it is safe to ask this subtree to remove its root;
return TRUE}NOTE:As you have been indoctrinated, it is "uncouth" do ask something for what it
is. Instead of checking a subtree for emptiness, we should ask the subtree tohelp carry out the deletion.
*/public class BSTDeleter implements IVisitor {
private Comparator _order;/*** Used when the items in the tree are Comparable objects.
*/public BSTDeleter() {
_order = new Comparator() {public int compare(Object x, Object y) {
return ((Comparable)x).compareTo(y);}
};}
/**
* Used when the items are ordered according to a given Comparator.* @param order a total ordering on the items stored in the tree.
*/public BSTDeleter (Comparator order) {
_order = order;}/**
* There is nothing to delete.
* @param host is empty and obviously satisfies the BST Property.* @param nu not used
* @return Boolean.FALSE*/
public Object emptyCase(BiTree host, Object... nu) {return Boolean.FALSE;
}/**if input<root
ask the host's left subtree to delete the input;else if root<input
ask the host's right subtree to delete the inputelse (at this point, input == root)
ask the left subtree for help to remove the host's root using ananonymous helper.
* @param host non-empty and satifies BST property* @param input[0] object to be deleted from the host.* @return Boolean.
*/public Object nonEmptyCase(final BiTree host, Object... input) {
Object root = host.getRootDat();if (_order.compare(input[0], root)<0) {
return host.getLeftSubTree().execute (this, input[0]);
}if (_order.compare(input[0], root)>0) {
return host.getRightSubTree().execute (this, input[0]);
}// At this point: input is equal to root.
return host.getLeftSubTree().execute(new IVisitor() {/**
* The outer host can safely remove its root and* becomes its right subtree.
* @param h the left subtree of the outer host.*/
public Object emptyCase (BiTree h, Object notUsed) {host.remRoot();
return Boolean.TRUE;}/**
* Finds the maximum value in the h paramter.* Asks the outer host parameter to set its root to this
* maximum value, and removes this maximum value from the* subtree containing this maximum value.
* @param h the left subtree of the outer host.*/
public Object nonEmptyCase (BiTree h, Object notUsed) {BiTree maxTree = (BiTree)h.execute(MaxTreeFinder.Singleton);
host.setRootDat(maxTree.remRoot());return Boolean.TRUE;
}});
}}
We now have all the needed ingredient to implement an efficient container for storage/retrieval/lookup, using the BiTree framework together with the above visitors!
Notification Switch
Would you like to follow the 'Principles of object-oriented programming' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|