Comp 121 – Introduction to Data Structures

Comp 121 – Introduction to Data Structures. Spring 2000

Programming Assignment 4 -- Due April 25, 2000

Objective: To obtain experience in implementing the AVL algorithms.

Goal. To implement an AVL tree for storing integers.

As discussed in class, AVL search trees are binary search trees that satisfy an additional "balance" property. For this assignment, you are to implement (and test) an AVL search tree object for storing integers. Your AVL search tree object should support the following operations:

create( ) – creates an empty AVL search tree

destroy( ) – destroys an AVL search tree

insert(n) – insert the integer n into the AVL search tree

find(n) – return true if n is on the AVL search tree, or false otherwise

delete(n) – if the integer n is in the AVL search tree, then it should be "marked" as being absent. Note that you are not being asked to explicitly delete the node, but are merely required to mark it as being not there. Such an implementation of the delete operation is called a "lazy" delete.

height( ) – returns the height of the AVL search tree

inorderPrint( ) – visits all the nodes of the AVL search tree according to an inorder traversal, and prints out (value, height) ordered pairs of each node

preorderPrint( ) – visits all the nodes of the AVL search tree according to a preorder traversal, and prints out (value, height) ordered pairs of each node

Structure of the program:

Your program should be implemented across (at least) three files – a header file (".h") containing the specifications of the AVL search tree, a separate implementation (".cpp") file implementing the AVL operations, and a client file that does the testing.

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.

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.

Include a test plan detailing how you tested your ADT, and why you believe it is correct.

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.