Ошибка при вставке узлов в красные черные деревья

Я пытаюсь вставить узлы в красные черные деревья. Функции rotate_left, rotate_right, вставка верны, но rb_fixup кажется неправильным. Красный цвет отображается как 1 и черный как 0. Я реализовал algo из CLRS. Когда вставлен третий элемент, он дает ошибку сегментации. Код rb_fixup:Ошибка при вставке узлов в красные черные деревья

struct node 
{ 
    int data; 

    int color; 
    struct node *left; 
    struct node *right; 
    struct node *parent; 
}*root; 


rb_fixup(struct node *z) 
{ 

    struct node *y; 
    y=(struct node *)malloc(sizeof(struct node)); 
    while(z->parent->color==1) 
    { 
     if(z->parent==z->parent->parent->left) 
     { 
      y=z->parent->parent->right; 
      if(y->color==1) 
      { 
       z->parent->color=0; 
       y->color=0; 
       z->parent->parent->color=1; 
       z=z->parent->parent; 
      } 
      else if(z==z->parent->right) 
      { 
       z=z->parent; 
       rotate_left(z); 
      } 
      z->parent->color=0; 
      z->parent->parent->color=1; 
      rotate_right(z->parent->parent); 

     } 
     else if(z->parent==z->parent->parent->right) 
     { 
      y=z->parent->parent->left; 
      if(y->color==1) 
      { 
       z->parent->color=0; 
       y->color=0; 
       z->parent->parent->color=1; 
       z=z->parent->parent; 
      } 
      else if(z->parent->left==z) 
      { 
       z=z->parent; 
       rotate_right(z); 
      } 
      z->parent->color=0; 
      z->parent->parent->color=1; 
      rotate_left(z->parent->parent); 
     } 
    } 
    root->color=0; 
}

источник

2015-06-13 Ravi Kuldeep

Ваш код предполагает, что множество указателей не равно нулю. Добавьте утверждения, чтобы они не были нулевыми. Например, 'while (z-> parent-> color == 1)' предполагает, что 'z' не является нулевым, а' z-> parent' не равно null. Вы можете добавить 'assert (z! = 0 && z-> parent! = 0);' перед циклом для защиты первой итерации; вам нужно сделать немного больше, чтобы убедиться, что последующие итерации безопасны. Или используйте отладчик, чтобы выяснить, какой оператор вызывает крах, и проверьте все указатели, участвующие в этом утверждении. –

Я добавил строки, но не помогал. Чтобы отлаживать, я добавлял инструкции print после каждого if/while, чтобы узнать, где могут возникнуть проблемы. Если я введу данные 4, 41, 14, он покажет мне операторы печати after while, after else if ('else if (z-> parent == z-> parent-> parent-> right'), но затем показывает ошибку сегментации. Таким образом, проблема может быть в строках: 'z = z-> parent;' rotate_right (z); '@Johnathan –

Итак, вы запустили программу с помощью отладчика? На какой линии он врезался? Вы запустили его под ['valgrind'] (http://www.valgrind.org/)? Рассказывает ли вам, где проблема? Есть ли проблемы перед сбоем? Как мы можем протестировать ваш код без образца RB-дерева, которое вы создали с другими функциями? Откуда вы знаете, что функции поворота и вставки в порядке? Когда вы вызываете 'rb_fixup()' и почему? У вас есть функция, которая сбрасывает все дерево RB? Если нет, сделайте это и используйте его. Если да, то что он говорит о дереве прежде, чем вы потерпите крах? –

Я решил вышеупомянутую проблему. Ошибка с указанным выше кодом заключается в том, что если дядя краснеет, он окрашивает дядю и родителя черного цвета, а красный бабушка, но затем переходит к выполнению операций, записанных после else if каждого условия, и многие условия выполнялись неправильно. Окончательный код выглядит следующим образом: -

rb_fixup(struct node *z) 
{ 

    struct node *y; 
    y=(struct node *)malloc(sizeof(struct node)); 
    while(z->parent->color==1 && z->parent!=NULL) 
    { 
     if(z->parent==z->parent->parent->left) 
     { 
      if(z->parent->parent->right!=NULL) 
      y=z->parent->parent->right; 
      if(y->color==1) 
      { 
       z->parent->color=0; 
       y->color=0; 
       z->parent->parent->color=1; 
       z=z->parent->parent; 
      } 
      else if(z==z->parent->right) 
      { 
       z=z->parent; 
       rotate_left(z,z->right); 
       z->parent->color=0; 
       z->parent->parent->color=1; 
       rotate_right(z->parent->parent,z->parent); 
      } 
      else 
      { 
       z->parent->color=0; 
       z->parent->parent->color=1; 
       rotate_right(z->parent->parent,z->parent); 
      } 
     } 
     else 
     { 
      if(z->parent->parent->left!=NULL) 
      { 
       y=z->parent->parent->left; 
      }   
      if(y->color==1) 
      { 
       z->parent->color=0; 
       y->color=0; 
       z->parent->parent->color=1; 
       z=z->parent->parent;     
      } 
      else if(z==z->parent->left) 
      { 
       z=z->parent; 
       rotate_right(z,z->left); 
       z->parent->color=0; 
       z->parent->parent->color=1; 
       rotate_left(z->parent->parent,z->parent); 
      } 
      else 
      { 
       z->parent->color=0; 
       z->parent->parent->color=1; 
       rotate_left(z->parent->parent,z->parent); 
      } 
     } 
    } 
    root->color=0; 
}

источник

2015-06-16 07:38:05

Ошибка при вставке узлов в красные черные деревья

ответ

Смежные вопросы