C++ Data Structures and Algorithms

Inserting a new key

Inserting a new key into an AVL tree is similar to inserting a new key in a BST. The difference is that we need to check the balance of the inserted node and the parent nodes. As we discussed earlier, we have the formula to make a balanced tree by balancing the left and right nodes. After that, we can decide if we have to rotate it left or right. The implementation of the Insert() operation in an AVL tree is as follows:

BSTNode * AVL::Insert(BSTNode * node, int key){    // If AVL tree doesn't exist    // create a new node as root    // or it's reached when    // there's no any child node    // so we can insert a new node here    if (node == NULL)    {        node = new BSTNode;        node->Key = key;        node->Left = NULL;        node->Right = NULL; node->Parent ...