Part I DUE Nov 17 in the lab, for demonstration and git-submit. The instructor will test and provide limited feedback on correctness.

Part II is DUE Nov 25, for submission via git.

In this lab, you are to alter an implementaton of the Dictionary ADT that uses a Binary Search Tree so that it balances as per AVL Tree operations -- i.e., a BST that balances by rotations to keep it in AVL-tree "balance" (no node has children whose height differs by more than one). Adapt the C++ files, header, and makefile files provided.


Part I is a Lab Demo of Working Subset I, to be demonstrated in the lab on Thursday November 17.

Also: submit the files via git.

Working Subset 1

1. The BST is to have the "Find" option enabled within testapp.cpp.
2. The fields BF and height are to be correctly maintained.
3. Two other options are to be offered in the testapp menu, LeftRotate and RightRotate. Upon entering "W" or "X", the user is to be prompted for a node to rotate left or rotate right, respectively. Rotating Left at a node v can only be done if there is a right child of the node; in that case the the right child of v becomes the child of v's parent in place of v, and v becomes the left child of v's former right child. A symmetric case holds for rightRotate.
   "Y" and "Z" are for testing your left-right and right-left double rotations, respectively. These two options are not required for the Working Subset 1, but will be incorporated into Working Subset 2

• A working AVL tree, with RightRotate and LeftRotate and both double rotations as part of the menu. All options (find, remove (extract), insert, debugprint) are to be working options from the testapp menu. Insert and Remove are now requried to use rotations to maintain balance, as per AVL tree algorithms.
• 
  
  To submit the files, use "git" to submit all the .cpp files and the makefile, and the header files.

  The project produces a link-based Binary Search Tree. A BST is ordered so that for any node in the tree, all the nodes in its left subtree have key value less than or equal to the key of the node, and all keys in the right subtree have key value greater than or equal to the key of the node. The subroutine stubs and header file provided are to be used as the base. You can alter them, and of course if there are bugs you can fix them.

  
  
  You can change testapp.cpp to test appropriately, but it must still be able to interface (i.e., link to) the original testapp.cpp file. Document your changes at the top of your testapp.cpp file in the comments -- i.e., keep a log there of the substantive changes to testapp.cpp



Document the code. The stubs provided are only minimally documented. Don't take them as a model. That said, your instructor is not making a point of grading your documentation per se in this assignment, but if she can't comprehend your code, then it goes badly for you when she assigns a grade to the work.

Everything but the data files and the makefile should bear your complete name and student number. Code should be well-documented and well designed.