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!