Project 4: Balanced tree-based encryption and decryption

You will receive 100% for turning this project in and passing the functionality test and style check before the deadline. After the deadline is 25% off.

Total points: 90

Before you start this project, you should have read the project submission guidelines and the coding style rules.

After that, get started on the project immediately! You will submit your solution to the new submission site.

---

Project Description

The goals of this project are to:

• Implement an advanced ordered data structure,
• Implement an AVL tree,
• Implement advanced algorithms with constant, linear, logarithmic, and log-linear running times,
• Practice the use of data abstraction,
• Practice coding a basic encryption algorithm,
• Test your program in the command line environment with input/output redirection and diff utilities, and
• Get you familiar with the new submission site for project uploads

This project is just like Project 3, but instead of using a regular binary search tree, we will use an AVL-balanced 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 C++ files provided here. I have provided a lot of code in this files. You are not allowed to change the existing code in this files. Instead, 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-tree-student-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 the correct solution. Here are the compiled solutions:

• 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 will not be turned in nor graded, however, I strongly recommend that you do them for your own good and at the suggested pace. There is no milestone 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.

Step	Finish by	Milestone
1.	Monday w.a.p.	WRITE and TEST all the rotation, insert, and rebalancePathToRoot methods in the AVLNode class.
2.	Monday t.w.a.p.	WRITE and TEST the AVLTree remove and printLevelOrder methods.

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.