c - AVL 树删除导致程序崩溃

Question

所以我有一个 C 语言的二叉搜索树代码，对我来说效果很好。但是，当我添加 BST 删除代码时，我的程序将在删除过程中崩溃。

它给我一个错误，提示访问冲突读取位置 0x00000000。

我认为这与传递 NULL 指针或其他东西有关。也许我在某处读到过，或者那是完全错误的，我很傻。

无论如何，这是我的 AVL 删除代码。如果您能帮助我让我的程序正常运行并帮助我理解我做错了什么，我将非常感激。我还将包括查找最小节点的函数，因为我觉得它可能是罪魁祸首。

AVL min_node(AVL self)
{
    /*  A AVL node to keep track of the current node. */
    AVL current = self;


    /*  This loop finds the minimum node, by traversing the tree until the leftmost node is discovered. */
    while (!empty_tree(current))
    {
        current = current->left;
    }

    /*  Returns the tree.   */
    return current;
}



AVL delete(AVL self, long id)
{

    if (self != NULL)
    {
        if (id == self->student_id)
        {
            if (self->left != NULL)
            {
                AVL successor = min_node(self->right);
                self->student_id = successor->student_id;
                self->right = delete(self->right, self->student_id);
            }
            else
            {
                AVL to_free = self;
                if (self->left)
                {
                    self = self->left;
                }
                else
                {
                    self = self->right;
                }
                free(to_free);
            }
        }
        else if (id < self->student_id)
        {
            self->left = delete(self->left, id);
        }
        else
        {
            self->right = delete(self->right, id);
        }
    }

    /*NEW SHIT*/
    int balance = getBalance(self);

    //Left Left Case
    if (balance > 1 && getBalance(self->left) >= 0)
    {
        return rotateRight(self);
    }
    //Left Right Case
    if (balance > 1 && getBalance(self->left) < 0)
    {
        self->left = leftRotate(self->left);
        return rotateRight(self);
    }
    //Right Right Case
    if (balance < -1 && getBalance(self->right) <= 0)
    {
        return leftRotate(self);
    }
    //Right Left Case
    if (balance < -1 && getBalance(self->right) > 0)
    {
        self->right = rotateRight(self->right);
        return leftRotate(self);
    }

    return self;
}

更新:所以它似乎在删除函数中的两行之一崩溃:

self->student_id = successor->student_id;

或者

AVL successor = min_node(self->right);

编辑 2:根据要求，我已经包含了整个 avl.c 文件。

#include <stdlib.h>
#include <stdbool.h>
#include "avl.h"

bool names_match(char* name_one, char* name_two)
{
    if (strcmp(name_one, name_two) == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool empty_tree(AVL self)
{
    if (self == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}


AVL leftRotate(AVL self)
{
    AVL y = self->right;
    AVL T2 = y->left;

    y->left = self;
    self->right = T2;

    return y;
}

AVL rotateRight(AVL self)
{
    AVL x = self->left;
    AVL T2 = x->right;

    x->right = self;
    self->left = T2;

    return x;
}

int getBalance(AVL node)
{
    if (node == NULL)
    {
        return 0;
    }
    return height(node->left) - height(node->right);
}


AVL insert(AVL self, long id)
{
    if (self == NULL)
    {
        self = (AVL)malloc(sizeof(struct avlNode));
        self->student_id = id;
        self->left = self->right = NULL;
    }
    else if (id < self->student_id)
    {
        self->left = insert(self->left, id);
    }
    else if (id > self->student_id)
    {
        self->right = insert(self->right, id);
    }


    /*NEW SHIT*/
    int balance = getBalance(self);

    //Left Left Case
    if (balance > 1 && id < self->left->student_id)
    {
        return rotateRight(self);
    }
    //Right Right Case
    if (balance < -1 && id > self->right->student_id)
    {
        return leftRotate(self);
    }
    //Left Right Case
    if (balance > 1 && id > self->left->student_id)
    {
        self->left = leftRotate(self->left);
        return rotateRight(self);
    }
    //Right Left Case
    if (balance < -1 && id < self->right->student_id)
    {
        self->right = rotateRight(self->right);
        return leftRotate(self);
    }

    //Return unchanged pointer (i dunno why. could probably be void)
    return self;
}

/*  === AVL MINIMUM NODE ===
Finds the minimum node in a AVL.
*/
AVL min_node(AVL self)
{
    /*  A AVL node to keep track of the current node. */
    AVL current = self;

    /*  This loop finds the minimum node, by traversing the tree until the leftmost node is discovered. */
    while (!empty_tree(current->left))
    {
        current = current->left;
    }

    /*  Returns the tree.   */
    return current;
}



AVL delete(AVL self, long id)
{
    if (self != NULL)
    {
        if (id == self->student_id)
        {
            if (self->left != NULL)
            {
                AVL successor = min_node(self->right);
                self->student_id = successor->student_id;
                self->right = delete(self->right, self->student_id);
            }
            else
            {
                AVL to_free = self;
                if (self->left)
                {
                    self = self->left;
                }
                else
                {
                    self = self->right;
                }
                free(to_free);
            }
        }
        else if (id < self->student_id)
        {
            self->left = delete(self->left, id);
        }
        else
        {
            self->right = delete(self->right, id);
        }
    }

    /*NEW SHIT*/
    if (self == NULL)
    {
        return self; //ADDED TODAY
    }

    int balance = getBalance(self);

    //Left Left Case
    if (balance > 1 && getBalance(self->left) >= 0)
    {
        return rotateRight(self);
    }
    //Left Right Case
    if (balance > 1 && getBalance(self->left) < 0)
    {
        self->left = leftRotate(self->left);
        return rotateRight(self);
    }
    //Right Right Case
    if (balance < -1 && getBalance(self->right) <= 0)
    {
        return leftRotate(self);
    }
    //Right Left Case
    if (balance < -1 && getBalance(self->right) > 0)
    {
        self->right = rotateRight(self->right);
        return leftRotate(self);
    }

    return self;
}

/*  === AVL NODE COUNT ===
Counts the number of nodes in the AVL.
*/
int number_of_nodes(AVL self)
{
    /*  If the tree is empty, return a count of 0 nodes.    */
    if (empty_tree(self))
    {
        return(0);
    }
    /*  If the tree is not empty, but its left and right nodes are, return a count of 1 node.   */
    else if (empty_tree(self->left) && empty_tree(self->right))
    {
        return(1);
    }

    /*  If the tree is not empty, and its left and right nodes are also not empty, run this function recursively in the left and right nodes.   */
    else
    {
        return(1 + (number_of_nodes(self->left) + number_of_nodes(self->right)));
    }

}

/*  === AVL HEIGHT ===
Returns the total height of a AVL.
*/
int height(AVL self)
{
    /*  If the tree is empty, return a count of 0 nodes.    */
    if (empty_tree(self))
    {
        return 0;
    }
    /*  If the tree is not empty, run this fucntion recursively on the left and right branches, returning the max of the two.   */
    else
    {
        return 1 + max(height(self->left), height(self->right));
    }
}



/*  === PRINT AVL ===
Prints a AVL in pre-order.
*/
void print_pre_order(AVL self)
{

    /*  If the tree isn't empty, print the node's ID and then run this function recursively on the left and then the right nodes,
    to print pre order. */
    if (!empty_tree(self))
    {
        printf("%d", self->student_id);
        printf("\n");
        print_pre_order(self->left);
        print_pre_order(self->right);

    }
}

/*  === SEARCH AVL ===
Searches a AVL for a particular node.
*/
bool searchTree(AVL self, long id)
{
    if (!empty_tree(self))
    {
        /*  If the node's ID matches the input ID, return true. */
        if (self->student_id == id)
        {
            return true;
        }

        /*  If the node's ID doesn't match the input ID, run this function recurseively on the appropriate node.    */
        else
        {
            if (self->student_id > id)
            {
                return searchTree(self->left, id);
            }
            else if (self->student_id < id)
            {
                return searchTree(self->right, id);
            }
        }
    }
    return false;
}

void destroy_tree(AVL self)
{
    /*  If the tree is not empty, free each node in the tree  by running this function recursively on the left and right branches.  */
    if (!empty_tree(self))
    {
        destroy_tree(self->left);
        destroy_tree(self->right);
        free(self);
    }
}

编辑3:有趣的发展。使用的AVL树实际上是一个链表，每个节点都包含一个AVL树。现在我开始意识到(通过大量测试)AVL 树上的节点可以被删除，IF 它是第一个被构建的节点。非常有趣，甚至更烦人。

Answer 1

我认为问题在于您传递给函数的“self->right”。如果“self”是一个我假设的指针，那么在我看来，您应该像“&(self->right)”一样传递“self”的“地址”，并且当前应该被分配为'&self' 就像'当前 = *self' 一样。然后我认为它可以工作。如果我提供了完整的代码，我想我可以纠正我所说的，但我认为你明白了要点