share coding and error message at the end. Resolve Them

AVL Operations

For part two of this assignment, you will be coding theadd()andremove()methods of an AVL.Since trees are naturally recursive structures, each of these methods should beimplemented recursively.

IMPORTANT:

• You will begiven unlimited attempts on this assignment, withno cooldownbetween submissions.
• Please run your code before each submission to ensure that there are no formatting errors! If there are formatting errors in your code, your code will not be graded and a submission attempt will be logged. For more information, please review the Vocareum overview below.

AVLNode

An AVLNode class is provided to you and will be used to represent the nodes of the tree. This fileshould be treated asread-onlyand should not be modified in any way. This AVLNode class contains getter and setter methods to access and mutate the structure of the nodes. Please make sure that you understand how this class works, as interaction with this class is crucial for this assignment.

Pointer Reinforcement

Since both the add() and remove() methods may change the structure of the tree, we highly recommend that you use a technique called pointer reinforcement. Although using pointer reinforcement is not required, it will help to make your code cleaner, and it'll also help greatly in future assignments if you end up taking the next course in our series! Below is a video created by our 1332 TAs,timestamped to a section on pointer reinforcement.

Pointer Reinforcement Overview

Balancing

The tree should rotate appropriately to ensure that it is always balanced. A tree is balanced if every node's balance factor is either -1, 0, or 1. Keep in mind that you will have to update the balancing information stored in the nodes on the way back up the tree after modifying the tree; the variables are not updated automatically.

NOTE: If you have completed part one of this assignment, then you should simply copy and paste your code for updateHeightAndBF, rotateLeft, rotateRight, and balance, into this assignment. Note that you may have to toggle the method visibilities to private.

Comparable

As stated, the data in the AVL must implement the Comparable interface. As you'll see in the files, the generic typing has been specified to require that it implements theComparableinterface. You use the interface by making a method call likedata1.compareTo(data2). This will return anint, and the value tells you howdata1anddata2are in relation to each other.

• If the int ispositive, then data1 islargerthan data2.
• If the int isnegative, then data1 issmallerthan data2.
• If the int iszero, then data1equalsdata2.

Note that the returned value can beanyinteger in Java's int range,notjust -1, 0, 1.

Successor

Recall that earlier in the modules you learned about the successor and predecessor of a node in a tree. As a refresher, the successor of a node, n, is the node in the tree that contains the smallest data that is larger than n's data. The predecessor of a node, n, is the node in the tree that contains the largest data that is smaller than n's data. When removing a node from an AVL that has two children, we can choose to replace the removed node with either it's successor or predecessor. For the 2-child case in remove(), you will be replacing the removed node with itssuccessor node,NOTthe predecessor node. For more details, please refer to the javadocs for remove().

Helper Methods

You'll also notice that the public method stubs we've provided do not contain the parameters necessary for recursion to work, so these public methods should act as "wrapper methods" for you to use. You will have to write private recursive helper methods and call them in these wrapper methods. All of these helper methodsmust be private. To reiterate, donotchange the method headers for the provided methods.

Operation Examples: 2 0 7 1 4 8 0 3 6 2 add(5) 4 0 1 remove(3) 2 3 2 4 5 6 LO 5 7 1 3 6 1 4 6 5 8