| home page - news - syllabus - schedule - assignments - tutorials - java - references - Mike Jacobson |
| Instructions - Assignment 1 - Assignment 2 - Assignment 3 - Assignment 4 |
| Assignment 3: Binary Search Trees |
Assignment #3 concerns material that was discussed in this course on or before Wednesday, March 9.
This assignment is due at 11:59 PM on Wednesday, March 23.
EXTENSION: the revised deadline is 11:59 PM on Monday, March 28
traversals.pdf - supplemental nodes on Java iterators and binary tree traversals
SimpleSortedMap.java - Java interfacedescribing a simplified version of the Java Collections Framework SortedMap interface
LinkedListMap.java - an implementation of SimpleSortedMap that uses the singly linked list data structure
KeyFoundException.java - an implementation of the KeyFoundException class required by SimpleSortedMap
KeyNotFoundException.java - an implementation of the KeyNotFoundException class required by SimpleSortedMap
CountWords.java - an application that uses a SimpleSortedMap to count the words and their frequencies in a text file
HarrisonBergeron.txt - a sample text file (that will be used by the TAs for grading this assignment)
Dracula.txt - another (longer) sample text file (that will be used by the TAs for grading this assignment)
The assignment has the following objectives:
to give you practice working with iterative algorithms on binary search trees
to introduce you to iterators and binary tree traversal
to give you practice working with an existing red-black tree implementation in the Java Collections Framework, by adapting it to work with a related interface
to investigate numerically the average height of binary search trees
Expected solutions: solution_3.pdf.
Iterative binary search tree class: BSTMap.java The BoundedArrayStack classes from Assignment 2 are used to implement the in-order traversal iterator.
TreeMap wrapper class: RBTMap.java
Red-black tree class: MyRBTMap.java
A3Q6 program: A3Q6.java
Please address any concerns or questions about the grading of this assignment to Mahshid Marbouti via D2L.
|
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W16/assignments/assignment3.html |