Red-black tree - how to turn if the root is grandfather?

Question

I am writing red-black wood. But when I test the rotation, which includes the root to be rotated, it loses the link somewhat.

Tree structure:

          45             
        /    \
      40x      70        
     /  \     /
    7   41   50           
   / \
  6  39

The logic of rotation says: "Turn with 45 (root) as the top, in the direction that X raises (i.e. 40)"

So this means you need to rotate, and the result should look like this:

     40x  
    /   \
   7     45
 / \     / \
 6  39  41  70
           /
          50

Assuming node 45 is grandfather, and 7 is parent and 41 is current. (I know that order does not make sense, but please ignore this because I have already turned once)

the 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

But for some reason this code does not work. When I tested:

preorder
45, 39, 70, 50
breadth-first
45, 39, 70, 50

So, I think the result is actually:

  45
 /  \
39  70
     /
    50

Can someone give me advice on what happened to my rotation code?

Answer 1

node Q:

• P = Q .
• Q left child = P
• P Q
• P = Q

. , , node . , , Q - , - null. "" node, node . , .

public static void rotateRight(Node node) {
    assert(!node.isLeaf() && !node.left.isLeaf());
    final Node child = node.left;
    node.setLeft(child.right);
    if (node.isRightChild())
         node.parent.setRight(child);
    else node.parent.setLeft(child);
    child.setRight(node);
}

Node, setRight setLeft parent, right left. node.isRightNode() (node.parent.right == node).

Answer 2

Gunslinger47, . . (, , ..)

:)

http://masatosan.com/btree.jsp

public static void rotateLeft(Node node) {
    assert(!node.isLeaf() && !node.right != null);
    final Node child = node.right;
    node.setRight(child.left);
    if(node.isLeftChild()) {
        node.parent.setLeft(child);
    }
    else {
        node.parent.setRight(child);
    }
    chlid.setLeft(node);
}