How to fix segmentation fault in AVL deletion operation when rebalancing?

Question

I am implementing an AVL tree and my search and insertion functions work properly, but I get a segmentation fault with my remove function. I have implemented a BST tree correctly before, so I know the issue is with the rebalancing of the tree rather than the initial deletion of a node.

Since my insertion operation works with the rebalancing, I also know the issue is not with the rotation functions themselves.

I have tried different strategies such as maintaining a balance factor at each node and have tried implementing other source code I have found online but I always end up with a segmentation fault and really cannot find where. I'd appreciate any help.

class AVL
{
public:
    AVL();

    Node* insert(int num);
    Node* search(int num);
    Node* remove(int num);
    void print();
    void comparisonPrint();

private:
    int comparisonCount;
    Node* root;
    int max(int a, int b);
    int getHeight(Node* t);
    int getBalance(Node* t);
    Node* insert(Node* &t, int num);
    Node* rotateWithLeftChild(Node* t);
    Node* rotateWithRightChild(Node* t);
    Node* doubleRotateWithLeftChild(Node* t);
    Node* doubleRotateWithRightChild(Node* t);

    Node* search(Node* t, int num);
    Node* removeMin(Node* parent, Node* node);
    Node* remove(Node* &t, int num);
    void print(Node* t);
    //print
};

int AVL::max(int a, int b)
{
    return (a > b)? a : b;
}
int AVL::getHeight(Node* t)
{
    return (t == NULL) ? 0 : t->height;
}
int AVL::getBalance(Node* t)
{
    if(t == NULL)
        return 0;
    return getHeight(t->leftChild) - getHeight(t->rightChild);
}

//helper function for remove - finds min
Node* AVL::removeMin(Node* parent, Node* node) //removes node, but does not delete - returns ptr instead
{
    if(node != NULL)
    {
        if(node->leftChild != NULL) //go to leftmost child in right subtree
            return removeMin(node, node->leftChild);
        else //min val
        {
            parent->leftChild = node->rightChild;
            return node;
        }
    }
    else //subtree empty - incorrect use of function
        return NULL;
}

Node* AVL::remove(Node* &t, int num)
{
    cout << num;
    if(t != NULL)
    {

        if(num > t->key)
        {
            comparisonCount++;
            remove(t->rightChild, num);
        }
        else if(num < t->key)
        {
            comparisonCount++;
            remove(t->leftChild, num);
        }
        else if(t->leftChild != NULL && t->rightChild != NULL)
        {
            comparisonCount++;
            //2 children
            Node* minRightSubtree = removeMin(t, t->rightChild);
            t->key = minRightSubtree->key;
            delete minRightSubtree;
        }
        else
        {
            comparisonCount++;
            //0 or 1 child
            Node* temp = t;
            if(t->leftChild != NULL)
                t = t->leftChild;
            else if(t->rightChild != NULL)
                t = t->rightChild;
            delete temp;
        }

        //update height
        t->height = max(getHeight(t->leftChild), getHeight(t->rightChild)) + 1;

        int balance = getBalance(t);

        if(balance > 1 && getBalance(t->leftChild) >= 0)
            return rotateWithRightChild(t);
        if(balance > 1 && getBalance(t->leftChild) < 0)
        {
            t->leftChild = rotateWithLeftChild(t->leftChild);
            return rotateWithRightChild(t);
        }
        if(balance < -1 && getBalance(t->rightChild) <= 0)
            return rotateWithLeftChild(t);
        if(balance < -1 && getBalance(t->rightChild) > 0)
        {
            t->rightChild = rotateWithRightChild(t->rightChild);
            return rotateWithLeftChild(t); 
        }

    }

    return t;
}

So I need the remove function to remove a specified node and rebalance the tree when necessary using the appropriate rotations. However, I keep getting a segmentation fault whenever I try to call the function in my main. Thanks.

Answer 1

There are two problems with your code. First is the removeMin function and the else if part in remove function when the node to be deleted has two children.

Basic aim of the removeMin function should be to find the inorder successor of the node to be deleted which is t in your case. Consider the case when t has 2 children (both leaf nodes) then your removeMin function will set t->leftChild as t->rightChild->rightChild which is NULL which is wrong. Also the restructuring of the tree should be done inside remove hence removeMin becomes:

Node* AVL::removeMin(Node* node) // returns inorder successor of 't'
{
    if(node->left == NULL)
        return node;
    return removeMin(node->left);
}

Coming to remove function, we reset t->key with minRightSubtree->key and the node to be deleted now is minRightSubtree. But notice that the order of keys has changed in the chain from node t till node minRightSubtree. t->key is less than all the keys of nodes till before minRightSubtree. Hence you cannot just delete minRightSubtree, you have to call remove function on the node minRightSubtree which will take care of restructuring this chain. Also you can get a little help from the recursion stack to get the correct child for the current node t after deletion/rotation:

Node* AVL::remove(Node* &t, int num)
{
    if (t == NULL)
        return NULL;

    if (num > t->key)
        t->rightChild = remove(t->rightChild, num);
    else if (num < t->key)
        t->leftChild = remove(t->leftChild, num);
    else if (t->leftChild != NULL && t->rightChild != NULL)
    {
        //2 children
        Node* minRightSubtree = removeMin(t->rightChild);
        t->key = minRightSubtree->key;
        t->rightChild = remove(t->rightChild, minRightSubtree->key);
    }
    else
    {
        //0 or 1 child
        Node* temp = t;
        if (t->leftChild != NULL)
            t = t->leftChild;
        else if (t->rightChild != NULL)
            t = t->rightChild;

        if(temp == t)
            t = NULL;
        delete temp;
    }

    if (t == NULL)          // this case was added since there is a possibility of deleting 't'
        return NULL;

    //update height
    t->height = max(getHeight(t->leftChild), getHeight(t->rightChild)) + 1;

    int balance = getBalance(t);

    if (balance > 1 && getBalance(t->leftChild) >= 0)
        return rotateWithRightChild(t);
    if (balance > 1 && getBalance(t->leftChild) < 0)
    {
        t->leftChild = rotateWithLeftChild(t->leftChild);
        return rotateWithRightChild(t);
    }
    if (balance < -1 && getBalance(t->rightChild) <= 0)
        return rotateWithLeftChild(t);
    if (balance < -1 && getBalance(t->rightChild) > 0)
    {
        t->rightChild = rotateWithRightChild(t->rightChild);
        return rotateWithLeftChild(t);
    }
    return t;
}

I'm assuming your code for updating heights and balancing the rooted sub-tree is correct since I've forgotten about it's theory and will need to revise.