C++ Data Structures and Algorithms

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 ...