In this project, you are required to write a program to compare the performance of AVL and Splay trees
based on the two criteria: the total number of comparisons and the number of rotations.
You will be given a text file as input, and your program will read the characters in the text and insert the
non-existing ones as keys in the corresponding tree (AVL or Splay) or otherwise (i.e., if existent) find them and
update their occurrence frequency in the text. For the AVL tree, if there is an AVL condition violation after
inserting the new node, you will employ the proper rotation and make the tree AVL. For the splay tree, you will
make the necessary splay(s) after reading each character in the text.
The number of comparisons will be considered for both the successful and the unsuccessful searches
(i.e., insertions). The number of rotations in AVL trees will be considered only when there is a need for rotation.
A single rotation in AVL trees costs one time unit (tu) (which is equal to the cost of the comparison of two
keys), while a double rotation costs two tus. A splay in splay trees costs as many tus as the number of depth
levels the nodes have moved through. In Splay trees, on the other hand, there will be rotation(s) after reading
each character from the text (remember Splay trees!).
The output of your program will be:
the total cost (= the cost component from the comparisons + the cost component from the
rotations) of the construction and search within
both trees.
In this project you are expected to develop an algorithm that is capable of finding a solution to the above
problem and implement this algorithm in ANSI C that runs under UNIX.
You are responsible for demonstrating your program to your TA Mehmet Kaya on the scheduled day
that will be announced later.
By the due date you are to electronically submit (to canvas) the source code of your program (file
name: YourStudentID_Prj2.c)
Note that projects submitted after the project’s due date will be deducted 5 points each day they are
late (until 5 days). After 5 days following the due date, no project will be accepted and evaluated. Please keep
this in mind and promptly start working on your projects!
You are required to exhibit an individual effort on this project. Any potential violation of this rule will
lead everyone involved to failing from all projects and necessary disciplinary actions will be taken.
☺
