CSC152 2005S, Class 38: Binary Search Trees

Admin:
* Extra credit for run on Saturday and talk tomorrow
* Possible visitor today
* Questions on the exam?

Overview:
* Binary search trees
* Lab
* Reflection (maybe)

/Exam Questions/
In problem 3, you said "Indicate the running time of put, get, peek, and isEmpty for your data structure."  I can't remember if you wanted us to give a running time like O(log2n) or something other than that.
* Yes, indicate running times with big-O notation
* Try to be as close as possible, but bound above

In problem 4, you said "Generalize that implementation to permit a heap of any kind of comparable value."  Do you want us to do what we did today in class with generics or do you want us to create a class that has a method "compareTo" for all the comparable types we can think of?  Or do you want us to do some other solution that I'm not thinking of?
* You do not need to do generics.
* You can, however, write put and get so that they expect a Comparable as a parameter
* If your client is so stupid that he puts an Integer and a String in the heap, is it okay that your program crashes?  Yes.

/Binary Search Trees/
* Review: What is a tree?
  * A data structure made of "complex nodes" that are connected from parent to child, usually with multiple children per parent (and one parent per child)
  * The length of the longest path from the "progenitor" (root) to a child is the depth
* Review: What is a binary tree?
  * A tree in which each node has zero, one or two children
* Review: What is a complete tree?
  * Every non-leaf node has two children
  * Children are all at the same level

Binary search tree:
* Binary tree
* Each node has two associated fields (along with the links):
  * Index (key)
  * Value
* Policy: The indices of all left descrendants are less than the index of the root; the indices of all right descendants are greater than the index of the root
  * Applies at every level

* Rolf wants there to be about the same number of values in each half
* Learn how to do that in CSC301

DO THE LAB!