Comp 121 – Introduction to Data Structures

Comp 121 – Introduction to Data Structures. Spring 2000

Programming Assignment 3 -- Due March 28, 2000

Objective: To gain experience in implementing binary trees.

Goal. To implement the binary search tree ADT as an object template in C++. To use this ADT as the basis of a sorting program.

The binary search tree (bstree) abstract data type is specified as follows [p. 490 of your text]:

AbstractDataType bstree{

Instances: binary trees; each node has an element; all elements are distinct; elements in the left subtree of any node are smaller than the element in the node; elements in the right subtree are larger.

Operations:

create( ): Create an empty binary search tree

destroy( ): Erase a binary search tree

find(k): Return true if the binary search tree contains the element k; false otherwise.

printSort( ): Output all elements in the binary search tree in ascending order

delete(k): Delete the element k from the binary search tree.

Insert(k): Insert the element k into the binary search tree

}

You are to implement this ADT in the C++ programming language. Feel free to refer to the code in the text for help – however, your work should be your own, and not a copy of the text code.

Sorting. In a prior assignment (Programming Assignment 1), you implemented a program for sorting a number of points with the help of a priority-queue. You are to now compare the performance of that sorting program with the following:

Given a file of elements that are to be sorted, we can insert these elements successively into a binary search tree, and then call printSort( ) to print out all the elements in the tree in sorted order.

You will be required to collect timing information on the performance of both your sorting programs – the one using priority queues, and the current one – in sorting certain data-sets that will be made available on the class web-page prior to the assignment due-date. These data-sets will be in the same format as in Programming Assignment 1: you will be given the points to be sorted in a file, which contains the number of points in the file followed by a pair of coordinates for each point.

Rules for submitting this program:

Recall that you are not permitted to work in groups – all your work must be your own, and you must attest to this in a signed comment that begins each program.

Include a (neatly typed – not handwritten) design plan. This design plan should contain a detailed description of all algorithms you use. Include some general comments on the structure and layout of your assignment.

Include a complete listing of all your code, input files, and output files. Since you will be using the Point class that you implemented for Assignment 1, include a listing of this class as well.

Your code must be appropriately commented – if we don’t understand your code with reasonable effort, you get no credit for it. Include comments on the "big-Oh" run-time complexity of all public methods. For this assignment, comments on the average run-time may also be useful.

Include a test plan detailing how you tested your ADT, and why you believe it is correct. (Note that the sorting part of your assignment need not test the entire ADT – only the create, insert, and printSort functions.)

A number of different data-sets will be made available on the course web page a few days prior to the assignment due-date. You are to collect and submit timing information on sorting these data-sets using both your priority queue implementation (from Assignment 1) and the binary search tree. You may find it useful to read Section 2.6 – Performance Measurement – of your text to help you with this.

All of the above should be placed in an envelope with your name and student-ID on the outside, and submitted at the beginning of class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class – no late submissions will be accepted without documented reasons.