Left rotation in red black trees

Question

I have been going through Red Black Trees described in Algorithms by Robert Sedgewick. Here is the code for insertion in the red black tree.

public void put(Key key, Value val) {
    root = put(root, key, val);
    root.color = BLACK;
    assert check();
}

// insert the key-value pair in the subtree rooted at h
private Node put(Node h, Key key, Value val) { 
    if (h == null) return new Node(key, val, RED, 1);

    int cmp = key.compareTo(h.key);
    if      (cmp < 0) h.left  = put(h.left,  key, val); 
    else if (cmp > 0) h.right = put(h.right, key, val); 
    else              h.val   = val;

    // fix-up any right-leaning links
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
    h.N = size(h.left) + size(h.right) + 1;

    return h;
} 

Here is an image to visualize the red black fix up. Consider the case , when the item to be inserted is in middle of the top 3-node . We have to perform three operations as given in the three ifstatements namely, h=rotateLeft(h), h=rotateRight(h) and flipcolors(h). The problem is that when we assign h = rotateLeft(h). the node returned is the pointer to the middle node in the three nodes with two consecutive left red links. But the algorithm assumes that the node returned is the top node in the 3-nodes with 2 consecutive left red links. So, when we again rotateRight(h) we end up with the same position we started with. May be I have not understood the algorithm.

Here is the code for rotateLeft(h)

private Node rotateLeft(Node h) {
    assert (h != null) && isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = x.left.color;
    x.left.color = RED;
    x.N = h.N;
    h.N = size(h.left) + size(h.right) + 1;
    return x;
}

Please help me understand how h=rotateLeft(h) gives the top node instead of the middle node in the three nodes with two consecutive red left links.

Answer 1

I finally understood how the algorithm works. after h=rotateLeft(h), the second and third if statements evaluate to false. and h is returned. One level up the recursion, We get h.left =h where h on the left of the equality, is the top level node in the three nodes with two consecutive red left links. Then the first if statement evaluates to false, the second if statement evaluates to true and we do a right rotate, then we do the flip colors.

Please correct me if I am wrong.