title: Red-black tree - how to rotate if root is the grandparent?
body: <p>I am working on writing red-black tree myself. But when I test the rotation that involves root to be rotated, somewhat it loses reference.</p>
  
  <p>Tree structure:</p>
  
  <pre><code>          45             
          /    \
        40x      70        
       /  \     /
      7   41   50           
     / \
    6  39
  </code></pre>
  
  <p>The rotate logic says:
  "Rotate with 45(root) as top, in the direction that raises X (i.e. 40)"</p>
  
  <p>So this means right rotate and result should look like:</p>
  
  <pre><code>     40x  
      /   \
     7     45
   / \     / \
   6  39  41  70
             /
            50
  </code></pre>
  
  <p>Assuming that node 45 is grandparent and 7 is parent and 41 is current. (I know the order doesn't make sense but please ignore, this is because I've rotated once already)</p>
  
  <p>Code:</p>
  
  <pre><code>  //current is node 45
      //parent is node 7
      //grandparent is node 45 (root)
  
      //first detach cross node (i.e. 41)
      Node crossNode2 = grandparent.left.right;
      grandparent.left.right = null; //detach
  
  
                     45             
                  /     \
                40x      70        
               /  \      /
              7   null   50           
             / \
            6  39
  
      grandparent.left = null;
  
  
  
  
                     45             
                   /    \
                 null   70        
                        /
                      50           
  
      current.right = grandparent;
  
            40
          /    \
        7        45
       /  \     /  \
     6    39   null 70
                    /
                   50
  
      grandparent.left = crossNode2; //attach
  
  
           40  
          /   \
         7     45
       / \     / \
       6  39  41  70
                 /
                50
  </code></pre>
  
  <p>But somehow this code does not work. When I tested:</p>
  
  <pre><code>preorder
  45, 39, 70, 50
  breadth-first
  45, 39, 70, 50
  </code></pre>
  
  <p>So I think the result is actually:</p>
  
  <pre><code>  45
   /  \
  39  70
       /
      50
  </code></pre>
  
  <p>Could anyone give me tips what's wrong with my rotation code?</p>