private void rotateLeft(Node u)
    {
        int hookType;
        if (root == u)   hookType = 0;
        else if (u == u.parent.left)    hookType = -1;
        else    hookType = 1;
        Node nodesRight = u.right;
        Node rightsLeft = nodesRight.left;
        nodesRight.left = u;
        if (hookType == 0)  root = nodesRight;
        else
        {
            nodesRight.parent = u.parent;
            if (hookType == -1) u.parent.left = nodesRight;
            else    u.parent.right = nodesRight;
        }
        u.right = rightsLeft;
        if (rightsLeft != null)   rightsLeft.parent = u;
        u.parent = nodesRight;
    }