This assignment has you writing another tree-based Map. Unlike the last one, this one will always be balanced because it will be an AVL tree. Most of the details of this assignment are the same as for the BST Map, so I'm not going to repeat them here. The main things are changing from that assignment are the following.
You will have code for rotations.
Write one function for rotate-left and one for rotate-right. Use the pseudocode in the book.
The fix-up function will call these appropriately when needed. You don't need to write double-rotation functions.
At the end of insert and remove, you will do a fix-up that starts at the lowest node changed and walks back up to the root.
This function must check for rotations and perform them if necessary.
It should also make sure that all heights are set properly on the path back up the tree.
I recommend having this function walk all the way to the root instead of trying to optimize it to stop partway.
I've added a treeHeight function to the public interface that I can use to verify your tree is the correct height.
In the case of a tie between grandchildren, do a single rotation.