[Solved] DataStructure Homework5-AVL Trees

You are required to implement an AVL tree. An AVL is a special type of binary search tree that follows all the same rules: each node has 0-2 children, all data in the left subtree is less than the nodes data, and all data in the right subtree is greater than the nodes data. The AVL differs from the BST with its own self-balancing rotations, which you must implement.

All methods in the AVL tree that are not O(1) must be implemented recursively. Good recursion with simple, focused states is strongly encouraged for this assignment in particular.

Your AVL tree will have two constructors: a no-argument constructor (which should initialize an empty tree), and a constructor that takes in data to be added to the tree, and initializes the tree with this data. Balancing

Each node has two additional instance variables, height and balanceFactor. The height variable should represent the height of the node (recall that a nodes height is max(child nodes heights)+1. The balance factor of a node should be equal to its left childs height minus its right childs height. The tree should rotate appropriately to make sure its always balanced. Keep in mind that you will have to update these instance variables; they are not updated automatically.

BST to AVL

You are encouraged to use your BST code as a base to get started on this homework. The main changes will occur in the add and remove methods since thats where the structure of the tree can change. One notable change you should make besides the rotation logic is change the remove method to use the predecessor rather than the successor. This is not generally necessary in an AVL, but we thought itd be good practice. Another method to make changes to is the height method since its no longer necessary to recalculate the height of the tree since its already been stored. Weve also added a successor method that should get the successor of any data in the tree, not just in the two child case. This method is just for practice, and you should not be using it in any other methods.