title: Red Black Tree insertion, I think I might have the rotations messed up
body: <p>I have been trying to create a red black tree that only implements an insert, search, and in-order traversal method so that I can compare it to a similar AVL tree I made previously. I have used all of the algorithms that are found in the Cormen text: Introduction to Algorithms, but for some reason I can't seem to get it to work correctly.</p>
  
  <p>For example, when I insert a, b, then c and try to do an in-order traversal, I am losing c. I have gone over the algorithms in the text about 10 times to make sure I have everything right and I can't seem to find any mistakes.</p>
  
  <p>Can anyone tell me if I am doing the <code>insertFix()</code> method correctly, as well as the rotations.</p>
  
  <p>Below is my header file to give you an idea of how I set up the nodes:</p>
  
  <pre><code>class RBT
  {
  private:
      struct node
      {
          int count;                  // counts the number of times the string has been inserted
          std::string  data;          // Storage for String Data
          node         *parent;       // pointer to this node's parent
          node         *LCH;          // pointer to this node's left child
          node         *RCH;          // pointer to this node's right child
          bool         isRed;         // bool value to specify color of node
      };
  
      node *root;                     // pointer to the tree's root node
      node *nil;                      // nil node used to implement RBT(aka sentinel)
      void traverse(node *t);         // perform an in-order traversal
      int  height(node *p);           // gets height of tree
      int  totalNodes(node *p);       // gets total nodes in tree
      int  totalWords(node *p);       // gets total words in tree
      void insertFix(node *z);        // fixes tree if RBT rules are broken
      void RR(node *z);               // performs Right rotation at z
      void LR(node *z);               // performs Left rotation at z
  
  public:
      int  insert(std::string str);   // tries to add str to tree.  Returns the new count for str
      int  search(std::string str);   // searches for str.  Returns count for str, 0 if not found
      void list();                    // prints in-order traversal of tree  
      void getHeight();               // prints the height of tree
      void getTotal();                // prints the total number of nodes in the tree, as well as total number of words
      void getComparisons();          // prints the number of comparisons used
      RBT();                          // constructor -- just builds an empty tree with a NULL root pointer
      int  numComp;                   // tracks number of comparisons, only counts for search and insert commands
  };
  </code></pre>
  
  <p>And here is my <code>insertFix()</code> method, which is ran after a normal insertion that you would find in any ordinary binary search tree:</p>
  
  <pre><code>void RBT::insertFix(node *z)
  {
      // Private method to fix any rules that might be broken in the RBT.
      // Takes a starting node z, as an input parameter and returns nothing,
      // except for a happy feeling knowing the you are not breaking any RBT laws.
      // Definitions of placeholder nodes used in this method:
      // z  = z
      // y  = left or right uncle of z  
  
      node *y;
  
      while (z-&gt;parent-&gt;isRed)
      {
          if(z-&gt;parent == z-&gt;parent-&gt;parent-&gt;LCH)
          {
              y = z-&gt;parent-&gt;parent-&gt;RCH;
              if(y-&gt;isRed)
              {
                  z-&gt;parent-&gt;isRed = false;
                  y-&gt;isRed = false;
                  z-&gt;parent-&gt;parent-&gt;isRed = true;
                  z = z-&gt;parent-&gt;parent;
              }
              else
              {
                  if( z == z-&gt;parent-&gt;RCH)
                  {
                      z = z-&gt;parent;
                      RBT::LR(z);
                  }
                  z-&gt;parent-&gt;isRed = false;
                  z-&gt;parent-&gt;parent-&gt;isRed = true;
                  RBT::RR(z);
              }
          }
          else
          {
              y = z-&gt;parent-&gt;parent-&gt;LCH;
              if(y-&gt;isRed)
              {
                  z-&gt;parent-&gt;isRed = false;
                  y-&gt;isRed = false;
                  z-&gt;parent-&gt;parent-&gt;isRed = true;
                  z = z-&gt;parent-&gt;parent;
              }
              else
              {
                  if( z == z-&gt;parent-&gt;LCH)
                  {
                      z = z-&gt;parent;
                      RBT::RR(z);
                  }
                  z-&gt;parent-&gt;isRed = false;
                  z-&gt;parent-&gt;parent-&gt;isRed = true;
                  RBT::LR(z);
              }
          }
      }
      root-&gt;isRed = false;
  }
  </code></pre>
  
  <p>Below are my two rotation methods, one is a Right Rotation (RR), and the other is a Left Rotation (LR):</p>
  
  <pre><code>void RBT::LR(node *x)
  {
      // Method to perform a Left Rotation at Node z. Takes a node pointer
      // as a parameter. Returns void.
  
      node *y; // y is x's right child
      y = x-&gt;RCH;
      x-&gt;RCH = y-&gt;LCH;
      if (y-&gt;LCH != nil) {y-&gt;LCH-&gt;parent = x;}
      y-&gt;parent = x-&gt;parent;
      if (x-&gt;parent == nil) {root = y;}
      else
      {
          if (x == x-&gt;parent-&gt;LCH) {x-&gt;parent-&gt;LCH = y;}
                              else {x-&gt;parent-&gt;RCH = y;}
      }
      y-&gt;LCH = x;
      x-&gt;parent = y;
  }
  
  void RBT::RR(node *x)
  {
      // Method to perform a Left Rotation at Node z. Takes a node pointer
      // as a parameter. Returns void.
  
      node *y; // y is x's left child
      y = x-&gt;LCH;
      x-&gt;LCH = y-&gt;RCH;
      if (y-&gt;RCH != nil) {y-&gt;RCH-&gt;parent = x;}
      y-&gt;parent = x-&gt;parent;
      if (x-&gt;parent == nil) {root = y;}
      else
      {
          if (x == x-&gt;parent-&gt;RCH) {x-&gt;parent-&gt;RCH = y;}
                              else {x-&gt;parent-&gt;LCH = y;}
      }
      y-&gt;RCH = x;
      x-&gt;parent = y;
  }
  </code></pre>
  
  <p>I know this is a lot of code to look over, but I am at my wits end trying to find out what I am doing wrong. I have a feeling I am messing up the pointers somewhere in one of the rotations but I can't figure out where. Any help would be really appreciated!</p>