CMSC 3613 Programming Assignment: AVL Tree Implementation and Deletion

This programming assignment for CMSC 3613 requires the implementation of an AVL tree in C++. The primary tasks involve implementing the `rotate_right()` and `left_balance()` functions, paying close attention to balance factors and the `longer` boolean value. The program's input will be a series of insert and delete operations from a data file, and the output must be a pre-order traversal of the tree. Extra credit is awarded for implementing the `avl_delete()` function. Students must create a folder named "p04" on their Linux server account, place their source code in this folder, and submit a report including their name, email, project details, implementation discussion, a test run screenshot, and source code. The program is evaluated based on the correctness of the tree methods and the quality of the code. The rubric includes points for `rotate_right`, `left_balance`, `avl_delete`, and a report.

CMSC 3613
Programming Assignment: AVL Tree
Due Date: Check the D2L calendar for the due date.
Assignment:
The task of this project is to implement the rotate_right() and left_balance() functions in the
provided program framework. Those two functions are marked as “TODO” in the comments inside
the file avl_tree.h. Please follow the program structures of rotate_left() and right_balance()
functions and make necessary modifications.
Please pay special attention to the balance factor for each node and the bool value longer.
The format of the input file (e.g. input1.dat) will be similar as:
{insert and delete will be followed by an integer in the next line. Leading or tailing spaces are
not handled, if you want to make it perfect, you can follow the utilities in p01.}
The format of the output will be similar as:
{This is a pre order traversal. In each line, the format is “root_value: left_value right_value”, in‐
which the value of a null child node is replaced by a dash.}
insert
80
insert
90
insert
100
insert
110
insert
95
insert
120
insert
92
insert
97
insert
70
insert
93
delete
100
delete
80
delete
120
delete
97
++++++++++++++++++++++
92: 90 95
90: 70 -
95: 93 110
++++++++++++++++++++++

Extra credits (extra 40%):
Implement the avl_delete() function, which is marked as “TODO 3” in the file avl_tree.h.
Hints:
1. Deleting a node on a binary search tree is recursively solved, so it’s similar for avl_delete().
The program structures will be very similar.
2. Be careful about the balance factor for each node and the bool value shorter. You can find
detailed discussion in the textbook about how to remove a node from an AVL tree, please
reference the contents on page 484 - 486.
Requirements:
1. Your program should follow the instructions described above in the “Assignment” section.
2. Use C++ language for implementation. The output has been readily defined, please don’t
change that part.
3. The files in command line argument should be similar as follows:
sz0**@CS:~$ ~/p04/p04 input1.dat
the first p04 is the folder contains the project source code, and the second p04 should be
the name of your executable (p04 should be a fixed name!), and input1.dat is the name of
the input file (the name can be any).
Evaluation:
This project will be evaluated according to the correctness of the various tree methods specified
above, and secondarily according to the quality of your code. The rubric is as follows:
Categories Weights
rotate_right 30%
left_balance 60%
avl_delete 40% (bonus)
report 10%
Submission:
1. You need to create a folder named “p04” directly under your Linux server account (i.e.,
its path should be /home/sz/sz0**/p04/). All source code should be put into this folder.
The code should NOT be modified after the due date. Altered code will be considered
late.
o Make sure that the instructor be able to use make to compile and build the program
and run it.
o After complication, the name of your executable file should be p04, such that it can
be invoked by the following command on the server:
sz0**@CS:~$ ~/p04/p04 input1.dat
2. You need to submit a report by the due date on D2L. The report should include the
following items:
1) Your name and UCO email address
2) The project number, i.e., p04
3) Your server username where the course code is hosted for your group
o Do not submit the password!

4) A brief discussion of your implementation: just like an explanation of your idea in an
interview.
5) A screenshot of a test run.
6) Also copy all your source code on D2L (not images, but text contents).
Notes:
1. To be considered on time, the program must be turned in by the due date.
2. Programs must reflect your knowledge and work, not others. You may ask others
questions about algorithms, methods and programming style, but when you start writing
code, you must work only with your group member(s).
3. No point, zero (0), will be given to any program containing compilation errors.