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 = ;
        parent->_bf = ;
    }
           

左單旋： 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 = ;
            parent->_bf = ;
        }
    }
           

左右雙旋： 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 == -)
        {
            subL->_bf = ;
            parent->_bf = ;
            subLR->_bf = ;
        }
        else if (bf == )
        {
            subL->_bf = -;
            parent->_bf = ;
            subLR->_bf = ;
        }
        else
        {
            subL->_bf = subLR->_bf = parent->_bf = ;
        }
    }
           

右左雙旋： 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 == )
        {
            subR->_bf = ;
            subRL->_bf = ;
            parent->_bf = -;
        }
        else if (bf == -)
        {
            subR->_bf = ;
            parent->_bf = ;
            subRL->_bf = ;
        }
        else
        {
            subR->_bf = subRL->_bf = parent->_bf = ;
        }
    }