AVL平衡樹的旋轉

AVL樹是一種平衡查找樹（每個節點左子樹與右子樹的高度差不超過1），這樣可以保證樹不偏向一邊，使查找的時間複雜度降低。

需要給節點一個平衡因子_bf(右子樹的高度減去左子樹的高度)。

AVL樹的插入分為下面幾種情況：

在父節點的右子樹插入節點，父節點的bf+1，如果父節點bf等于0,樹平衡，插入成功，父節點bf等于1，右子樹高度加1，接着向上調整。

在父節點的左子樹插入節點，父節點的bf-1，如果父節點bf等于0,樹平衡，插入成功，父節點bf等于-1，左子樹高度加1，接着向上調整。

如果父節點的bf為2或者-2，樹不平衡，進行旋轉。

在較高右子樹的右邊插入節點需要進行左旋轉。

pCur為插入節點，parent的bf為2，這時候把SubR提高,parent降低,重新滿足平衡條件。

如果原右子樹SubR的左子樹SubRL不為空，SubR的左子樹需要指向parent,是以把SubRL連到parent的右子樹上。重新滿足平衡。

–》

左單旋與右單旋為鏡像，旋轉方法相同，介紹省略。。

當父節點的bf為2,右子樹的bf為-1,用上面方法沒法一次旋轉完成。（在較高右子樹的左側插入節點使進行右左雙旋）。

先對SubR進行右單旋。

最後平衡

左右雙旋為右左雙旋的鏡像，省略。。

代碼實作：

#include <iostream>
using namespace std;
#include <assert.h>
#include <stdlib.h>

template <class K, class V>
struct AVLTreeNode
{
    AVLTreeNode(const K& key = K(), const V& value = V())
        :_key(key)
        , _value(value)
        , _pLeft(NULL)
        , _pRight(NULL)
        , _parent(NULL)
        , _bf()
    {}
    AVLTreeNode *_pLeft;
    AVLTreeNode *_pRight;
    AVLTreeNode *_parent;
    K _key;
    V _value;
    int _bf;

}; 

template <class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V>   Node;
public:
    AVLTree()
        :_pRoot(NULL)
    {}

    bool Insert(const K& key, const V& value)
    {
        if (NULL == _pRoot)
        {
            _pRoot = new Node(key, value);
            return true;
        }
        Node *pCur = _pRoot;
        Node *parent = NULL;
        while (pCur)
        {
            if (key < pCur->_key)
            {
                parent = pCur;
                pCur = pCur->_pLeft;
            }
            else if (key > pCur->_key)
            {
                parent = pCur;
                pCur = pCur->_pRight;
            }
            else
                return false;
        }

        pCur = new Node(key, value);
        if (key < parent->_key)
        {
            parent->_pLeft = pCur;
            --parent->_bf;
        }
        else
        {
            parent->_pRight = pCur;
            ++parent->_bf;
        }
        pCur->_parent = parent;

        while (parent && parent->_bf != )
        {
            if (parent->_bf == )
            {
                if (pCur->_bf == )
                    _RotateL(parent);
                else
                    _RotateRL(parent);
                return true;
            }
            else if (parent->_bf == -)
            {
                if (pCur->_bf == -)
                    _RotateR(parent);
                else
                    _RotateLR(parent);
                return true;
            }

            if (parent->_bf == )
            {
                pCur = parent;
                parent = parent->_parent;
                if (parent)
                    ++parent->_bf;
                else
                    return true;
            }
            else if (parent->_bf == -)
            {
                pCur = parent;
                parent = parent->_parent;
                if (parent)
                    --parent->_bf;
                else
                    return true;
            }
        }
    }

    bool IsBalance()
    {
        return IsBalanceTree(_pRoot);
    }

 void InOrder()
    {
        cout << "中序：";
        _InOrder(_pRoot);
        cout << "end" << endl;
    }
private:    
    void  _RotateL(Node* parent)
    {
        Node *SubR = parent->_pRight;
        Node *SubRL = SubR->_pLeft;

        parent->_pRight = SubRL;
        if (SubRL != NULL)
        SubRL->_parent = parent;

        Node *pPParent = parent->_parent;

        parent->_parent = SubR;
        SubR->_pLeft = parent;
        SubR->_parent = pPParent;

        if (NULL == pPParent)
            _pRoot = SubR;
        else if (pPParent->_pLeft == parent)
        {
            pPParent->_pLeft = SubR;
        }
        else
        {
            pPParent->_pRight = SubR;
        }

        SubR->_bf = ;
        parent->_bf = ;
    }

    void  _RotateR(Node* parent)
    {
        Node *SubL = parent->_pLeft;
        Node *SubLR = SubL->_pRight;
        parent->_pLeft = SubLR;
        if (SubLR != NULL)
            SubLR->_parent = parent;

        Node *pPParent = parent->_parent;

        parent->_parent = SubL;
        SubL->_pRight = parent;
        SubL->_parent = pPParent;

        if (NULL == pPParent)
            _pRoot = SubL;
        else if (pPParent->_pLeft == parent)
        {
            pPParent->_pLeft = SubL;
        }
        else
        {
            pPParent->_pRight = SubL;
        }

        SubL->_bf = ;
        parent->_bf = ;
    }

    void _RotateRL(Node *parent)
    {
        _RotateR(parent->_pRight);
        _RotateL(parent);
        parent->_pRight->_bf = -;
    }

    void _RotateLR(Node *parent)
    {
        _RotateL(parent->_pLeft);
        _RotateR(parent);
        parent->_pLeft->_bf = ;
    }

    void _InOrder(Node *proot)
    {
        if (NULL == proot)
            return;
        _InOrder(proot->_pLeft);
        cout << proot->_value << " ";
        _InOrder(proot->_pRight);
    }

    int Hight(Node *proot)
    {
        if (NULL == proot)
            return ;
        if (proot->_pLeft == NULL && proot->_pRight == NULL)
            return ;
        int LeftHight = Hight(proot->_pLeft);
        int RightHight = Hight(proot->_pRight);
        return  + ((LeftHight > RightHight) ? LeftHight : RightHight);
    }

    bool IsBalanceTree(Node *proot)
    {
        if (NULL == proot)
            return true;
        if (proot->_bf >=  || proot->_bf <= -)
        {
            cout << proot->_key<<"平衡因子大于2！" << endl;
            return false;
        }
        if (Hight(proot->_pRight) - Hight(proot->_pLeft) != proot->_bf)
        {
            cout <<proot->_key<<"  平衡因子不正确!" << endl;
            return false;
        }
        if (IsBalanceTree(proot->_pLeft) && IsBalanceTree(proot->_pRight))
            return true;
    }
private:
    Node *_pRoot;
};
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    AVLTree<int, int> avtree;
    for (int i = 0; i < sizeof(arr) / sizeof(arr[]); ++i)
    {
        avtree.Insert(arr[i], arr[i]);
        avtree.IsBalance();
    }
    avtree.InOrder();
    getchar();
    return 0;
}