Building a balanced BST (AVL) ADT

As we discussed earlier in the Building a binary search tree ADT section, it's possible to have a skewed tree (either left or right) and cause the time complexity of several operations to become slow for O(h), where h is the height of the tree. In this section, we are going to discuss a balanced binary search tree to ensure that we won't get a skewed tree. There are several implementations needed to create a balanced BST. However, we will only focus on the AVL tree, which was invented by Adelson-Velskii and Landis in 1962, and is named after the inventors.

To make a balanced BST, we have to know the height of each node in the tree. So, we need to modify the BSTNode class by adding a new property named Height, as follows:

class BSTNode
{
public:
    int Key;
    BSTNode * Left;
    BSTNode * Right;
    BSTNode * Parent;
int Height;
};

This new property is used to track the height of each node. We will also create a new method to fetch the height of a node, which...