c - 将值插入 AVL 树

Question

我用 C 语言编写了 AVL Tree 实现。 我有其他功能，但当我尝试插入一些值时显示错误。 这是我的插入函数、旋转和主要代码。 我使用 RR、LL、RL、LR 旋转来平衡树。

代码:

struct avl_tree {
int key;
int bf;
struct avl_tree *up;
struct avl_tree *left;
struct avl_tree *right;
};

typedef struct avl_tree node;


void deleteTree(node *tree)
{
    if(tree)
    {
        deleteTree(tree->left);
        deleteTree(tree->right);
        free(tree);
    }
}

void RR(node **tree, node *A)
{
node *B = A->right;
node *p = A->up;

A->right = B->left;

if(A->right)
{
    A->right->up = A;
}

B->left = A;
B->up = p;
A->up = B;

if(p)
{
    if(p->left == A) p->left = B;
    else p->right = B;
}
else *tree = B;

if(B->bf == -1)
{
    A->bf = B->bf = 0;
}
else
{
    A->bf = -1;
    B->bf = 1;
}
}


void LL(node **tree, node *A)
{
node *B = A->left;
node *p = A->up;

A->left = B->right;

if(A->left)
{
    A->left->up = A;
}

B->right = A;
B->up = p;
A->up = B;

if(p)
{
    if(p->left == A) p->left = B;
    else p->right = B;
}
else *tree = B;

if(B->bf == 1)
{
    A->bf = B->bf = 0;
}
else
{
    A->bf = 1;
    B->bf = -1;
}
}


void RL(node **tree, node *A)
{
node *B = A->right;
node *C = B->left;
node *p = A->up;

B->left = C->right;

if(B->left)
{
    B->left->up = B;
}       

A->right = C->left;

if(A->right)
{
    A->right->up = A;
}       

C->left = A;
C->right = B;
A->up = B->up = C;
C->up = p;

if(p)
{
    if(p->left == A) p->left = C;
    else p->right = C;
}
else *tree = C;

if(C->bf == -1) A->bf = 1;
else A->bf = 0;

if(C->bf == 1) B->bf = -1;
else B->bf = 0;

C->bf = 0;
}

void LR(node **tree, node *A)
{
node *B = A->left;
node *C = B->right;
node *p = A->up;

B->right = C->left;

if(B->right)
{
    B->right->up = B;
}

A->left = C->right;

if(A->left)
{
    A->left->up = A;
}       

C->right = A;
C->left = B;
A->up = B->up = C;
C->up = p;


if(p)
{
    if(p->left == A) p->left = C;
    else p->right = C;
}
else *tree = C;

if(C->bf == 1) A->bf = -1;
else A->bf = 0;

if(C->bf == -1) B->bf =1;
else B->bf = 0;

C->bf = 0;
}

void insert(node **tree, int k)
{
node *w; 
node *p;
node *r;
bool t;

w = (node*)malloc(sizeof(node));
w->left = w->right = w->up = NULL;
w->key = k;
w->bf = 0;

/* 1. Insert to AVL */
p = *tree; 

if(!p)
{
    *tree = w;
}
else 
{
    while(true)
    {
        if(k < p->key)
        {
            if(!p->left)
            {
                p->left = w;
                break;
            };

            p = p->left;
        }
        else
        {
            if(!p->right)
            {
                p->right = w;
                break;
            };

            p = p->right;
        }

    w->up = p;

/* 2. Balance AVL */
    if(p->bf) p->bf = 0;
    else 
    {
        if(p->left == w) p->bf = 1;
        else p->bf = -1;

        r = p->up;

        t = false;
        while(r)
        {
            if(r->bf)
            {
                t = true;
                break;
            };

            if(r->left == p) r->bf = 1;
            else r->bf = -1;

            p = r;
            r = r->up;
        }

        if(t)
        {
            if(r->bf == 1)
            {
                if(r->right == p) r->bf = 0;
                else if(p->bf == -1) LR(tree, r);
                else LL(tree, r);
            }
            else
            {
                if(r->left == p) r->bf = 0;
                else if(p->bf == 1) RL(tree, r);
                else RR(tree, r);
            }
        }
    }
    }
}
}

主要:

node *root;
root = NULL;


char str[100];
int n, x, i;

scanf("%d", &n);

for(i = 0; i<=n; i++)
{
    fgets(str, sizeof str, stdin);

    if (!strncmp(str, "insert", 6)) 
    {
        sscanf(str,"%*[^0-9]%d", &x);
        insert(&root, x);
        str[0] = '\0';          
    }
}

return 0;

输入:

29
insert 15
insert 41
insert 63
insert 99
insert 91
insert 55
insert 31
insert 82
insert 1
insert 90
insert 20
insert 52
insert 80
insert 99
insert 89
insert 32
insert 78 
insert 25
insert 55
insert 48
insert 33
insert 9
insert 80
insert 54
insert 87
insert 35
insert 33
insert 38
insert 78

尝试使用 LR 旋转插入值 52 后出现错误，我不知道为什么。

编辑:

insert 52

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400bfd in LR ()
(gdb) print
The history is empty.
(gdb) where
#0  0x0000000000400bfd in LR ()
#1  0x0000000000400f08 in insert ()
#2  0x0000000000401503 in main ()

编辑2:

clang -Wall -Wextra -std=c99 --analyze Alg3.c 
Alg3.c:33:13: warning: Access to field 'left' results in a dereference of a null
  pointer (loaded from variable 'B')
    A->right = B->left;
               ^~~~~~~
Alg3.c:101:12: warning: Access to field 'left' results in a dereference of a
  null pointer (loaded from variable 'B')
    node *C = B->left;
              ^~~~~~~
Alg3.c:394:10: warning: Access to field 'bf' results in a dereference of a null
  pointer (loaded from variable 't')
                                    if(!(t->bf))
                                        ^~~~~~~
3 warnings generated.

Answer 1

while (true)循环输入insert()没有在应该结束的地方结束:

       }
    // The while (true) loop should end here, but it doesn't...
    w->up = p;

/* 2. Balance AVL */