| This project has been viewed 833
times and was posted by risik09 from Yemen. |
|
| Start date : 03 Jul. 2008, 18:52 |
End date :17 Jul. 2008, 18:52 |
There is 1 registered bid. |
| Project number : 251746 |
Project category:Engineering |
| This project owner has posted 2 projects on Projects Pool and selected winners for 1 of them. |
Description :
CS352 SS08 Project 2: AVL Tree
Due date: July 24, 2008, 11:59pm, Central time.
Purpose: Practice the implementation and maintenance of AVL tree. Help to understand binary search tree and the balance property of AVL tree.
Description:
1. Write a program generate an AVL tree according to the input parameters (number of nodes and node values). Your program can either accept these parameters from command line or text file. Your program should be general, that is, it should be able to generate an AVL tree with any number of nodes and corresponding values. However, for your convenience, you can assume these nodes only store integers. Once you have generated the tree then print it. This is your initial tree.
2. Then your program should provide a menu which includes at least three options: Insertion, Deletion, and Quit.
3. Insertion: a. Insert a node with a value which is selected randomly. That means you should accept an input from the user for the value to be inserted. It is important to select the value randomly so that your program will identify where the node must go on the tree and add it there. Print this tree.
b. Check if the resulting tree violates AVL condition. If it is then identify what type of rotation (single or double) is required to balance the tree. Print out the rotation you perform to make the tree a legal AVL tree. Print it the balanced tree.
4. Deletion: Select randomly a node to delete. Same requirements as that for insertion.
5. Run time testing: Your program should be able to build a big tree with a given size and randomly generated numbers (using some C++ function). You don’t need to print out such tree. But you need to print out the run time after some searching, insertion or deletion operations.
What to submit?
1. Source code which could be compiled without errors.
2. An exe file which can be run on Windows or Linux.
3. A sample result of an input which includes one insertion and one deletion.
Grading criteria:
1. A project with the program failing to compile earns at most 30%.
2. For successfully compiled program:
a. Source code (well commented): 60%
b. Correct and well formatted result: 30%
c. Sample result: 10%
|
Support :
|
