Ошибка сегментации (ядро сброшено) во время «коррекции» красно-черного дерева - C

Question

Код выглядит следующим образом:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

typedef struct node
{
    unsigned long int val;
    bool black;
    struct node* parent;
    struct node* lchild;
    struct node* rchild;
}mynode;

mynode* createNode(unsigned long int ival, mynode* father);
mynode* createLeaf(unsigned long int ival, mynode* father);
mynode* search (unsigned long int ival, mynode *root);
void insert ( unsigned long int ival, mynode *root);
mynode * getFather (mynode* child);
mynode * getUncle (mynode* child);
void doubleRotate (mynode* myptr);
void rotate(mynode* myptr);
void myRotate(mynode* myptr);
void changeRed(mynode* myptr);
void changeBlack(mynode* myptr);
void colorFlip( mynode* myptr);
void subtreeRepair (mynode* myptr);
bool isRoot(mynode* myptr);
void rootRepair (mynode* myptr);
void repair (mynode* myptr);
bool isRed (mynode* myptr);
void smallRotate(mynode* myptr);


int main()
{
    mynode myroot;
    mynode *myrootptr;
    mynode *myleafptr;
    FILE *fp;
    int ch;
    unsigned long long lines=0, i=0;
    unsigned long *myArr;
    unsigned long int ival;

   fp = fopen("integers.txt","r");
   if(fp == NULL)
   {
      printf("Error in opening file.");
      return(-1);
   }

    while(!feof(fp))
    {
    ch = fgetc(fp);
    if(ch == '\n')
    {
        lines++;
    }
    }
    lines++;
    printf("lines = %lu", lines);
    myArr = (unsigned long*)calloc(lines, sizeof(unsigned long));

    fseek(fp, 0, SEEK_SET);
    while(!feof(fp))
    {
          fscanf(fp, "%lu,", &myArr[i] ); // des ta pos k giati tou input.
          i++;
    }
    fclose(fp);

    myroot.val = myArr[0];
    myroot.parent = NULL;
    myroot.lchild = NULL;
    myroot.rchild = NULL;
    myroot.black = true;
    myrootptr = &myroot;
    myleafptr = createLeaf(myrootptr->val, myrootptr);
    myrootptr->lchild = myleafptr;
    myleafptr = createLeaf(myrootptr->val, myrootptr);
    myrootptr->rchild = myleafptr;
    for(i=1; i<lines; i++)
    {
        ival = myArr[i];
        insert(ival, myrootptr);
    }

    return 0;
}

mynode* createNode(unsigned long int ival, mynode* father)
{
  mynode* nodeptr = (mynode* )malloc(sizeof(mynode));
  nodeptr->val = ival;
  nodeptr->lchild = NULL;
  nodeptr->rchild = NULL;
  nodeptr->parent = father;
  nodeptr->black = false;
  return nodeptr;
}

mynode* createLeaf(unsigned long int ival, mynode* father)
{
  mynode* leafptr = (mynode* )malloc(sizeof(mynode));
  leafptr->val = ival;
  leafptr->lchild = NULL;
  leafptr->rchild = NULL;
  leafptr->parent = father;
  leafptr->black = true;
  return leafptr;
}

mynode* search (unsigned long int ival, mynode *rootptr)
{
    mynode* myptr = (mynode* )malloc(sizeof(mynode));

    myptr = rootptr;

    while ( ( (myptr->lchild) != NULL) && ( (myptr->rchild) != NULL))
    {
        if ( ival < myptr->val)
        {
            myptr = myptr->lchild;
        }
        else
        {
            myptr = myptr->rchild;
        }
    }
    return myptr;
    }

void insert (unsigned long int ival, mynode *root)
{
    mynode * current = (mynode* )malloc(sizeof(mynode));
    mynode * insertleafptr = (mynode* )malloc(sizeof(mynode));
    mynode * father = (mynode* )malloc(sizeof(mynode));
    unsigned long int max, min;
    unsigned long int num;

    current = search(ival, root);
    num = current->val;
    if((current->val) == ival)
    {
        return ;
    }
    else
    {
        if(ival>(current->val))
        {
            max = ival;
            min = current->val;
        }
        else
        {
            max = current->val;
            min = ival;
        }
        father = current->parent;
        current = createNode(min, father);
        if(num == (father->lchild)->val)
        {
            father->lchild = current;
        }
        else
        {
            father->rchild = current;
        }
        insertleafptr = createLeaf(min, current);
        current->lchild = insertleafptr;
        insertleafptr = createLeaf(max, current);
        current->rchild = insertleafptr;
        repair(current);
       return ;
    }
}

mynode * getFather (mynode* child)
{
    return child->parent;
}

mynode * getUncle (mynode* child)
{
    mynode * randNode1 = (mynode* )malloc(sizeof(mynode));
    mynode * randNode2 = (mynode* )malloc(sizeof(mynode));
    randNode1 = getFather(child);
    randNode2 = getFather(randNode1);
    if((randNode1->val) == ((randNode2->lchild)->val))
    {
        return randNode2->rchild;
    }
    else
    {
        return randNode2->lchild;
    }
    free(randNode1);
}

bool isRed (mynode* myptr)
{
    if ((myptr->black) != true)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void changeColor (mynode* myptr)
{
        if ((myptr->black) == true)
        {
            myptr->black = false;
        }
        else
        {
            myptr->black = true;
        }
}

bool sameType(mynode* myptr)
{
    int counter = 0;
    unsigned long int val;
    mynode* father;
    father = myptr->parent;
    val = myptr->val;
    if ( val == (father->lchild)->val)
    {
        counter++;
    }
    else
    {
        counter--;
    }
    val = father->val;
    father = father->parent;
        if ( val == (father->lchild)->val)
    {
        counter++;
    }
    else
    {
        counter--;
    }
    if( (counter == 2) || (counter == -2))
    {
        return true;
    }
    else
    {
        return false;
    }
}



void repair (mynode* myptr)
{
    rootRepair(myptr);
    subtreeRepair(myptr);
    return ;
}

void rootRepair (mynode* myptr)
{
    if(isRoot(myptr))
    {
        myptr->black = true;
    }
    return ;
}

bool isRoot(mynode* myptr)
{
    if ((myptr->parent) == NULL)
    {
        return true;
    }
    return false;
}

void subtreeRepair (mynode* myptr)
{
    mynode* father = (mynode* )malloc(sizeof(mynode));
    mynode* uncle = (mynode* )malloc(sizeof(mynode));
    father = getFather(myptr);
    uncle = getUncle(myptr);

    if( (isRed(father)) || (isRoot(myptr) == false))
    {
        if( isRed(uncle))
        {
            colorFlip(myptr);
        }
        else
        {
            myRotate(myptr);
        }

    }
    return ;
}


void colorFlip( mynode* myptr)
{
    mynode* cfather = (mynode* )malloc(sizeof(mynode));
    mynode* cuncle = (mynode* )malloc(sizeof(mynode));
    mynode* cgrandpa = (mynode* )malloc(sizeof(mynode));
    cfather = getFather(myptr);
    cuncle = getUncle(myptr);
    cgrandpa = getFather(cfather);
    changeBlack(cfather);
    changeBlack(cuncle);
    changeRed(cgrandpa);
    repair(cgrandpa);
    return ;
}

void changeBlack(mynode* myptr)
{
    myptr->black = true;
    return ;
}

void changeRed(mynode* myptr)
{
    myptr->black = false;
    return ;
}

void myRotate(mynode* myptr)
{
    if( sameType(myptr))
    {
        rotate(myptr);
    }
    else
    {
        doubleRotate(myptr);
    }
    return ;
}

void rotate(mynode* myptr)
{
    mynode* rfather = (mynode* )malloc(sizeof(mynode));
    mynode* runcle = (mynode* )malloc(sizeof(mynode));
    mynode* rgrandpa = (mynode* )malloc(sizeof(mynode));
    mynode* current = (mynode* )malloc(sizeof(mynode));
    rfather = getFather(myptr);
    runcle = getUncle(myptr);
    rgrandpa = getFather(rfather);

    changeColor(rfather);
    changeColor(rgrandpa);

    if((rfather->lchild)->val == ((myptr)->val) )
    {
        current = rfather->rchild;
    }
    else
    {
        current = rfather->lchild;
    }

    if((rgrandpa->lchild)->val == (runcle->val))
    {
        rgrandpa->rchild = current;
    }
    else
    {
        rgrandpa->lchild = current;
    }

    rfather->parent = rgrandpa->parent;
    current = rgrandpa->parent;
    if((current->lchild)->val == (rgrandpa)->val)
    {
        current->lchild = rfather;
    }
    else
    {
        current->rchild = rfather;
    }

    if((rfather->rchild)->val == (myptr)->val)
    {
        rfather->lchild = rgrandpa;
    }
    else
    {
        rfather->rchild = rgrandpa;
    }

    free(current);
    return ;
}

void doubleRotate (mynode* myptr)
{
    mynode* current = (mynode* )malloc(sizeof(mynode));
    current = myptr->parent;
    smallRotate(myptr);
    rotate(current);
    return ;
}


void smallRotate(mynode* myptr)
{
    mynode* srfather = (mynode* )malloc(sizeof(mynode));
    mynode* srgrandpa = (mynode* )malloc(sizeof(mynode));
    mynode* srcurrent = (mynode* )malloc(sizeof(mynode));
    int flag = 0;
    srfather = getFather(myptr);
    srgrandpa = getFather(srfather);

    if( (srgrandpa->lchild)->val == (srfather->val))
    {
        srgrandpa->lchild = myptr;
    }
    else
    {
        srgrandpa->rchild = myptr;
        flag = 1;
    }

    if(flag = 0)
    {
        srcurrent = myptr->lchild;
        myptr->lchild = srfather;
        srfather->rchild = srcurrent;
    }
    else
    {
        srcurrent = myptr->rchild;
        myptr->rchild = srfather;
        srfather->lchild = srcurrent;
    }

    return ;
}

Запрограммируйте до тех пор, пока функция вставки не запустится без проблем.Ошибка сегментации произошла, когда я добавил функцию восстановления (в функции вставки) и все функции, которые реализуют свойства красно-черного дерева в моей структуре данных.

Алгоритм коррекции R & B (или балансировки, если вы предпочитаете) в основном из здесь

важный EDIT:

Использование отладчика привело меня к функциям getUncle иЯ думаю, что произошла ошибка сегментации.Я предсказываю, что он не может вернуть «дядю», потому что он близок к корню.Поэтому, когда информация в начале массива хранится в дереве или балансировка достигнута так высоко в дереве, у меня возникает проблема ... Есть идеи?

Answer 1

У вас есть следующая строка:

if(flag = 0)

, которая, скорее всего, должна быть:

if(flag == 0)

Обратите внимание, что = - это присвоение, == - это сравнение.

Обратите внимание, что если бы вы включили предупреждения компилятора (например, gcc -Wall ...), это было бы помечено во время компиляции вместе с другими полезными предупреждениями о сомнительном коде:

rbtree.c:64:31: warning: format specifies type 'unsigned long' but the argument has type 'unsigned long long' [-Wformat]
        printf("lines = %lu", lines);
                        ~~~   ^~~~~
                        %llu
rbtree.c:436:17: warning: using the result of an assignment as a condition without parentheses [-Wparentheses]
        if(flag = 0)
           ~~~~~^~~
rbtree.c:436:17: note: place parentheses around the assignment to silence this warning
        if(flag = 0)
                ^
           (       )
rbtree.c:436:17: note: use '==' to turn this assignment into an equality comparison
        if(flag = 0)
                ^
                ==
2 warnings generated.