Gator AVL

First Data Structure & Algorithm Project

C++

Maxmilian Pennisi

3/1/2024

This was the first project assigned to us in Data Structures & Algorithms in my Fall Sophomore semester at UF. On my first attempt I failed 1 out of 15 hidden test cases, but could later resubmit and was able to pass all the test cases for this project.

An AVL is a binary tree that is self balancing, thus the worst time complexity for a search is O(logn) because the height of each subtree only differs by one creating a balanced tree that prevents skewed trees that could take O(n) time. The self balancing properties come from four different types rotations that occur upon insertion of a new node.

I learned a lot from this project, it took a lot of time but it was one of my favorites. I learned a lot about the rotations which was tricky to figure it out. Same with removing nodes as it was a lot of recursion and pointer work to get the right nodes to point to each other.

This was the first project I completed that used Unit Test. It was required to write 5 unit tests and test all the functions and also input validation commands. Checking for edge cases and verifying that our AVL tree would have the correct structure and positioning of certain nodes. We used the Catch2 module in C++ to do this.

First time handling complex inputs through console. The user was allowed to type in the console an insert, delete, search, and print commands and then whatever arguments the function needed (User did not have access to the direct function but instead a helper function that would then call the function that dealt with memory and pointers). It was not too difficult but it was definitely the first time I had to tokenize a string and check based on the current token whats the value and what arguments/token should come after that.

The source code is on Github but the repo is private due to plagiarism concerns of other students. Please reach out and I would be happy to add you to the repo to take a look. :)