在紅黑樹中插入節點的錯誤

我想在紅黑樹中插入節點。函數rotate_left，rotate_right，插入正確，但rb_fixup似乎是錯誤的。紅色顯示爲1，黑色顯示爲0.我已經實施了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

您的代碼假定很多指針不爲null。添加斷言以確保它們不爲空。例如，'while（z-> parent-> color == 1）'假定'z'不爲空，並且'z-> parent'不爲空。你可以在循環之前添加'assert（z！= 0 && z-> parent！= 0）;'以保護第一次迭代;你需要做更多的工作來確保後續的迭代是安全的。或者使用調試器來找出哪個語句導致崩潰並檢查該語句中涉及的所有指針。 –

我添加了行但沒有幫助。爲了調試，我在每次if/while後都添加了print語句，以瞭解它可能存在問題的地方。如果我輸入數據4，41，14，它會顯示after while後面的打印語句，else else（else if（z-> parent == z-> parent-> parent-> right）），顯示分段故障。所以，問題可能是線路：'Z = Z->父;''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

在紅黑樹中插入節點的錯誤

回答

相關問題