违反AVL树平衡期间的分段错误

Question

我尝试实现一个程序来说明 AVL 树的基本操作。之前我将该代码制作为二叉搜索树，并将其操作扩展为 AVL。每当树必须保持平衡时，无论如何旋转，都会出现问题。在所有情况下（LL LR RR RL）我都会遇到分段错误。我找不到我做错了什么。

#include <stdio.h>
#include <stdlib.h>


//define the node for the BST
typedef struct node
{
    struct node * left;
    int data;
    struct node * right;
    int height;
}node;

typedef node * BST;

//function definitions 
void BST_INSERT(BST *tree,int data);
void BST_DESTROY(BST *tree);
BST NODE_CREATE(int data);
//AVL OPERATIONS
BST ROTATE_L(BST C);
BST ROTATE_R(BST C);
BST ROTATE_LR(BST C);
BST ROTATE_RL(BST C);
int max(int a,int b);
int height(BST C);



//main function
int main(void)
{
    BST t = NULL;
//case with seg fault 
   BST_INSERT(&t,10);
    BST_INSERT(&t,15);
    BST_INSERT(&t,20);
    BST_INSERT(&t,25);
//another case with seg fault 
    BST_INSERT(&t,0);
    BST_INSERT(&t,-5);
    BST_INSERT(&t,-10);
    BST_INSERT(&t,-15);
//non seg fault case 
 /* BST_INSERT(&t,10);
    BST_INSERT(&t,5);
    BST_INSERT(&t,15);
    BST_INSERT(&t,3);
    BST_INSERT(&t,6);
    BST_INSERT(&t,14);
    BST_INSERT(&t,16);

*/


    return 0;
}








//helper to create a new node before intgrating it to the tree
//its not nessecaty but is used in order to create some abstraction
//to the main function
BST NODE_CREATE(int data)
{
        BST new = (BST)malloc(sizeof(node));
        if(!new)
        {
            fprintf(stderr,"error allocating memory\n");
            return NULL;
        }
        new->data = data;
        new->right = NULL;

        new->left = NULL;
        return new;
}
//insert a node in the BST
//recursively find the proper position for the element to be inserted 
//left wise for the smallest elementsprintf("___UNDER CONSTRUCTION___");
//right wise for the highest elements return 0;
//take as base case null
//if bigger than current element move to the right child 
//if equal or smaller than the current parent move to the left child 
//if the node is null place the element there 
//works also for uninitialized tree
void BST_INSERT(BST *tree,int data)
{
    //base case 
    if(*tree == NULL)
    {
        *tree = NODE_CREATE(data);
        return;
    }
    else if(data <= (*tree)->data)
    {
        BST_INSERT(&(*tree)->left,data);
    }
    else
    {
        BST_INSERT(&(*tree)->right,data);
    }

    // Update the height of the current node
    (*tree)->height = max(height((*tree)->left), height((*tree)->right)) + 1;

    // Check balance factor and perform rotations if necessary
    int balance = height((*tree)->left) - height((*tree)->right);

    // Left-Left Case
    if (balance > 1 && data <= (*tree)->left->data) {
        *tree = ROTATE_R(*tree);
    }
    // Left-Right Case
    else if (balance > 1 && data > (*tree)->left->data) {
        *tree = ROTATE_LR(*tree);
    }
    // Right-Right Case
    else if (balance < -1 && data > (*tree)->right->data) {
        *tree = ROTATE_L(*tree);
    }
    // Right-Left Case
    else if (balance < -1 && data <= (*tree)->right->data) {
        *tree = ROTATE_RL(*tree);
    }
}

//recursive aproach to destroy the binary search tree
//traverse to the lowest nodes from left to right
//if we reach null node then we destroy the node
//following the order left-right-parent
void BST_DESTROY(BST *tree)
{
    //base case NULL node 
    if(*tree == NULL)
    {
        return;
    }
    BST_DESTROY(&(*tree)->left);
    BST_DESTROY(&(*tree)->right);
    printf("deleting : %i ",(*tree)->data);
    free(*tree);

}

//find the height of the nodes and the maximum of them

int max(int a,int b)
{
    //return the highest height
    return (a > b) ? a : b;
}
int height(BST C)
{
    //null node
    if(C == NULL)
    {
        return 0;
    }
    return C->height;
}


//perform LEFT rotation
BST ROTATE_L(BST C)
{
    BST L = C->left;
    C->left = L->right;
    L->right = C;
    C->height = max(height(C->left),height(C->right))+1;
    L->height = max(height(L->left),height(L->right))+1;
    return L;
}

//perform right rotation
BST ROTATE_R(BST C)
{
    BST R = C->right;
    C->right = R->left;
    R->left = C;
    C->height = max(height(C->left),height(C->right))+1;
    R->height = max(height(R->left),height(R->right))+1;
    return R;
}
//perform rl rotation
BST ROTATE_RL(BST C)
{
    C->right = ROTATE_R(C->right);
    return ROTATE_L(C);
}
//perform lr rotation
BST ROTATE_LR(BST C)
{
    C->left = ROTATE_L(C->left);
    return ROTATE_R(C);
}

我没有发送整个代码，因为正如我所说，我已经实现了 BST 树的代码，所以我很确定它是正确的。我的考虑是旋转函数。

我尝试的插入是：1,2,3,4 4,3,2,1 10,5,20,25,0，我还尝试了所有元素都不违反 AVL 规则的插入。更准确地说，插入：10,5,15,4,6,14,16,20 并没有导致分段错误，因为它们没有违反规则。

您将在我的代码中看到一个名为

BST_DESTROY

的函数。这是在程序结束之前销毁树。目前在我上面的程序中我没有使用它，但它功能齐全。

Answer 1

原来的

ROTATE_L

功能实际上是向右旋转，而

ROTATE_R

功能实际上是向左旋转。交换两个函数的名称（和标题注释）似乎可以解决问题。