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