Операция вставки Red Black Tree продолжает падать

Question

Я пытался реализовать Red Black Tree, но не смог сам его кодировать, поэтому я искал код, написанный в C, и нашел приведенный ниже код на github. Я проанализировал его, и это было довольно красиво. прямо и просто, поэтому я сделал небольшие изменения (просто переименовал пару переменных и добавил меню), и когда я попытался запустить его, я столкнулся с проблемой при попытке повернуть дерево. Вставка работает нормально, пока дерево не станет неуравновешенным, особенно когда дядя становится "Черным" моей программе не удается повернуть дерево, и он просто падает. Итак, позвольте мне объяснить вам ход программы: всякий раз, когда мы вставляем новый узел, вызывается функция с именем insert, после успешной вставки она вызывает другую функцию с именем insertfixup, которая проверяет, были ли какие-либо свойства красного черного дерева нарушается, и если это так, то он вращает дерево на основе того, является ли дядя проблемного c узла RED или ЧЕРНЫЙ если дядя красный , то он работает нормально, но как только дядя становится черным , он просто падает. Может ли кто-нибудь изучить код, который я дал ниже, и указать, что именно является причиной проблемы, я сомневаюсь, что это как-то связано с указателями, но не может понять, что на самом деле происходит,

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

typedef struct RB_Tree {
    struct RB_Tree *left, *right, *parent;
    int info;
    char color;
} node;
int count = 0;

void left_rotate(node **root, node *par) {  
    node *child = par->right;

    par->right = child->left;

    if (child->left!=NULL)
        child->left->parent = par;

    child->parent = par->parent;

    if (par->parent == NULL)
        (*root) = child;
    else
    if (par == par->parent->left)
        par->parent->left = child;
    else
        par->parent->right = child; 

    child->left = par;
    par->parent = child;
}

void right_rotate(node **root, node *par) {
    node *child = par->left;

    par->left = child->right;

    if (child->right!=NULL)
        child->right->parent = par;

    child->parent = par->parent;

    if (par->parent == NULL)
        (*root) = child;
    else
    if (par = par->parent->left)
        par->parent->left = child;
    else
        par->parent->right = child;

    child->right = par;

    par->parent = child;
}

void insertFixup(node **root, node *new) {
    while (new != *root && new->parent->color == 'R') {
        node *uncle;
        //Find uncle and store uncle in "uncle" variable!

        if (new->parent == new->parent->parent->left) {
            uncle = new->parent->parent->right;
        } else {
            uncle = new->parent->parent->left;
        }

        if (uncle == NULL || uncle->color == 'B') {

            if (new->parent == new->parent->parent->left && new == new->parent->left) {
                printf("Inside ll case before rot");
                char col = new->parent->color;
                new->parent->color = new->parent->parent->color;
                new->parent->parent->color = col;

                right_rotate(root, new->parent->parent);
            }

            if (new->parent == new->parent->parent->right && new == new->parent->right) {
                char col = new->parent->color;
                new->parent->color = new->parent->parent->color;
                new->parent->parent->color = col;
                left_rotate(root, new->parent->parent);
            }

            if (new->parent == new->parent->parent->left && new == new->parent->right) {
                char col = new->color;
                new->color = new->parent->parent->color;
                new->parent->parent->color = col;
                //printf("\nHere we are in the left right!");
                left_rotate(root, new->parent);

                right_rotate(root, new->parent->parent); 
            }

            if (new->parent == new->parent->parent->right && new == new->parent->left) {
                char col = new->color;
                new->color = new->parent->parent->color;
                new->parent->parent->color = col;
                right_rotate(root, new->parent);
                left_rotate(root, new->parent->parent);
            }
        }

        if (uncle) {
            if (uncle->color == 'R') {
                uncle->color = 'B';
                new->parent->color = 'B';
                new->parent->parent->color = 'R';
                new = new->parent->parent;
            }
        }
    }

    (*root)->color = 'B';
}

void insert(node **root, int data) {
    node *new = (node*)malloc(sizeof(node));
    new->info = data;
    new->parent = new->left = new->right = NULL;

    if (*root == NULL) {
        (*root) = new;
        new->color = 'B';
    } else {
        node *par;
        node *temp = (*root);

        while (temp) {
            par = temp;
            if(new->info > temp->info)
                temp = temp->right;
            else
                temp = temp->left;
        }

        new->parent = par;

        if (par->info > new->info)
            par->left = new;
        else
            par->right = new;

        new->color = 'R';

        insertFixup(root, new);
    }
}

void main() {
    int men, c, data;
    node *root = NULL;

    while (1) {
        system("cls");
        printf("1.) Insert\n");
        printf("2.) exit\n");
        printf("Enter your choice : ");
        scanf("%d", &men);
        switch (men) {
          case 1:
            printf("Enter data : ");
            scanf("%d", &data);
            insert(&root, data);
            printf("%d successfully added!", data);
            break;

          case 2:
            exit(0);

          default:
            printf("Invalid choice!");
            while ((c = fgetc(stdin)) != '\n') {}
            break;       
        }
        getch();
    }
}

Answer 1

Скомпилируйте с предупреждениями, в строке 53:

else if(par = par->parent->left)
    par->parent->left = child;

вы назначаете, вы хотите сравнить:

else if(par == par->parent->left)
    par->parent->left = child;

Answer 2

Основные проблемы

Как уже говорилось, строка 53

иначе, если (par = par-> parent-> left)

должно быть

else if(par == par->parent->left)

Алгоритм в insertFixup не является правильным, например, для вставки данных 3, затем 2, а затем 1 производит cra sh, я вижу идентичное определение для inte rnet, возможно, вы его получили, но, к сожалению, ваш источник содержит ошибки Это определение работает:

void insertFixup(node **root, node *new) {
  while (new != *root && new->parent->color == 'R') {
    if (new->parent == new->parent->parent->left) {
      if (new->parent->parent->right && new->parent->parent->right->color == 'R') {
        new->parent->color = 'B';
        new->parent->parent->right->color = 'B';
        new->parent->parent->color = 'R';
        new = new->parent->parent;
      }
      else {
        if (new == new->parent->right) {
          new = new->parent;
          left_rotate(root, new);
        }

        new->parent->color = 'B';
        new->parent->parent->color = 'R';
        right_rotate(root, new->parent->parent);
      }
    }
    else {
      if (new->parent->parent->left && new->parent->parent->left->color == 'R') {
        new->parent->color = 'B';
        new->parent->parent->left->color = 'B';
        new->parent->parent->color = 'R';
        new = new->parent->parent;
      }
      else {
        if (new == new->parent->left) {
          new = new->parent;
          right_rotate(root, new);
        }

        new->parent->color = 'B';
        new->parent->parent->color = 'R';
        left_rotate(root, new->parent->parent);
      }
    }
  }

  (*root)->color = 'B';
}

Дополнительные проблемы

Неверная подпись * main *, main возвращает int

Если пользователь не вводит int , ваша scanf строка 160 не устанавливает men , и вы можете проверить никогда не инициализированное значение , Всегда проверьте возвращаемое значение scanf , например, чтобы быть совместимым с кодом после:

if (scanf("%d", &men) != 1)
  men = -1;

In

while ((c = fgetc(stdin)) != '\n') {}

c установлено, но никогда не используется, и наихудшее, если вы достигнете, например, EOF , потому что ввод был перенаправлен в файл, вы будете l oop без окончания , Например,

while ((c = fgetc(stdin)) != '\n')
  if (c == EOF)
    exit(0);

Строка 10:

int count = 0;

определить глобальную переменную, которая никогда не использовалась, вы можете удалить эту строку

---

Чтобы проверить мое предложение, я добавил эту функцию для отображения дерева:

void display(node * x){
  if (x) {
    display(x->left);
    printf("%d ", x->info);
    display(x->right);
  }
}

, и я изменил ваш main , чтобы иметь возможность отображать дерево:

int main()
{
  int men, c, data;
  node *root = NULL;

  while (1) {
    fputs("\n"
          "1.) Insert\n"
          "2.) exit\n"
          "3.) Display tree\n"
          "Enter your choice : ",
          stdout);
    if (scanf("%d", &men) != 1)
      men = -1;

    switch (men) {
    case 1:
      printf("Enter data : ");
      scanf("%d", &data);
      insert(&root, data);
      printf("%d successfully added!", data);
      break;

    case 2:
      exit(0);

    case 3:
      display(root);
      putchar('\n');
      break;

    default:
      puts("Invalid choice!");
      while ((c = fgetc(stdin)) != '\n')
        if (c == EOF)
          exit(0);
      break;       
    }
  }
}

Компиляция и исполнение:

bruno@bruno-XPS-8300:/tmp/t$ gcc -Wall -Wextra t.c
bruno@bruno-XPS-8300:/tmp/t$ ./a.out

1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 3
3 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 2
2 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 1
1 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 3
1 2 3 

1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 5
5 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 1
Enter data : 4
4 successfully added!
1.) Insert
2.) exit
3.) Display tree
Enter your choice : 3
1 2 3 4 5 

1.) Insert
2.) exit
3.) Display tree
Enter your choice : 2
bruno@bruno-XPS-8300:/tmp/t$