CSE225 Data Structures Project 2-Solved

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. 
☺