c - C中删除AVL树中的元素

Question

struct node *delete(struct node *root, int key)
{  

    struct node *remove_node;
    if (root == NULL){
        return root;
    }

    if ( key < root->key) {
        root->left = delete(root->left, key);

    } else if ( key > root->key) {
        root->right = delete(root->right,key);

    } else {

        if ((root->left == NULL) && (root->right != NULL)){
            remove_node = root->right;
            *root = *remove_node;
            deletetree(remove_node); // this is for free-ing the memory

        } else if ((root->right == NULL)  && (root->left != NULL)){
            remove_node = root->left;
            *root = *remove_node;
            deletetree(remove_node);

        } else if ((root->right == NULL)  && (root->left == NULL)){
            remove_node = root;
            root = NULL;

        } else {

            remove_node = successor(root);
            root->key = remove_node->key;
            root->right = delete(root->right, remove_node->key);
        }
    }

    if (root == NULL) {
        return root;

    if (balance_factor(root) == 2){
        if (balance_factor(root->left) == -1) {
            return single_right_rotation(root);

        } else if (balance_factor(root->left) == 1) {
            return double_left_rotation(root);
        }
    }

    if (balance_factor(root) == -2) {
        if (balance_factor(root->right) == -1) {
            return single_left_rotation(root);
        }
        else if (balance_factor(root->right) == 1)  { 
        return double_right_rotation(root);
            }
        }
    }

    return root;    
}

这是我删除 AVL 树中元素的代码。一切似乎都工作正常，它处理节点 n 没有子节点、一个子节点和两个子节点时的所有情况。但由于某种奇怪的原因，它没有平衡树，也没有到达该代码块。

希望有人可以帮助我调试代码，因为我无法找到错误“确切”来自哪里。

提前致谢

PS:后继函数仅返回要删除的节点的右侧树上的最小元素，deletetree 处理释放内存分配的内容。而且我 100% 相信我的旋转工作正常，因为它在我的插入功能中工作得很好。

Answer 1

您可以使用临时根作为引用，并且可以像这样进行更改:

struct node *localRoot = root;

然后你将 root 更改为 localRoot，问题可能就解决了。希望对您有所帮助。