title: Red Black Tree - printing tree in preorder
body: <p>I've made red-black-tree implementation based on Cormen, but I must have broke something as it doesn't work like it should. I believe I rewrote Cormen correctly but I have no idea what is wrong then... How do I know that.. I took 10 values and checked how tree should look (http://secs.ceas.uc.edu/~franco/C321/html/RedBlack/redblack.html) and mine does look different. So I ask kindly for any tips that could help me find out what's wrong, whole code is pretty long, but I can't reproduce error without it, sorry about that. I believe guilty are rotate and/or fixup after insertion... </p>
  
  <p>EDIT: New code, but it still causes red and even black violations though I'm could swear I just rewrote pseudocode to C++...</p>
  
  <pre><code>#include &lt;cstdio&gt;
  #include &lt;algorithm&gt;
  #include &lt;string&gt;
  
  
  enum rbt_color { RED, BLACK };
  
  struct rbt_node
  {
      int key; //klucz
      int sub_tree; //wielkość poddrzewa
      std::string data; //wartość (napis do 21 znaków)
      rbt_node *left; //lewy syn
      rbt_node *right; //prawy syn
      rbt_node *parent;
      rbt_color color; //kolor
  };
  
  
  int is_RED(rbt_node *root)
  {
      return root != NULL &amp;&amp; root-&gt;color == RED;
  }
  
  int is_BLACK(rbt_node *root)
  {
      return root != NULL &amp;&amp; root-&gt;color == BLACK;
  }
  
  rbt_node *make_node(int key, std::string data)
  {
      rbt_node *new_node = new rbt_node; 
      new_node-&gt;key = key;
      new_node-&gt;data = data;
      new_node-&gt;color = RED;
      new_node-&gt;left = NULL;
      new_node-&gt;right = NULL;
      new_node-&gt;sub_tree = 1; //inicjalna wartość
      return new_node;
  }
  
  void add_node(rbt_node *&amp;tree, rbt_node *node, rbt_node *parent)
  {
          if(tree == NULL)
          {
              node-&gt;parent = parent;
              tree = node;
          }
          else if(node-&gt;key &lt; tree-&gt;key)
          {
              tree-&gt;sub_tree += 1;
              add_node(tree-&gt;left, node, tree);
          }
          else if(node-&gt;key &gt; tree-&gt;key)
          {
              tree-&gt;sub_tree += 1;
              add_node(tree-&gt;right, node, tree);
          }
  }
  
  
  //funkcja testująca drzewo, źródło http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx (trochę ulepszyłem)
  int rbt_assert (rbt_node *root)
  {
     int lh, rh;
  
     if ( root == NULL )
       return 1;
     else {
       rbt_node *ln = root-&gt;left;
       rbt_node *rn = root-&gt;right;
  
       /* Consecutive RED links */
       if ( is_RED ( root ) ) {
         if ( is_RED ( ln ) || is_RED ( rn ) ) {
           puts ( "RED violation" );
           printf("VIOLATION AT KEY: %d\n", root-&gt;key);
          //return 0;
         }
       }
  
       lh = rbt_assert ( ln );
       rh = rbt_assert ( rn );
  
       if (1 + (ln ? ln-&gt;sub_tree : 0) + (rn ? rn-&gt;sub_tree : 0) != root-&gt;sub_tree) 
       {
            puts ("Subtree violation");
            printf("VIOLATION AT KEY: %d\n", root-&gt;key);
            return 0;
       }
  
       if (root-&gt;left != NULL &amp;&amp; root-&gt;left-&gt;parent != root || root-&gt;right != NULL &amp;&amp; root-&gt;right-&gt;parent != root) 
       {
            puts ("Parent violation");
            printf("VIOLATION AT KEY: %d\n", root-&gt;key);
            return 0;
       }
  
       /* Invalid binary search tree */
       if ( ( ln != NULL &amp;&amp; ln-&gt;key &gt;= root-&gt;key )
         || ( rn != NULL &amp;&amp; rn-&gt;key &lt;= root-&gt;key ) )
       {
         puts ( "Binary tree violation" );
         return 0;
       }
  
       /* BLACK height mismatch */
       if ( lh != 0 &amp;&amp; rh != 0 &amp;&amp; lh != rh ) {
         puts ( "BLACK violation" );
         return 0;
       }
  
       /* Only count BLACK links */
       if ( lh != 0 &amp;&amp; rh != 0 )
         return is_RED ( root ) ? lh : lh + 1;
       else
         return 0;
     }
   }
  
  
  
  
  void left_rotate(rbt_node *&amp;root, rbt_node *&amp;node)
  {
      rbt_node *new_node = node-&gt;right;
      if(new_node != NULL)
      {
          node-&gt;right = new_node-&gt;left;
          if(new_node-&gt;left != NULL)
              new_node-&gt;left-&gt;parent = node;
  
          if(node-&gt;parent == NULL)
              root = new_node;
          else if(node == node-&gt;parent-&gt;left)
              node-&gt;parent-&gt;left = new_node;
          else
              node-&gt;parent-&gt;right = new_node;
  
          new_node-&gt;left = node;
  
          //aktualizujemy rozmiar poddrzewa
          new_node-&gt;sub_tree = node-&gt;sub_tree;
          node-&gt;sub_tree = 1;
          if(node-&gt;left != NULL)
              node-&gt;sub_tree += node-&gt;left-&gt;sub_tree;
          if(node-&gt;right != NULL)
              node-&gt;sub_tree += node-&gt;right-&gt;sub_tree;
  
          new_node-&gt;parent = node-&gt;parent;
          new_node-&gt;left-&gt;parent = new_node;
  
  
      }
  }
  
  void right_rotate(rbt_node *&amp;root, rbt_node *&amp; node)
  {
  
      rbt_node *new_node = node-&gt;left;
      if(new_node != NULL)
      {
          node-&gt;left = new_node-&gt;right;
          if(new_node-&gt;right != NULL)
              new_node-&gt;right-&gt;parent = node;
  
  
  
          if(node-&gt;parent == NULL)
              root = new_node;
          else if(node == node-&gt;parent-&gt;right)
              node-&gt;parent-&gt;right = new_node;
          else
              node-&gt;parent-&gt;left = new_node;
  
          new_node-&gt;right = node;
  
              //aktualizujemy rozmiar poddrzewa
          new_node-&gt;sub_tree = node-&gt;sub_tree;
          node-&gt;sub_tree = 1;
          if(node-&gt;left != NULL)
              node-&gt;sub_tree += node-&gt;left-&gt;sub_tree;
          if(node-&gt;right != NULL)
              node-&gt;sub_tree += node-&gt;right-&gt;sub_tree;
  
          new_node-&gt;parent = node-&gt;parent;
          new_node-&gt;right-&gt;parent = new_node;
  
      }
  }
  
  
  void add_rbt_node(rbt_node *&amp;root, int key, std::string data, rbt_node *parent)
  {
      rbt_node *element = make_node(key, data);
      add_node(root, element, parent);
      while(element != root &amp;&amp; element-&gt;parent-&gt;color == RED)
      {
          if(element-&gt;parent == element-&gt;parent-&gt;parent-&gt;left)
          {
              rbt_node *uncle = element-&gt;parent-&gt;parent-&gt;right;
              if(uncle != NULL &amp;&amp; uncle-&gt;color == RED)
              {
                  element-&gt;parent-&gt;color == BLACK;
                  uncle-&gt;color = BLACK;
                  element-&gt;parent-&gt;parent-&gt;color = RED;
                  element = element-&gt;parent-&gt;parent;
              }
              else
              {
                  if(element == element-&gt;parent-&gt;right)
                  {
                      element = element-&gt;parent;
                      left_rotate(root, element);
                  }
                  element-&gt;parent-&gt;color = BLACK;
                  element-&gt;parent-&gt;parent-&gt;color = RED;
                  right_rotate(root, element-&gt;parent-&gt;parent);
              }
          }
          else
          {
              rbt_node *uncle = element-&gt;parent-&gt;parent-&gt;left;
              if(uncle != NULL &amp;&amp; uncle-&gt;color == RED)
              {
                  element-&gt;parent-&gt;color = BLACK;
                  uncle-&gt;color = BLACK;
                  element-&gt;parent-&gt;parent-&gt;color = RED;
                  element = element-&gt;parent-&gt;parent;
              }
              else
              {
                  if(element == element-&gt;parent-&gt;left)
                  {
                      element = element-&gt;parent;
                      right_rotate(root, element);
                  }
                  element-&gt;parent-&gt;color = BLACK;
                  element-&gt;parent-&gt;parent-&gt;color = RED;
                  left_rotate(root, element-&gt;parent-&gt;parent);
              }
          }
      }
      root-&gt;color = BLACK;
  
  }
  
  void search_key(rbt_node *root, int key)
  {
      if(root == NULL)
          printf("-\n");
      else if(root-&gt;key == key)
          printf("%s\n", root-&gt;data.c_str());
      else if(root-&gt;key &lt; key)
          search_key(root-&gt;right, key);
      else if(root-&gt;key &gt; key)
          search_key(root-&gt;left, key);
  }
  
  void min_key(rbt_node *root, int number)
  {
      if(root != NULL)
      {
          int rank = 1;
          if(root-&gt;left != NULL)
              rank += root-&gt;left-&gt;sub_tree;
          if(rank == number)
              printf("%s\n", root-&gt;data.c_str());
          else if(number &lt; rank)
              min_key(root-&gt;left, number);
          else
              min_key(root-&gt;right, number - rank);
      }
  }
  
  void print_out(rbt_node *root)
  {
      if(root != NULL)
      {
          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 != NULL)
              printf("%d ",root-&gt;parent-&gt;key);
          else
              printf("- ");
          if(root-&gt;left != NULL)
              printf("%d ",root-&gt;left-&gt;key);
          else
              printf("- ");
          if(root-&gt;right != NULL)
              printf("%d ",root-&gt;right-&gt;key);
          else
              printf("- ");
          printf("\n");
  
          print_out(root-&gt;left);
          if(root-&gt;right != NULL)
          {
              print_out(root-&gt;right);
          }
      }
  }
  
  
  
  int main()
  {
  
      int key;
      char data [21];
      char operation;
      rbt_node *root = NULL;
      while(scanf("%c",&amp;operation) != EOF)
      {
          switch(operation)
          {
              case 'I':
                  scanf("%d",&amp;key);
                  scanf("%s",data);
                  add_rbt_node(root, key, data, NULL);
                  break;
              case 'S':
                  scanf("%d",&amp;key);
                  search_key(root, key);
                  break;
              case 'F':
                  scanf("%d",&amp;key);
                  if(key &lt;= root-&gt;sub_tree &amp;&amp; key != 0)
                      min_key(root, key);
                  else
                      printf("-\n");
                  break;
              case 'G':
                  printf("%d\n", rbt_assert(root));
                  break;
              case 'P':
                  //print_out(root);
                  break;
          }
      }
  }
  </code></pre>