AVL树(平衡搜索二叉树)

二叉搜索树具有很高的灵活性，，对其进行优化可以生成平衡搜索二叉树。
AVL树为高度平衡的二叉搜索树，能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。
AVL树增删查改的效率都是O(lgN)。

AVL树的特性：
左子树和右子树高度之差绝对值不超过1；
树中的每个左子树和右子树都应该是AVL树；每个节点都有一个平衡因子，任一节点的平衡因子都等于右子树高度减去左子树高度，且平衡因子是-1 0 1.

AVL树的插入：
插入操作和二叉搜索树的插入操作基本相同，不同的是AVL树在插入数据之后需要对每个节点的平衡因子进行判断(每个节点的平衡因子)分为以下三种情况：
循环的条件是parent存在：

1.当新插入节点的父亲节点的平衡因子_bf==0，return true插入成功；
2.当新插入节点的父亲节点的平衡因子_bf==1|_bf==-1，需要往上不断进行更新，cur=parent;parent=cur->parent;；
3.当新插入节点的父亲节点的平衡因子_bf==2|_bf==-2，这是需要根据情况进行旋转：

右单旋： parent->_bf==-2 cur->_bf==-1

说明：当此时的parent已经是整棵树的根节点的时候，subL=parent；如果存在pparent，还需要判断subL位于pparent的左子树还是右子树。
调节完成后需要将subL和parent的平衡因子置0.

    void Rotate_R(Node* parent)
    {
        Node* ppNode = parent->_parent;
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
        parent->_parent = subL;
        if (_root == parent)
        {
            _root = subL;
            subL->_parent = NULL;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subL;
                subL->_parent = ppNode;
            }
            else
            {
                ppNode->_right = subL;
                subL->_parent = ppNode;
            }
        }
        subL->_bf = 0;
        parent->_bf = 0;
    }

左单旋： parent->_bf==2 cur->_bf==1

说明：当此时的parent已经是整棵树的根节点的时候，subR=parent；如果存在pparent，还需要判断subR位于pparent的左子树还是右子树。
调节完成后需要将subR和parent的平衡因子置0。

void Rotate_L(Node* parent)
    {
        Node* ppNode = parent->_parent;
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        parent->_parent = subR;
        if (_root == parent)
        {
            _root = subR;
            subR->_parent = NULL;
        }
        else
        {
            //这里还需判断parent是在ppNode的左子树还是右子树
            if (parent == ppNode->_left)
            {
                ppNode->_left = subR;
                subR->_parent = ppNode;
            }
            else
            {
                ppNode->_right = subR;
                subR->_parent = ppNode;
            }
            subR->_bf = 0;
            parent->_bf = 0;
        }
    }

左右双旋： parent->_bf==-2 cur->_bf==1

void Rotate_LR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;

        Rotate_L(subL);
        Rotate_R(parent);

        if (bf == -1)
        {
            subL->_bf = 0;
            parent->_bf = 1;
            subLR->_bf = 0;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            parent->_bf = 0;
            subLR->_bf = 0;
        }
        else
        {
            subL->_bf = subLR->_bf = parent->_bf = 0;
        }
    }

右左双旋： parent->_bf==2 cur->_bf==-1

void Rotate_RL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subR->_bf;

        Rotate_R(subR);
        Rotate_L(parent);

        if (bf == 1)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            subR->_bf = 1;
            parent->_bf = 0;
            subRL->_bf = 0;
        }
        else
        {
            subR->_bf = subRL->_bf = parent->_bf = 0;
        }
    }