Computer Science 269
Introduction to Data Structures
Fall 2000
Assignment 4 Due Tuesday, October 3, 2000
-
Implement the abstract data type, "AVL Tree." The items stored in
the nodes will have type integer.
-
You may not simply copy an AVL tree implementation available in the
textbook or elsewhere. Too much resemblence between your code and
that found in another source (including another student's code) will
be grounds for suspicion.
-
Your implementation should allow insertion and inorder traversal, but
not deletion. Your insertion method must permit the insertion of
duplicate data.
-
Use your implementation to write a program to sort an external file
of integers.
Run your program on each file using the AVL feature, but then run it
again without the AVL feature, i.e., do no rebalancing.
This way you see how much time rebalancing saves, or perhaps, costs.
-
Insertion Sort.
-
Initialize an AVL tree (or just binary search tree, if you are doing
the "no rebalancing" option) to empty.
-
Read the input file one item at a time, inserting each into
the tree.
-
Traverse the tree, writing each item into the output file.
-
Time Complexity Verification.
-
Declare two global counters, a data counter and a
complexity counter.
-
Increment the data counter every time you read a number from the input file.
-
Increment the complexity counter for each function call
and for each iteration of each loop.
-
Write a function that computes an integer approximation of
n log2n .
-
As part of your output, write the final value of the counter, and
write the ratio of the complextity counter value to your approximation of
n log2n,
where n is the final value of the data counter.
-
Be sure to run several files of different sizes.
-
Do your results support the statement that your program has
O(n log n) time complexity? Give an answer.
-
Write some English sentences discussing the merits of rebalancing.
-
You may write this portion of the assignment as a computer file and
then turn it in electronically.
But do not copy any part of it from anyone else -- it must be entirely
your own writing.
-
Submit to the Graduate Assistant by email.
-
In the subject line of the message, write "CSC 269 HW 4"
-
Include your source code as well as input and output files.
-
The deadline is October 3 at 5:30 PM. No late homework will be accepted.
-
You will receive results by email.
-
Here is a hint: create a function which tests whether the AVL condition
holds. This function should not cause the complexity counter to increment,
as it is not actually part of the algorithm. But it is helpful for you
to make sure that your algorithm has been properly implemented.