CSC153, Class 53: Implementing Dictionaries with Binary Search Trees
Admin:
* Questions on HW8?
* Saul says Radix Sort can be influenced by the size of the elements.
* Radix is typically pronounced with a long a (at least by those in the know and not Saul's previous teachers)
* The plural of radix is radices
* What is the plural of curriculum vitae? Curricula vitarum
* Grading: Exam 3 this Friday. Everything else a week from Friday, at the earliest, and if ever.
* Plans for Monday
* Proposal: Three Samurai
* Votes for Sushi Popo: 1
* Votes for Three Samurai: 2
* Who has a Monday morning final? Brian. Leave at 11:30 anyway from Darby lot. Sam treats.
* What is the Imperial Measurement of Magnetic Flux?
* Whatever the Queen gets when she measures straw with a magnet?
Overview:
* An ADT for binary search
* Implementing that ADT with arrays
* Implementing that ADT with trees
* Binary search trees as dictionaries
* Balancing trees
Morals of Algorithm/ADT design: Observe/determine the key operations needed for the algorithm, then design an ADT for those operations, then implement the ADT
Start with an early favorite algorithm: Binary search
binarySearch(Collection c)
If there's one element
If it matches what you're looking for, return it
Otherwise, report "not found" (throw an exception, return null, ...)
Look at the middle element:
If it matches what you're looking for, return it
If it is bigger than what you're looking for, recurse on the smaller half
Otherwise, recurse on the larger half
Simplification:
binarySearch(Collection c)
If there are no elements in the collection
Report "not found" (throw an exception, return null, ...)
Look at the middle element:
If it matches what you're looking for, return it
If it is bigger than what you're looking for, recurse on the smaller half
Otherwise, recurse on the larger half
public static boolean binarySearch(Object findMe, BinarySearchable bs)
{
if (bs.isEmpty())
return false;
else {
java.util.Comparator compare = bs.getComparator();
if (bs.middle().equals(findMe)) {
return true;
}
else if (compare.compare(findMe,bs.middle()) < 0) {
return binarySearch(findMe, bs.smaller());
}
else {
return binarySearch(findMe, bs.greater());
}
} // bs is not empty
} // binarySearch(BinarySearchable)
public static Object briansInfinitelyMoreUsefulBinarySearch(Object findMe, BinarySearchable bs)
{
if (bs.isEmpty())
return null;
else {
java.util.Comparator compare = bs.getComparator();
if (compare.compare(bs.middle(), findMe) == 0) {
return bs.middle();
}
else if (compare.compare(findMe,bs.middle()) < 0) {
return briansInfinitelyMoreUsefulBinarySearch(findMe, bs.smaller());
}
else {
return briansInfinitelyMoreUsefulBinarySearch(findMe, bs.greater());
}
} // bs is not empty
} // binarySearch(BinarySearchable)
ADT for "Things that can be binary searched"
public interface BinarySearchable
extends BunchOfStuff
{
/* Notes:
* * The "about" in middle is intentional. Different collections may
* choose different approximations of the middle.
*/
/* General preconditions.
* (1) All the elements in this collection must be comparable by
* this.compare().
*/
/**
* Get the middle element.
* Produces: mid, an Object.
* Pre:
* (1) The collection is non-empty.
* Post:
* (1) mid is less than about half of the elements in the collection
* and greater than about half the elements.
* (2) mid is an element of this collection.
* (3) mid is consistent. Given the same collection, it returns
* the same value.
*/
public Object middle();
/**
* Get the values less than the middle element.
* Produces: smallerHalf, a binary-searchable collection
* Pre:
* (1) At least one item in this collection.
* Post:
* (1) smallerHalf is a subset of this collection.
* (2) If this collection has exactly one item, smallerHalf is empty.
* (3) Each element of smallerHalf is smaller than the middle element.
* More formally, For each s in smallerHalf,
* this.getComparator().compare(s, this.middle()) < 0
* (4) For each e in collection that is smaller than the middle element,
* e is in smallerHalf.
*/
public BinarySearchable smaller();
/**
* Get the values less than the middle element.
* Produces:
* Pre:
* Post:
*/
public BinarySearchable greater();
/**
* Get the comparator used to order elements in this collection.
*/
public java.lang.Comparator getComparator();
/**
* Determine if the collection is empty. (Since we never formally
* defined BunchOfStuff.)
*/
public boolean isEmpty();
} // interface BinarySearchable
public class BinarySearchTree
implements BinarySearchable
{
public BinarySearchTree(Comparator compare) {
this.compare = compare;
}
}
Time for questions