AVL树的实现

#include
#include

template
struct AVL
{
    typedef avlnode node;
public:
    AVL()
    {
        _root = nullptr;
    }
    bool insert(const pairkv)
    {
        if (_root == nullptr)                       //1.按照搜索二叉树进行插入   再调整
        {
            _root = new node(kv);
            return true;
        }
        node* cur = _root;
        node* parent = nullptr;
        while (cur)
        {
            if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }
        cur = new node(kv);
        if (parent->_kv.first > cur->_kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        //更新_bf;

        while (parent)
        {
            if (parent->_left == cur)
            {
                parent->_bf--;
            }
            else if(parent->_right==cur)
            {
                parent->_bf++;
            }

            if(parent->_bf==0)
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                cur = parent;
                parent = parent->_parent;
            }
            else if(parent->_bf==2||parent->_bf==-2)    //调整平衡
            {
                //1、左旋转
                if (parent->_bf == -2 && parent->_left->_bf== -1)  
                {
                    rotatel(parent);
                }
                else if (parent->_bf == 2&&parent->_right->_bf == 1)   //2.右旋转
                {
                    rotater(parent);
                }
                else if (parent->_bf == -2 && parent->_left->_bf == 1)      //3.双旋转
                {
                    node* subL = parent->_left;
                    node* subLR = subL->_right;
                    int bf = subLR->_bf;

                    rotater(parent->_right);
                    rotatel(parent);

                    if (bf == 1)
                    {
                        parent->_bf = -1;
                        subL->_bf = 0;
                        subLR->_bf = 0;
                    }
                    else if (bf == -1)
                    {
                        parent->_bf = 0;
                        subL->_bf = 1;
                        subLR->_bf = 0;
                    }
                    else if (bf == 0)
                    {
                        parent->_bf = 0;
                        subL->_bf = 0;
                        subLR->_bf = 0;
                    }
                    else
                    {
                        assert(false);
                    }
                }
                else if(parent->_bf==2&&parent->_right->_bf==-1)
                {
                    node* subR = parent->_right;
                    node* subRL = subR->_left;
                    int bf = subRL->_bf;

                    rotatel(parent->_left);
                    rotater(parent);

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

        }

    }
    void rotatel(node* parent)
    {
        node* subl = parent->_left;
        node* sublr = subl->_right;
        parent->_left = sublr;
        if (sublr != nullptr)
        {
            sublr->_parent = parent;
        }
        node* parentP = parent->_parent;
        subl->_right = parent;
        parent->_parent = subl;
        if (parent==_root)
        {
            _root = subl;
            _root->_parent = nullptr;
        }
        else if (parentP->_left == parent)
        {
            parentP->_left = subl;
            subl->_parent = parentP;
        }
        else
        {
            parentP->_right = subl;
            subl->_parent = parentP;
        }

        parent->_bf = subl->_bf = 0;
    }

    void rotater(node* parent)
    {
        node* subr = parent->_right;
        node* subrl = subr->_left;
        parent->_right = subrl;
        if (subrl->_left != nullptr)
        {
            subrl->_parent = parent;
        }
        subr->_left = parent;
        node* parentP = parent->_parent;
        parent->_parent = subr;
        if (parent == _root)
        {
            _root = subr;
            _root->_parent = nullptr;
        }
        else if (parentP->_left == parent)
        {
            parentP->_left = subr;
            subr->_parent = parentP;
        }
        else
        {
            parentP->_right = subr;
            subr->_parent = parentP;
        }
        parent->_bf = 0;
        subr->_bf = 0;
    }
    void orled()
    {
        _orled(_root);
    }
    void _orled(const node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _orled(root->_left);
        cout << root->_kv.first << " : " << root->_kv.second << endl;
        _orled(root->_right);
    }
private:
    node* _root;
};
int main()
{

    AVLa;
    for (int i = 10; i >= 0; i--)
    {
        a.insert(make_pair(i, i));
    }
    a.orled();

    return 0;
}