Objective: In this lab assignment, you will implement either an AVL Tree or a Red-Black Tree and demonstrate its self-balancing properties, particularly its ability to perform rotations to maintain the balance.

Do not forget you are working with new groups.

Chosen Tree: AVL Tree Implementation:

Ensure your tree supports basic operations: insert, delete, and search. Implement the necessary rotations for your chosen tree: For AVL: leftRotate, rightRotate, leftrightRotate, and rightleftRotate

Demonstrate Rotations: Create a series of tests that cause your tree to become unbalanced and require different rotations using both insertions and deletion. Document the state of the tree before and after rotations. Visual representations or step-by-step explanations are encouraged.

Test your Implementation: Insert at least 10 elements into your tree. Delete at least 5 elements. Search for at least 5 elements. Ensure your tree remains balanced after each operation, demonstrating the rotations as required.

Submission: Submit Java code files for the implemented data structure. Submit javadoc and output screenshots. A diagram of your final tree.

Grading Rubric: Tree Implementation (6 Points):

Properly structured tree: 1 Point Successful insert method: 1.5 Points Successful delete method: 1.5 Points Successful search method: 1 Point Correct rotation implementation: 1 Point Demonstration and Testing (3 Points):

Clear demonstration of unbalance scenarios: 1 Point Clear demonstration of rotation results: 1 Point Comprehensive test cases: 1 Point Documentation and Diagram (1 Points)