title: Red Black Tree - deletion
body: <p>I've implemented delete function for RBT (basing on Cormen), it looks like it works but test for deletion + printing tree in preorder gives me wrong answer. I spent few hours looking what may be wrong but couldn't find anything... </p>
  
  <p>Here's func to print tree in preorder:</p>
  
  <pre><code>void print_out(rbt_node *root, rbt_node *NIL)
  {
      if(root != NIL)
      {
          printf("%d %s ", root-&gt;key, root-&gt;data.c_str());
          if(root-&gt;color == BLACK)
              printf("black ");
          else
              printf("red ");
          if(root-&gt;parent != NIL)
              printf("%d ",root-&gt;parent-&gt;key);
          else
              printf("- ");
          if(root-&gt;left != NIL)
              printf("%d ",root-&gt;left-&gt;key);
          else
              printf("- ");
          if(root-&gt;right != NIL)
              printf("%d ",root-&gt;right-&gt;key);
          else
              printf("- ");
          printf("\n");
  
          print_out(root-&gt;left, NIL);
          if(root-&gt;right != NIL)
          {
              print_out(root-&gt;right, NIL);
          }
      }
  }
  </code></pre>
  
  <p>Here is rest of important stuff for deletion:</p>
  
  <pre><code>rbt_node *NIL = new rbt_node;
  NIL-&gt;color = BLACK;
  NIL-&gt;left = NIL-&gt;parent = NIL-&gt;right = NIL;
  
  rbt_node *tree_minimum(rbt_node *node, rbt_node *NIL)
  {
      while(node-&gt;left != NIL)
          node = node-&gt;left;
  
      return node;
  }
  
  rbt_node *tree_succesor(rbt_node *node, rbt_node *NIL)
  {
      if(node-&gt;right != NIL)
          return tree_minimum(node-&gt;right, NIL);
  
      rbt_node *helper = node-&gt;parent;
      while(helper != NIL &amp;&amp; node == helper-&gt;right)
      {
          node = helper;
          helper = helper-&gt;parent;
      }
  
      return helper;
  }
  
  void delete_fixup(rbt_node *&amp;root, rbt_node *&amp;target, rbt_node *NIL)
  {
      rbt_node *helper = NIL;
      while(target != root &amp;&amp; target-&gt;color == BLACK)
      {
          if(target == target-&gt;parent-&gt;left)
          {
              helper = target-&gt;parent-&gt;right;
              if(helper-&gt;color == RED)
              {
                  helper-&gt;color = BLACK;
                  target-&gt;parent-&gt;color = RED;
                  left_rotate(root, target-&gt;parent, NIL);
                  helper = target-&gt;parent-&gt;right;
              }
              if(helper-&gt;left-&gt;color == BLACK &amp;&amp; helper-&gt;right-&gt;color == BLACK)
              {
                  helper-&gt;color = RED;
                  target = target-&gt;parent;
              }
              else if(helper-&gt;right-&gt;color== BLACK)
              {
                  helper-&gt;left-&gt;color = BLACK;
                  helper-&gt;color = RED;
                  right_rotate(root, helper, NIL);
                  helper = target-&gt;parent-&gt;right;
              }
              else
              {
                  helper-&gt;color = target-&gt;parent-&gt;color;
                  target-&gt;parent-&gt;color = BLACK;
                  helper-&gt;right-&gt;color = BLACK;
                  left_rotate(root, target-&gt;parent, NIL);
                  target = root;
              }
          }
          else
          {
              helper = target-&gt;parent-&gt;left;
              if(helper-&gt;color == RED)
              {
                  helper-&gt;color = BLACK;
                  target-&gt;parent-&gt;color = RED;
                  right_rotate(root, target-&gt;parent, NIL);
                  helper = target-&gt;parent-&gt;left;
              }
              if(helper-&gt;right-&gt;color == BLACK &amp;&amp; helper-&gt;left-&gt;color == BLACK)
              {
                  helper-&gt;color = RED;
                  target = target-&gt;parent;
              }
              else if(helper-&gt;left-&gt;color== BLACK)
              {
                  helper-&gt;right-&gt;color = BLACK;
                  helper-&gt;color = RED;
                  left_rotate(root, helper, NIL);
                  helper = target-&gt;parent-&gt;left;
              }
              else
              {
                  helper-&gt;color = target-&gt;parent-&gt;color;
                  target-&gt;parent-&gt;color = BLACK;
                  helper-&gt;left-&gt;color = BLACK;
                  right_rotate(root, target-&gt;parent, NIL);
                  target = root;
              }
          }
      }
  
      target-&gt;color = BLACK;
  }
  
  void rbt_delete(rbt_node *&amp;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-&gt;left == NIL || victim-&gt;right == NIL)
              help_one = victim;
          else
              help_one = tree_succesor(victim, NIL);
  
          if(help_one-&gt;left != NIL)
              help_two = help_one-&gt;left;
          else
              help_two = help_one-&gt;right;
  
          help_two-&gt;parent = help_one-&gt;parent;
  
          if(help_one-&gt;parent == NIL)
              root = help_two;
          else if(help_one == help_one-&gt;parent-&gt;left)
              help_one-&gt;parent-&gt;left = help_two;
          else
              help_two-&gt;parent-&gt;right = help_two;
  
          if(help_one != victim)
          {
              victim-&gt;key = help_one-&gt;key;
              victim-&gt;data = help_one-&gt;data;
          }
  
          if(help_one-&gt;color == BLACK)
              delete_fixup(root, help_two, NIL);
      }
  
      root-&gt;color = BLACK;
  }
  </code></pre>