Как исправить ошибку сегментации в операции удаления AVL при балансировке?

Question

Я реализую дерево AVL, и мои функции поиска и вставки работают правильно, но я получаю ошибку сегментации с моей функцией удаления. Ранее я правильно реализовал дерево BST, поэтому я знаю, что проблема связана с перебалансировкой дерева, а не с первоначальным удалением узла.

Поскольку моя операция вставки работает с перебалансировкой, я также знаю проблемуне с самими функциями ротации.

Я пробовал разные стратегии, такие как поддержание коэффициента баланса на каждом узле, и пытался реализовать другой исходный код, который я нашел в Интернете, но я всегда заканчиваю с ошибкой сегментации и действительноне могу найти где. Буду признателен за любую помощь.

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;
}

Поэтому мне нужна функция удаления, чтобы удалить указанный узел и при необходимости перебалансировать дерево, используя соответствующие повороты. Тем не менее, я продолжаю получать ошибку сегментации всякий раз, когда пытаюсь вызвать функцию в моем main. Спасибо.

Answer 1

Есть две проблемы с вашим кодом. Во-первых, это функция removeMin и часть else if в функции remove, когда удаляемый узел имеет двух дочерних элементов.

Основная цель функции removeMin должна состоять в том, чтобы найти преемника по порядку следованияудаляемый узел, который в вашем случае равен t. Рассмотрим случай, когда t имеет 2 дочерних элементов (оба конечных узла), тогда ваша функция removeMin установит t->leftChild как t->rightChild->rightChild, что является NULL, что неверно. Также реструктуризация дерева должна быть сделана внутри remove, поэтому removeMin становится:

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

При переходе к функции remove мы сбрасываем t->key с помощью minRightSubtree->key и удаляемый узелсейчас minRightSubtree. Но обратите внимание, что порядок ключей в цепочке изменился с узла t до узла minRightSubtree. t->key меньше, чем все ключи узлов до minRightSubtree. Следовательно, вы не можете просто delete minRightSubtree, вам нужно вызвать remove функцию на узле minRightSubtree, которая позаботится о реструктуризации этой цепочки. Также вы можете получить небольшую помощь от стека рекурсии, чтобы получить правильный дочерний элемент для текущего узла t после удаления / поворота:

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;
}

Я предполагаю, что ваш код для обновления высоты и балансировки корневыхподдерево верное, так как я забыл о его теории и должен будет пересмотреть.