平衡搜索二叉树

[bosthhe1]

平衡搜索二叉树的核心就在于旋转，我的主要是靠平衡因子来判断旋转

[bosthhe1]

template<class K,class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V>* left;
    AVLTreeNode<K, V>* right;
    AVLTreeNode<K, V>* _parent;
    pair<K, V> vk;
    int bf;
    AVLTreeNode(const pair<K, V>& _vk)
        :left(nullptr)
        , right(nullptr)
        , _parent(nullptr)
        , vk(_vk)
        , bf(0)
    {}
};
template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> AVLNode;
public:
    AVLTree()
        :root(nullptr)
    {}
    bool insert(const pair<K, V>& _vk)
    {
        AVLNode* node = new AVLNode(_vk);
        if (root == nullptr)
        {
            swap(root, node);
            return true;
        }
        //root!=nullptr
        else
        {
            AVLNode* cur = root;
            AVLNode* parent = cur;
            while (cur)
            {
                parent = cur;
                if (node->vk.first > cur->vk.first)
                    cur = cur->right;
                else if (node->vk.first < cur->vk.first)
                    cur = cur->left;
                else
                    return false;
            }
            if (parent->vk.first>node->vk.first)
            {
                node->_parent = parent;
                parent->left = node;
                parent->bf--;
            }
            else
            {
                node->_parent = parent;
                parent->right = node;
                parent->bf++;
            }
            if (parent->bf == 0)
                return true;
            else if (parent->bf == (-1) || parent->bf == 1)
            {
                AVLNode* cur = parent;
                AVLNode* _parent = cur->_parent;
                while (_parent != nullptr)
                {
                    if (_parent->left == cur)
                        _parent->bf--;
                    else
                        _parent->bf++;
                    if (_parent == 0)
                        return true;
                    else if (_parent->bf == (-2) || _parent->bf == 2)
                    {
                        if (_parent->bf==-2&&cur->bf==-1)//右旋
                            RRotate(_parent);
                        else if (_parent->bf==2&&cur->bf ==1)//左旋
                        {
                            LRotate(_parent);
                        }
                        else if (_parent->bf == -2 && cur->bf == 1)//双旋(先左旋，后右旋)
                        {
                            LRPotate(_parent);
                        }
                        else if (_parent->bf == 2 && cur->bf == -1)//双旋(现右旋，后左旋)
                        {
                            RLPotate(_parent);
                        }
                        break;
                    }
                    else if (_parent->bf==(-3)||_parent->bf==3)
                        assert(false);
                    cur = _parent;
                    _parent = _parent->_parent;
                }
            }
        }
    }
    void RRotate(AVLNode* parent1)
    {
        AVLNode* parent = parent1;
        AVLNode* Grandparent = parent1->_parent;
        AVLNode* Sub = parent->left;
        AVLNode* Subr = Sub->right;
        parent->left = Subr;
        if(Subr)
        Subr->_parent = parent;
        Sub->right = parent;
        parent->_parent = Sub;
        Sub->_parent = Grandparent;
        if (Grandparent)
        {
            if (Grandparent->left == parent)
                Grandparent->left = Sub;
            else
                Grandparent->right = Sub;
        }
        else
        {
            Sub->_parent = nullptr;
            root = Sub;
        }
        Sub->bf = 0;
        parent->bf = 0;
    }
    void LRotate(AVLNode* parent1)
    {
        AVLNode* parent = parent1;
        AVLNode* Grandparent = parent1->_parent;
        AVLNode* Sub = parent->right;
        AVLNode* Subl = Sub->left;
        parent->right = Subl;
        if (Subl)
            Subl->_parent = parent;
        Sub->left = parent;
        parent->_parent = Sub;
        Sub->_parent = Grandparent;
        if (Grandparent)
        {
            if (Grandparent->left == parent)
                Grandparent->left = Sub;
            else
                Grandparent->right = Sub;
        }
        else
        {
            Sub->_parent = nullptr;
            root = Sub;
        }
        Sub->bf = 0;
        parent->bf = 0;
    }
    void RLPotate(AVLNode* cur)
    {
        AVLNode* left = cur;
        AVLNode* right = cur->right;
        int bf = right->left->bf;
        AVLNode* cur1 = right->left;
        RRotate(cur->right);
        LRotate(cur);
        if (bf == 1)
        {
            left->bf = -1;
            right->bf = 0;
            cur->bf = 0;
        }
        else if(bf == -1)
        {
            left->bf = 0;
            right->bf = 1;
            cur->bf = 0; 
        }
        else if (bf==0)
        {
            left->bf = 0;
            right->bf = 0;
            cur->bf = 0;
        }
        else
        {
            assert(false);
        }
    }
    void LRPotate(AVLNode* cur)
    {
        AVLNode* right = cur;
        AVLNode* left = cur->left;
        int bf = left->right->bf;
        LRotate(cur->left);
        RRotate(cur);
        if (bf == 1)
        {
            left->bf = 0;
            right->bf = -1;
            cur->bf = 0;
        }
        else if (bf == -1)
        {
            left->bf = 1;
            right->bf = 0;
            cur->bf = 0;
        }
        else if (bf==0)
        {
            left->bf = 0;
            right->bf = 0;
            cur->bf = 0;
        }
        else
        {
            assert(false);
        }
    }
    bool testTree()
    {
        return _testTree(root);
    }
    int _GetHight(AVLNode* root)
    {
        if (root == 0)
            return 0;
        int left = _GetHight(root->left);
        int right = _GetHight(root->right);
        return left > right ? left + 1 : right + 1;
    }
    private:
    bool _testTree(AVLNode* root)
    {
        if (root == nullptr)
            return true;
        int left = _GetHight(root->left)+1;
        int right = _GetHight(root->right)+1;
        if (abs(left - right) >= 2)
            return false;
        return _testTree(root->left)&&
        _testTree(root->right);
    }
private:
    AVLNode* root;
};