
Comp201: Principles of ObjectOriented Programming

Consider the following binary tree of Integer objects.
7
_ 55
 _ []
 _ 16
 _ 20
  _ []
  _ []
 _ 9
 _ []
 _ []
_ 0
_ 4
 _ []
 _ []
_ 23
_ []
_ []
Notice the following property:
Moreover, this property holds recursively for all subtrees. It is called the binary search tree (BST) property.
In general, instead of Integer objects, suppose we have a set of objects that can be compared for equality with "equal to" and "totally ordered" with an order relation called "less or equal to" . Define "less than" to mean "less or equal to" AND "not equal to". Let T be a BiTree structure that stores such totally ordered objects.
The binary search tree property (BSTP) is defined on the binary tree structure as follows.
We can take advantage of this property when looking up for a particular ordered object in the tree. Instead of scanning the whole tree for the search target, we can compare the search target against the root element and narrow the search to the left subtree or the right subtree if necessary. So in the worst possible case, the number of comparisons is proportional to the height of the binary tree. This is a big win if the tree is balanced. It can be proven that when a tree containing N elements is balanced, its height is at most a constant multiple of logN. For example, the height of a balanced tree containing 10^{6} elements is at most a fixed multiple of 6. Here is the definition of what a balanced tree is.
A binary tree with the BST property is called a binary search tree. It can serve as an efficient way for storage/retrieval of data. We are lead to the following question: how to create and maintain a binary search tree.
Suppose we start with an empty binary tree T and a Comparator that models a total ordering in a given set of objects S. Then T clearly has the BST property with respect the Comparator ordering of S. The following algorithm (visitor on binary trees) will allow us to insert elements of S into T and at the same time maintain the BST property for T. This algorithm also works for binary search tree containing Comparable objects.
package brs.visitor; import brs.*; import java.util.*; /** * Inserts an Object into the host maintaining the host's binary search tree * property via a given Comparator. * Can also be used for Comparable objects. * Duplication is not allowed: replaces old data object with the new one. * @author Dung X. Nguyen  Copyright 2003  All rights reserved. * @since 04/09/2004 */ public class BSTInserter implements IVisitor { private Comparator _order; /** * Used when the items in the tree are Comparable objects. */ public BSTInserter() { _order = new Comparator() { public int compare(Object x, Object y) { return ((Comparable)x).compareTo(y); } }; } /** * Used when we want to order the items according to a given Comparator. * @param order a total ordering on the items to be stored in the tree. */ public BSTInserter (Comparator order) { _order = order; } /** * Returns the host tree where the input is inserted as the root. * @param host an empty binary tree, which obviously satisfies BSTP. * @param input new data to be inserted. * @return host (which is no longer empty). */ public Object emptyCase(BiTree host, Object input) { host.insertRoot (input); return host; } /** * If the input is equal to host.getRootDat) then the old root data is * replaced by input. Equality here is implicitly defined by the total * ordering represented by the Comparator _order. * @param host nonempty and satisfies BSTP. * @param input new data to be inserted. * @return the tree where input is inserted as the root. */ public Object nonEmptyCase(BiTree host, Object input) { Object root = host.getRootDat(); if (_order.compare(input, root) < 0) { return host.getLeftSubTree().execute(this, input); } if (_order.compare(input, root) > 0) { return host.getRightSubTree().execute(this, input); } host.setRootDat(input); return host; } }
Suppose we have a binary search tree based on a given Comparator ordering. The following algorithm will allow us to lookup and retrieve a particular data object from the tree. This algorithm also works for binary search tree containing Comparable objects.
package brs.visitor; import brs.*; import java.util.*; /** * Finds a data object in a binary host tree that satisfies the * Binary Search Tree Property. * The algorithm is similar to that of insertion. * @author Dung X. Nguyen  Copyright 2004  All Rights Reserved * @since 04/09/2004 */ public class BSTFinder implements IVisitor { private Comparator _order; /** * Used when the items in the tree are Comparable objects. */ public BSTFinder() { _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 BSTFinder(Comparator order) { _order = order; } /** * Returns the empty host tree itself. * @param host an empty binary (which obviously satisfies the * Binary Search Tree Property). * @param input not used * @return BiTree the empty host tree. */ public Object emptyCase(BiTree host, Object input) { return host; } /** * Returns the tree such that whose root, if it exists, is equal to input * via the given Comparator _order. * @param host non empty and satisfies BSTP. * @param input object to be looked up. * @return BiTree */ public Object nonEmptyCase(BiTree host, Object input) { Object root = host.getRootDat(); if (_order.compare(input, root) < 0) { return host.getLeftSubTree().execute(this, input); } if (_order.compare(input, root) > 0) { return host.getRightSubTree().execute(this, input); } return host; } }
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 two visitors: one 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 == null, 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 annomymous * helper, passing to it the host as a parameter. * @param host satisfies the binary search tree property. * @param nu == null, 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 a Bitree, the parent of h. */ public Object emptyCase (BiTree h, Object hp) { return hp; } /** * Keep going to the right looking for the max. * @param hp 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 to help carry out the deletion. * @author Dung X. Nguyen * @since 03/07/03 Copyright 2003  All rights reserved. * @since 04/09/2004 */ 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 input not used * @return Boolean.FALSE */ public Object emptyCase(BiTree host, Object input) { 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 input else (at this point, input == root) ask the left subtree for help to remove the host's root using an anonymous helper. * @param host nonempty and satifies BST property * @param input 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, root) < 0) { return host.getLeftSubTree().execute (this, input); } if (_order.compare(input, root) > 0) { return host.getRightSubTree().execute (this, input); } // 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, null); host.setRootDat(maxTree.remRoot()); return Boolean.TRUE; } }, null); } }
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!
Last Revised Thursday, 03Jun2010 09:50:07 CDT
©2004 Stephen Wong and Dung Nguyen