平衡二叉树-旋转

旋转分为左旋转与右旋转，左右旋转与右左旋转
我都在图片里表示：

//右旋转，这里传入的为图中的b点

    {
        Node *grandfather = father->_father;
        Node *great_father = grandfather->_father;

        grandfather->_left = father->_right;
if (father->_right != NULL)
            father->_right->_father = grandfather;

        father->_right = grandfather;
        grandfather->_father = father;
//判段是否为头结点,事实上这里的头节点会被修改，你应该传入 
// root引用来修改root
if (NULL != great_father)
        {
if (great_father->_left == grandfather)
                great_father->_left = father;
else great_father->_right = father;
        }
        father->_father = great_father;
    }

//father为图中b点
void rotate_left(Node *father)
{
Node *grandfather = father->_father;
Node *great_father = grandfather->_father;

    grandfather->_right = father->_left;
    if (father->_left != NULL)
        father->_left->_father = grandfather;

    father->_left = grandfather;
    grandfather->_father = father;
    //判段是否为头结点,事实上这里的头节点会被修改，你应该传入         
    //  root引用来修改root
    if (NULL != great_father)
    {
        if (great_father->_left == grandfather)
            great_father->_left = father;
        else great_father->_right = father;

    }
    father->_father = great_father;

}

//先对b,c进行左旋，在对c,a进行右旋
void rotate_left_right(Node *father)
    {
        father = father->_right;
        rotate_left(father);
        rotate_right(father);
    }

//与左右旋转同理
void rotate_right_left(Node *father)
    {
        father = father->_left;
        rotate_right(father);
        rotate_left(father);
    }

**特别补充：**A, B, C, D四个点也可能表示子树。