HW 6 AVL Tree Implementation
The AVL tree implementation provided in the text (and posted on piazza) is missing two rotation methods: rotateWithRightChild (AvlNode k2) – a single rotation required because k2 is out of balance due to an insertion of a new node into the right subtree of k2’s right child. Note, Weiss did the other single routine for us, rotateWithLightChild, which is shown on page 135 doubleWithRightChild (AvlNode k3) a double rotation required when k3 is out of balance due to the insertion of a new node into the left subtree of k3’s right child. Note, Weiss did the other double rotation for us, doubleWithLeftChild is on page 136. 1. Implement rotateWithRightChild, modeling your code after that provided (pages listed above). 2. Implement doubleWithRightChild, modeling your code after that provided (pages listed above). 3. Implement a more efficient version of doubleWithRightChild without the inefficiency of doing two single rotations – that is, write code that does not call other methods of single-‐rotation methods. Make sure that the code that you submit contains both doubleWithRightChild methods, just have one commented out when you submit. For your testing purposes, comment out whichever one you are not testing. Include a test driver that shows that calls the methods.
