CSC152 2004F, Class 38: Dictionaries (2): Binary Search Trees

Admin:
* Cool talk Wednesday!
* Project discussion tomorrow.
* Exam discussion delayed until Friday.
* Cool convo (and other seminars): Incarceration

Overview:
* Detour: Binary Search Revisited (with an ADT)
* Implementing the BinarySearchable ADT
* An alternative: Search trees

"Get something that's in the middle"
"Look at the left or the right"
* "Try to avoid looking at everything to the left and then everything to the right"
* Look in the middle.  If it's bigger than what we're looking for, look to the left.  If it's smaller, look to the right.  If it's the same, we're done.
* To express this "smaller, greater, equal", we use a Comparator.
* Possible return values:
  * The matching object [Today]
  * The index of the matching object [Exam]
  * True or false [Outline]
* Two strategies for "look in left and right"
  * Recursively
  * Loop (for or while loop)
* Concern when you recurse: How do you build "the new array that only goes up to the middle"?  (And should you?)
  n/2 + n/4 + n/8 + .... = n* (1/2 + 1/4 + 1/8 + .... + 1/2^n) = O(n)
  * But binary search should be logn
public Object binarySearch(Object[] values, Object findMe, Comparator c) 
{
	return binarySearch(values, findMe, c, 0, values.length-1);
}
private Object binarySearch(Object[] values, Object findMe, Comparator c, int lb, int ub) 
{
	int m = (lb + ub) / 2;
	Object mid = values[m];
	if (c.compare(findMe, mid) < 0)
		return binarySearch(values, findMe, c, lb, m-1);
	else if (c.compare(findMe, mid) > 0)
		return binarySearch(values, findMe, c, m+1, ub);
	else return mid;
} // binarySearch(Object[], Object)
* How would we check whether or not this works correctly?
  * Give it some values and see whether it gives the right result.
  * Also check that it has the correct running time.
* For each array size between 0 and 32
  * Fill the array with the values 0, 2, .... 2*(size-1)
  * Search for the values -1 to 2*size-1 // Every value in the array and every value that falls between two neighbors
    * Verify the return value
* This much testing gives you more assurance

Observation: When you are using a structure (in this case, an array) in a certain way, generalize to an ADT.

Challenge: Let's design an ADT for "BinarySearchable"
* Philosophy: Things which we can binary search.
* Methods
  * getMiddle()
  * getSmallerThanMiddle()
  * getLargerThanMiddle()
* Applications: Binary search
private Object binarySearch(BinarySearchable bs, Object findMe, Comparator c)
{
	Object mid = bs.getMiddle();
	if (c.compare(findMe, mid) < 0)
		return binarySearch(bs.getSmallerThanMiddle(), findMe, c)
	else if (c.compare(findMe, mid) > 0)
		return binarySearch(bs.getLargerThanMiddle(), findMe, c)
	else return mid;
} // binarySearch(Object[], Object)
* Implementations
  * As a sorted array with a lb and ub

* Why choose this design of binary search rather than the earlier design?
  * We can choose a different implementation of the things we search
  * We get rid of lb and ub in the binary search code, which makes it clearer

/Implementing Dictionaries with BinarySearchable/
/adfasddf asdfasdfa/

* Need to think about find, add, and remove
* find is straightforward: 
  * Store key/value pairs in the BinarySearchable
  * Search by key
  * Return the value part of the pair
* If we use sorted arrays, add and remove are probably O(n)

/Alternate Implementation/

* Use trees!  Divide and conquer the data structure.
* The root is the middle element
* The left subtree contains the smaller elements
* The right subtree contains the larger elements
* The subtrees are organized in the same way

* Addition: Follow the tree down and add when you run off the tree
* Removal: Shove the rightmost thing in the left subtree (or the leftmost thing in the right subtree) in the place of the deleted element
* Problem: Keeping it balanced:
  * Wait until 301
  * When you notice severe imbalance, spend the O(n) time to rebalance
* Running time
  * find: O(logn)
  * add: O(logn)
  * remove: O(logn)
* Significantly better than a sorted array for add and remove; comparable for find

What's the difference between a binary search tree and a heap?
* Root value
  * Heaps put the "smallest" value at the root
  * Binary search trees put the "middle" value at the root
* Structure
  * Heaps are guaranteed to be nearly-complete
  * Binary search trees are "hopefully balanced"

Can we do better than balanced binary search trees?
* Yes, if we rely on luck in different ways
* Wednesday's topic
  * find: O(1)
  * add: O(1)