Description
Project description
This project is just like Project 3, but instead of using a regular binary search tree, we will use an AVLbalanced binary search tree. This change will make this new project different in several ways:
• each tree node must retain height information
• we must implement node rotation
• insert and remove functions must rebalance the tree when necessary
• the encryption cipher may change whenever we insert or remove something (since the tree paths
change when rotations happen)
• the AVL tree will support level-order traversal in addition to preorder traversal (the command for
printing pre-order will still be ‘p’, and the command for printing level-order will be ‘l’ — lower-case L).
Otherwise, this project is identical to the previous project in terms of input and output specifications.
Sample inputs
Several sample inputs are available here. You can get the correct output by capturing the output of the
sample executable on these inputs.
• input 1
• input 2
Provided code
You must use the .h files provided here. I have provided a lot of code for you in the ‘prof’ file. You are not
allowed to change the code in these files. Instead, you will write your code in and submit the ‘student’ file.
• avl-tree-prof-proj4.h
• avl-tree-student-proj4.h
Remember that when using templates, all of the code you write goes in the .h file. So you will turn in 2
files for this project: avl-tree-student-proj4.h and driver-proj4.cpp. Your driver should #include “avl-treestudent-proj4.h”, and that file should #include “avl-tree-prof-proj4.h” (which it already does).
Sample executables
Here are sample executables for you. When you design test cases, you can judge your output against the
output from my correct solution.
• DOS executable
• Linux (Intel) executable
• MacOSX (Universal) executable
If you give a command-line argument to these executables, they will print extra information about how
they are exploring. For example, this will execute the program like normal, redirecting input from a file
called my_input.txt:
% project4_solution_dos.exe < my_input.txt
But here is the mode of operation that will cause the program to print out what it is doing in more detail:
% project4_solution_dos.exe printMore < my_input.txt
The command-line argument doesn't have to be the word "printMore", it can be anything.
Structuring the project
Since this is a large project, it helps to have a plan of attack. The following milestones should be turned in
via the upload site. There's no milestone requirements for the driver, EncryptionTree, or methods that are
just like they were in the BST, since they should be almost the same as that for project 3.
Use your book. Your book has code for writing an AVL-balanced binary search tree, but your code will be
fairly different, since the book uses recursion but your code will mostly not use recursion. However, you
should read and understand the code in the book first.
Final notes
Remember when writing this program to adhere to the coding style guidelines. This is an individual
project, so you must work alone. No credit will be given for a solution which does not pass all the hidden
tests I create, or does not pass in the allowed time. For more detailed instructions, read the project
submission guidelines.
Copyright © 2016 Greg Hamerly.
Computer Science Department
Baylor University
valid html and css
Step Finish by Milestone
1 Monday, October 16 at noon WRITE and TEST all the rotation, insert, and
rebalancePathToRoot methods in the AVLNode class.
2 Thursday, October 19 at noon WRITE and TEST the AVLTree remove and printLevelOrder
methods.
