As we have seen in class, AVL trees are excellent for search given their height of log2nlog_2{n}log2n or log2n+1log_2{n} + 1log2n+1. Unfortunately, to achieve this efficient search, they have to use rotations during insertions and deletions, and those take time!
In this project, you will implement AVL-G trees, a simple modification of AVL Trees that allows for tuning the balance of an AVL Tree based on a constructor parameter. Simply put, an AVL-G tree, where G=1,2,3,,G = 1, 2, 3, ldots,G=1,2,3,, allows for any given subtree to have a balance of at most G. This means that our classic AVL trees can be referred to as AVL-1 trees.