c++ - Red Black Tree - deletion -

i've implemented delete function rbt (basing on cormen), looks works test deletion + printing tree in preorder gives me wrong answer. spent few hours looking may wrong couldn't find anything...

here's func print tree in preorder:

void print_out(rbt_node *root, rbt_node *nil) {     if(root != nil)     {         printf("%d %s ", root->key, root->data.c_str());         if(root->color == black)             printf("black ");         else             printf("red ");         if(root->parent != nil)             printf("%d ",root->parent->key);         else             printf("- ");         if(root->left != nil)             printf("%d ",root->left->key);         else             printf("- ");         if(root->right != nil)             printf("%d ",root->right->key);         else             printf("- ");         printf("\n");          print_out(root->left, nil);         if(root->right != nil)         {             print_out(root->right, nil);         }     } } 

here rest of important stuff deletion:

rbt_node *nil = new rbt_node; nil->color = black; nil->left = nil->parent = nil->right = nil;  rbt_node *tree_minimum(rbt_node *node, rbt_node *nil) {     while(node->left != nil)         node = node->left;      return node; }  rbt_node *tree_succesor(rbt_node *node, rbt_node *nil) {     if(node->right != nil)         return tree_minimum(node->right, nil);      rbt_node *helper = node->parent;     while(helper != nil && node == helper->right)     {         node = helper;         helper = helper->parent;     }      return helper; }  void delete_fixup(rbt_node *&root, rbt_node *&target, rbt_node *nil) {     rbt_node *helper = nil;     while(target != root && target->color == black)     {         if(target == target->parent->left)         {             helper = target->parent->right;             if(helper->color == red)             {                 helper->color = black;                 target->parent->color = red;                 left_rotate(root, target->parent, nil);                 helper = target->parent->right;             }             if(helper->left->color == black && helper->right->color == black)             {                 helper->color = red;                 target = target->parent;             }             else if(helper->right->color== black)             {                 helper->left->color = black;                 helper->color = red;                 right_rotate(root, helper, nil);                 helper = target->parent->right;             }             else             {                 helper->color = target->parent->color;                 target->parent->color = black;                 helper->right->color = black;                 left_rotate(root, target->parent, nil);                 target = root;             }         }         else         {             helper = target->parent->left;             if(helper->color == red)             {                 helper->color = black;                 target->parent->color = red;                 right_rotate(root, target->parent, nil);                 helper = target->parent->left;             }             if(helper->right->color == black && helper->left->color == black)             {                 helper->color = red;                 target = target->parent;             }             else if(helper->left->color== black)             {                 helper->right->color = black;                 helper->color = red;                 left_rotate(root, helper, nil);                 helper = target->parent->left;             }             else             {                 helper->color = target->parent->color;                 target->parent->color = black;                 helper->left->color = black;                 right_rotate(root, target->parent, nil);                 target = root;             }         }     }      target->color = black; }  void rbt_delete(rbt_node *&root, int key, rbt_node *nil) {     rbt_node *victim = to_delete(root, key, nil);     if(victim != nil)     {         rbt_node *help_one = nil;         rbt_node *help_two = nil;         if(victim->left == nil || victim->right == nil)             help_one = victim;         else             help_one = tree_succesor(victim, nil);          if(help_one->left != nil)             help_two = help_one->left;         else             help_two = help_one->right;          help_two->parent = help_one->parent;          if(help_one->parent == nil)             root = help_two;         else if(help_one == help_one->parent->left)             help_one->parent->left = help_two;         else             help_two->parent->right = help_two;          if(help_one != victim)         {             victim->key = help_one->key;             victim->data = help_one->data;         }          if(help_one->color == black)             delete_fixup(root, help_two, nil);     }      root->color = black; } 

at least imo, print_out isn't working way should. specific problem it's trying (directly) print out data child nodes.

when you're dealing binary tree (of sort -- unbalanced, avl, rb, etc.) traversal this:

void print_out(node *current_node) {      if current_node != nil {         show_data(current_node);          print_out(current_node->left);         print_out(current_node->right);    } } 

as is, that's pre-order; post-order or inorder matter of rearranging print_data compared recursive calls print_out (for post-order comes after them, inorder between them).

in particular, however, print_out should not have anything left or right sub-trees, other passing them parameters in recursive call. shouldn't check whether they're nil/null either -- should make recursive call, , let if (current_node != nil) handle in recursive call deal possibility we've hit leaf node.

call me lazy if will, that's as i'm willing examine without @ least some guidance sort of problem i'm looking for, , @ least reasonable assurance it's right place look. helpful (for example) if showed can insert few nodes, , expected structure, show what goes wrong when delete node. node still there? other nodes getting lost? nodes right, balance wrong? if so, what's going wrong balance?