C++ Data Structures and Algorithms

Removing a given key

Removing a key in an AVL tree is also the same as removing a key in a BST. We also need to check the balance after removing the key. Here is the implementation of the Remove() operation in the AVL class, which has been updated with balance checking:

BSTNode * AVL::Remove(BSTNode * node, int key){    // The given node is    // not found in AVL tree    if (node == NULL)        return NULL;    // Target node is found    if (node->Key == key)    {        // If the node is a leaf node        // The node can be safely removed        if (node->Left == NULL && node->Right == NULL)            node = NULL;        // The node have only one child at right        else if (node->Left == NULL && node->Right != NULL)        {            // The only child will be connected to            // the parent's of node directly node->Right->Parent ...