AVLtree平衡二叉树

1.
以下四种方式时需要旋转

template<class K,class V>
struct AVLTreeNode
{
    AVLTreeNode(const K& key,const V& value)
        :_left(NULL)
        ,_right(NULL)
        ,_parent(NULL)
        ,_key(key)
        ,_value(value)
        ,_bf(0)
    {}
    AVLTreeNode<K,V>* _left;
    AVLTreeNode<K,V>* _right;
    AVLTreeNode<K,V>* _parent;
    K _key;
    V _value;
    int _bf;//平衡因子
};
template<class K,class V>
class AVLTree
{
    typedef AVLTreeNode<K,V> Node;
public:
    AVLTree()
        :_root(NULL)
    {}
    bool Insert(const K& key,const V& value)
    {
        if(_root == NULL)
        {
            _root = new Node(key,value);
            return true;
        }
        //插入
        Node *cur = _root;
        Node *parent = NULL;
        while(cur)
        {
            if(key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(key,value);
        if(key > parent->_key)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        //调整平衡因子
        bool IsRotate = false;
        while(parent)
        {
            if(parent->_left == cur)
            {
                parent->_bf--;
            }
            else
            {
                parent->_bf++;
            }
            if(parent->_bf == 0)
            {
                break;
            }
            else if(parent->_bf == 1||parent->_bf == -1)
            {
                cur = parent;
                parent = cur->_parent;
            }
            else
            {
                IsRotate = true;
                if(parent->_bf == 2)
                {
                    if(cur->_bf == 1)
                    {
                        RotateL(parent);
                    }
                    else//cur->_bf == -1
                    {
                        RotateRL(parent);
                    }
                }
                else//parent->_bf == -2
                {
                    if(cur->_bf == -1)
                    {
                        RotateR(parent);
                    }
                    else//cur->_bf == 1
                    {
                        RotateLR(parent);
                    }
                }
                break;
            }
        }
        if(IsRotate)
        {
            Node* GrandParent = parent->_parent;
            if(GrandParent == NULL)
            {
                _root = parent;
            }
            else
            {
                if(parent->_key < GrandParent->_key)
                {
                    GrandParent->_left = parent;
                }
                else
                {
                    GrandParent->_right = parent;
                }
            }
        }
        return true;
    }
    void InOrder()
    {
        _InOrder(_root);
        cout<<endl;
    }
    bool IsBalance()
    {
        return _IsBalance(_root);
    }

protected:
    int _Height(Node* root)
    {
        if(root == NULL)
        {
            return 0;
        }
        int left = _Height(root->_left) + 1;
        int right = _Height(root->_right) + 1;
        return (left>right)?left:right;
    }
    bool _IsBalance(Node* root)
    {
        if(root == NULL)
        {
            return true;
        }
        int left = _Height(root->_left);
        int right = _Height(root->_right);

        int bf = left - right;
        if(abs(bf) > 1)
        {
            return false;
        }
        if(abs(bf) != abs(root->_bf))
        {
            cout<<root->_key<<"平衡因子出错！"<<endl;
            return false;
        }
        return _IsBalance(root->_left)&&_IsBalance(root->_right);
    }
    void _InOrder(Node* root)
    {
        if(root == NULL)
            return;
        _InOrder(root->_left);
        cout<<root->_key<<" ";
        _InOrder(root->_right);
    }
    void RotateL(Node*& parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if(subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        subR->_parent = parent->_parent;

        parent->_parent = subR;
        parent->_bf = subR->_bf = 0;

        parent = subR;

    }
    void RotateR(Node*& parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if(subLR)
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
        subL->_parent = parent->_parent;

        parent->_parent = subL;
        parent->_bf = subL->_bf = 0;

        parent = subL;
    }
    void RotateLR(Node*& parent)
    {
        RotateL(parent->_left);
        RotateR(parent);
    }
    void RotateRL(Node*& parent)
    {
        RotateR(parent->_right);
        RotateL(parent);
    }
protected:
    Node* _root;
};

测试：

void test()
{
    AVLTree<int,int> t;
    int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
    for(int i = 0;i < sizeof(a)/sizeof(int);++i)
    {
        t.Insert(a[i],i);
    }
    t.InOrder();
    cout<<"IsBalance?"<<t.IsBalance()<<endl;
}
void test2()
{
    AVLTree<int,int> t;
    int a[]={4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for(int i = 0;i < sizeof(a)/sizeof(int);++i)
    {
        t.Insert(a[i],i);
    }
    t.InOrder();
    cout<<"IsBalance?"<<t.IsBalance()<<endl;
}

可以看到第二个测试用例并不符合，所以由此知道RL,LR不可以直接调用上面的来旋转，要调整平衡因子，不然插着插着就出错了。
  乖乖来写RL,LR吧。

void RotateRL(Node*& parent)
    {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;
        subR->_left = subRL->_right;

        if (subRL->_right != NULL)
        {
            subRL->_right->_parent = subR;
        }
        subRL->_right = subR;
        subR->_parent = subRL;

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

        parent->_right = subRL->_left;

        if (subRL->_left != NULL)
        {
            subRL->_left->_parent = parent;
        }
        subRL->_left = parent;
        subRL->_parent = parent->_parent;
        parent->_parent = subRL;
        if (subRL->_bf == 0 || subRL->_bf == -1)
        {
            parent->_bf = 0;
        }
        else
        {
            parent->_bf = -1;
        }
        parent = subRL;
        subRL->_bf = 0;
    }

    void RotateLR(Node*& parent)
    {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;
        subL->_right = subLR->_left;

        if (subLR->_left != NULL)
        {
            subLR->_left->_parent = subL;
        }
        subLR->_left = subL;
        subL->_parent = subLR;

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

        parent->_left = subLR->_right;

        if (subLR->_right != NULL)
        {
            subLR->_right->_parent = parent;
        }
        subLR->_right = parent;
        subLR->_parent = parent->_parent;
        parent->_parent = subLR;
        if (subLR->_bf == 0 || subLR->_bf == 1)
        {
            parent->_bf = 0;
        }
        else
        {
            parent->_bf = 1;
        }
        parent = subLR;
        subLR->_bf = 0;

    }