Cosc 2P03 Fall 2011
Assignment#3
(Due date for assignment --> Tuesday November.15th
noon., Late date Friday November. 18th, noon)
Part A [75% weight]
For this assignment part, you will be exploring AVL trees, insertion
and deletion.
Consider a Node class with the following fields, left, right,
height, data (String). You may add more but that is the basic data
you will need. Write a program which puts up the following GUI on
the screen. Feel free to use Basic Forms or any other Java platform.
- Load Tree - Will build a new AVL tree from a specified
file. Contents of the file is to be strings. Feel free to use
same input as in A2.
- Insert - Will Prompt to insert a new string value into the AVL
tree.
- Delete - Will Prompt to delete a node from the AVL tree,
maintaining AVL conformity.
- Print - Will dump out the tree to some output device.
Displayer.
- isBST - Will return a boolean check to ensure that the tree is
still BST.
- isAVL - Will run a quick check to ensure the tree is still AVL
Note: 4, 5, and 6 are used for debugging and verification - that
your tree is proper. These should be some of the first routines you
write. Further, the isBST code as described in class has a serious
flaw (as pointed out by one of your fellow students). Without
getting into details, consider implementing it as a SOT which keeps
checking the current visit with the previous visit. If you wish you
can combine 4,5 and 6 into 1 command.
Some suggestions:
Use the AVL code given in class. You will need to implement the
deletion on your own, using the recursive BST deletion code and
inserting counter AVL rotations where appropriate.
Part B [25% weight]
Implement a HeapSort on a randomly generated set of numbers, say
less then 25, in a range 0-99.
For output print the unsorted numbers and then the sorted result.
Submission Requirements:
- Cover Sheet completely filled out, available
from: "http://www.cosc.brocku.ca/coverpage"
Note: your assignment will not be marked unless one is submitted
with the assignment on the assignment due date.
- Commented and properly documented source code
listing.
- Listing of any input you used to test your program.
- Listing of your output. Be sure to adequately show that the
input, operations and output show the marker that your program
is working. Don't be afraid to tell the marking if something is
not working correctly.
- Source code is to be Java.
- Disk, CD containing source, input, output and executables.
- Electronic submission, run the script "submit2p03" from
sandcastle.
- Statement on coversheet with following information.
- Platform, e.g. Mac PP6100, PC, Commodor 64, my Java enabled
wrist watch.
- Compiler Version, e.g. Java 1.5, Java 1.6 e.g.
Good Luck