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. We can take advantage of this property when looking up for a particular Integer 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 "more of less" balanced. This is because when the tree is balanced, that is the difference between the heights of the left and right subtrees is O(1), its height is O(logN), where N is the number of elements in the tree.
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. We first generalize the notion of ordering.
In order to compare objects in a set for inequality, we need what is called a totally ordered relation on the set. Such a concept is studied in a discrete mathematics course. For our purpose, we can think of a totally ordered relation as a bolean function that takes two any two objects in the set and return a ture or false in a way similar to the "<=" (less or equal to) ordering for integers. To facilitate comparison, we break up the comparison for "<=" into two comparisons: "<" (less than), "=" (equal) and encapsulate them into the following abstract class.
public abstract class AOrder {
/** defines a "less than"
strict ordering.*/
public abstract boolean lt(Object x, Object y);
/** defines equality. */
public abstract boolean eq(Object x, Object y);
/** defines equality. */
public boolean ne(Object x, Object y) {
return !eq(x, y);
}
/** defines equality. */
public boolean le(Object x, Object y) {
return lt(x, y) || eq(x, y);
}
/** defines equality. */
public boolean gt(Object x, Object y) {
return !le(x, y);
}
/** defines equality. */
public boolean ge(Object x, Object y) {
return !lt(x, y);
}
}
For specific and concrete ordering of a specific set of objects, we need to provide a concrete subclass of AOrder with concrete lt and eq methods. We can now use AOrder as a "strategy" for comparison to perform the task for insertion, search, and deletion on binary trees. The following is an example of a concrete ordering of Integer.
/**
* Represents the standard ordering on integers.
*/
public class OrderInt extends AOrder {
public static final OrderInt Singleton = new OrderInt ();
private OrderInt() {
}
public boolean lt(Object x, Object y) {
return ((Integer)x).intValue() <
((Integer)y).intValue();
}
public boolean eq(Object x, Object y) {
return x.equals(y);
}
}