def rotate_left(root, x):
    """Apply left rotation on x, and return the new root."""
    assert root and x and x.right
    y = x.right
    x.right = y.left
    if x.right:
        x.right.parent = x
    y.left = x
    y.parent = x.parent
    x.parent = y
    if not y.parent:
        root = y
    elif y.parent.left == x:
        y.parent.left = y
    elif y.parent.right == x:
        y.parent.right = y
    return root
