Lab 3

Warning

To compile you should use a CMakeLists.txt. It takes sometimes to get use to it, but it makes the compilation much easier.

AVL - Start

  1. Download the header file of the class AvlTree header

  2. Implement each method of the class in a file AvlTree.cpp.

  3. Download the test file of the class main.

  4. Test your class. Make sure everything works.

AVL - Template

  1. Import the classes Rectangle and Position like in the previous lab (the comparison on the area).

  2. Create different rectangles (position and size), at least 15, and insert them in an AVL Tree.

  3. Print the tree and ensure that the tree:

    • Contains all the rectangles

    • Have the rectangle ordered by the area

    • The tree is balanced

  4. Try to remove some rectangle.

    • Make sure that the tree is still ordered.

    • Make sure that the tree is still balanced.

    • Do try to remove a rectangle that would make the rectangle unbalanced.

  5. Modify the operators operator<, operator> operator== to compare the rectangle with the position.

  6. Redo the steps from 1 to 4. Make sure everything is working.

AVL - Advanced

  1. Write the functions to perform the double rotation without the inefficiency of doing two single rotations. Make sure that it is working by comparing the two methods.

  2. Write a nonrecursive function to insert into an AVL tree.

LeetCode

If you are done, you can start doing the following problems on LeetCode: