Red Black Treeノードの正しい色付けが得られません

Question

最終的にどのようにセグメンテーション違反を発生させずに赤い黒色のツリーにアイテムを挿入するのかがわかりました。

私は、次の順序でツリーに次の値を挿入しようとしています：4 3 2 6 5 1

私は次の取得順序どおりツリーをプリントアウトするために行くとき：1-R 2-B 3-B 4-R 5-R 6-B

私が取得する必要があるときは：ここで1-R 2-B 3-B 4-R 5-B 6-R

は私InsertFixUp機能です：

void RBTree::RBInsertFixUp(RBNode* z){ 
RBNode* y; 

if(z == RBTree::root){ 
    root->color = 'B'; 
}else{ 
    while(z->parent->color == 'R'){ 
     if(z->parent == z->parent->parent->left){ 
      y = z->parent->parent->right; 


     if(y->color == 'R'){ 
      z->parent->color = 'B';     //Case 1 Check 
      y->color = 'B';       //Case 1 Check 
      z->parent->parent->color = 'R';   //Case 1 Check 
      z = z->parent->parent;     //Case 1 
     }else{ 

       if(z == z->parent->right){ 
        z = z->parent;     //Case 2 
        RBLeftRotate(z);    //Case 2 Look at Rotate 
       } 
       z->parent->color = 'B';    //Case 3 Check 
       z->parent->parent->color = 'R';  //Case 3 Check 
       RBRightRotate(z->parent->parent); //Case 3 Look at Rotate 
      } 
     }else{ 
      y = z->parent->parent->left; 

      if(y->color = 'R'){      
       z->parent->color = 'B';    //Case 1 Check 
       y->color = 'B';      //Case 1 Check 
       z->parent->parent->color = 'R';  //Case 1 Check 
       z = z->parent->parent;    //Case 1 

      }else{ 

       if(z = z->parent->left){ 
        z = z->parent;     //Case 2 
        RBRightRotate(z);    //Case 2 Look at Rotate 
       } 
       z->parent->color = 'B';    //Case 3 Check 
       z->parent->parent->color = 'R';  //Case 3 Check 
       RBLeftRotate(z->parent->parent); //Case 3 Look at Rotate 
      } 
     } 
    } 

    root->color = 'B'; 
} 

ここは私の左と右ローテートしている：私が見ることができるすべてのものから

void RBTree::RBLeftRotate(RBNode* x){ 
    RBNode* y = x->right; 
    x->right = y->left; 
    y->left->parent = x; 
    y->parent = x->parent; 

    if(x->parent == RBTree::Tnil){ 
     root = y; 
    }else if(x == x->parent->left){ 
     x->parent->left = y; 
    }else{ 
     x->parent->right = y; 
    } 

    y->left = x; 
    x->parent = y; 
} 

void RBTree::RBRightRotate(RBNode* x){ 
    RBNode* y = x->left; 
    x->left = y->right; 
    y->right->parent = x; 
    y->parent = x->parent; 

    if(x->parent == RBTree::Tnil){ 
     root = y; 
    }else if(x == x->parent->right){ 
     x->parent->right = y; 
    }else{ 
     x->parent->left = y; 
    } 
    y->right = x; 
    x->parent = y; 
} 

、私の着色が権利であると私の回転もありますが、多分私は何かが欠けています。私の配色がどうして消えてしまうのかについての助けは素晴らしいことでしょう。

Answer 1

非赤叔父のパスのための第2の回転（彼女のZ-から>親が子枝を残している）の場合：

RBRightRotate(z->parent->parent); //Case 3 Look at Rotate 

あなたは祖父母ノードで回転しているが、zはすでに移動されていますzとz-> parentの向きが異なる場合は1つ上のレベルになります。しかし、あなたは何を見てなかった -

if(z == z->parent->right) 
     RBLeftRotate(z->parent); 
    else 
     z = z->parent; 

    z->color = 'B'; 
    z->parent->color = 'R'; 
    RBRightRotate(z->parent);