AVL树

AVL树是一种自平衡二叉排序树，它的特点是任何一个节点的左子树高度和右子树的高度差在-1,0,1三者之间。AVL树的任何一个子树都是AVL树。

旋转

插入操作：

template<typename T>
struct BiTNode{
    T val;
    int h;
    BiTNode *left,*right;
    BiTNode(){}
    BiTNode(T val):val(val){
        left=NULL;right=NULL;
    }
};


template<typename T,typename node=BiTNode<T>>
class AVL
{
    public:

    AVL():n(0),root(NULL){}
    AVL(T *bg,T *ed):n(0),root(NULL){while(bg!=ed)insert(*bg++);}
    ~AVL(){clear(root);}
    void insert(const T& key){insert(root,key);}
    void clear(){clear(root);}
    int size()const{return n;}
    bool empty()const{return n==0;}
    int leaf()const{return leaf(root);}
    vector<T> DLR(){vector<T>v;DLR(root,v);return v;}
    vector<T> LDR(){vector<T>v;LDR(root,v);return v;}
    vector<T> LRD(){vector<T>v;LRD(root,v);return v;}
    vector<T> _DLR(){vector<T>v;_DLR(root,v);return v;}
    vector<T> _LDR(){vector<T>v;_LDR(root,v);return v;}
    vector<T> _LRD(){vector<T>v;_LRD(root,v);return v;}
    vector<T> bfs(){vector<T>v;bfs(root,v);return v;}
    int max_height()const{return height(root);}
    void erase(const T& key){erase(root,key);}
    bool find(const T& key)const{return search(key)!=NULL;}

private:
    void bfs(node *Tree,vector<T>&v)
    {
        if(Tree==NULL)return;
        queue<node*>q;
        q.push(Tree);
        while(!q.empty())
        {
            node *p=q.front();
            v.push_back(p->val);
            q.pop();
            if(p->left)q.push(p->left);
            if(p->right)q.push(p->right);
        }
    }
    void DLR(node *Tree,vector<T>&v)
    {
        if(Tree==NULL){return ;}
        v.push_back(Tree->val);
        DLR(Tree->left,v);
        DLR(Tree->right,v);
    }
    void LDR(node *Tree,vector<T>&v)
    {
        if(Tree==NULL){return ;}
        LDR(Tree->left,v);
        v.push_back(Tree->val);
        LDR(Tree->right,v);
    }
    void LRD(node *Tree,vector<T>&v)
    {
        if(Tree==NULL){return ;}
        LRD(Tree->left,v);
        LRD(Tree->right,v);
        v.push_back(Tree->val);
    }
    void _DLR(node *Tree,vector<T>&v)
    {
        stack<node*>Stack;
        node *p=Tree;
        while(p!=NULL||!Stack.empty())
        {
            if(p)
            {
                v.push_back(p->val);
                Stack.push(p);
                p=p->left;
            }
            else
            {
                p=Stack.top();
                Stack.pop();
                p=p->right;
            }
        }
    }
    void _LDR(node *Tree,vector<T>&v)
    {
        stack<node*>Stack;
        node *p=Tree;
        while(p!=NULL||!Stack.empty())
        {
            if(p)
            {
                Stack.push(p);
                p=p->left;
            }
            else
            {
                p=Stack.top();
                Stack.pop();
                v.push_back(p->val);
                p=p->right;
            }
        }
    }
    void _LRD(node *Tree,vector<T>&v)
    {
        stack<node*>Stack;
        Stack.push(Tree);
        node *pre,*cur;
        cur=pre=NULL;
        while(!Stack.empty())
        {
            cur=Stack.top();
            if((cur->left == NULL && cur->right == NULL) \
            || (pre != NULL && (pre == cur->left || pre == cur->right)))
            {
                v.push_back(cur->val);
                cur=Stack.top();
                Stack.pop();
                pre=cur;
            }
            else
            {
                if(cur->right!=NULL)Stack.push(cur->right);
                if(cur->left!=NULL)Stack.push(cur->left);
            }
        }
    }
    int leaf(node *Tree)
    {
        if(Tree==NULL)return 0;
        if(Tree->left==NULL && Tree->right==NULL)return 1;
        return leaf(Tree->left)+leaf(Tree->right);
    }
    void insert(node* &rt,const T& key)
    {
        if(rt==NULL)
        {
            rt=new node(key);
            ++n;
        }
        else if(key<rt->val)
        {
            insert(rt->left,key);
            int H=height(rt->left)-height(rt->right);
            if(H==2)
            {
                if(key<rt->left->val)LL(rt);
                else LR(rt);
            }
        }
        else if(key>rt->val)
        {
            insert(rt->right,key);
            int H=height(rt->left)-height(rt->right);
            if(H==-2){
                if(key>rt->right->val)RR(rt);
                else RL(rt);
            }
        }
        uph(rt);
    }
    void uph(node* &p){p->h=max(height(p->left),height(p->right))+1;}
    int height(node* p){return p==NULL?-1:p->h;}
    void LL(node* &rt)
    {
        node* p=rt->left;
        rt->left=p->right;
        p->right=rt;
        uph(p);uph(rt);rt=p;
    }
    void RR(node* &rt)
    {
        node* p=rt->right;
        rt->right=p->left;
        p->left=rt;
        uph(p);uph(rt);rt=p;
    }
    void LR(node* &rt){RR(rt->left);LL(rt);}
    void RL(node* &rt){LL(rt->right);RR(rt);}
    node* &search(const T& key)
    {
        node* p=root;
        while(p)
        {
            if(p->val==key)return p;
            if(key<p->val)p=p->left;
            else p=p->right;
        }
        return NULL;
    }
    void clear(node* &rt)
    {
        if(rt==NULL)return;
        clear(rt->left);clear(rt->right);
        delete rt;--n;rt=NULL;
    }
        void erase(node* &rt,const T& key)
    {
        if(rt==NULL)return;
        if(key<rt->val)
        {
            erase(rt->left,key);
            int H=height(rt->left)-height(rt->right);
            if(H==-2)
            {
                int x=height(rt->right->right);
                int y=height(rt->right->left);
                if(x>y)RR(rt);else RL(rt);
            }
        }
        else if(key>rt->val)
        {
            erase(rt->right,key);
            int H=height(rt->left)-height(rt->right);
            if(H==2)
            {
                int x=height(rt->left->left);
                int y=height(rt->left->right);
                if(x>y)LL(rt);else LR(rt);
            }
        }
        else if(key==rt->val&&rt->left&&rt->right)
        {
            node* q=rt->left;
            while(q->right)q=q->right;
            rt->val=q->val;
            erase(rt->left,rt->val);
        }else 
        {
            node* q=rt->left==NULL?rt->right:rt->left;
            delete rt;rt=q;--n;
        }
        if(rt)uph(rt);
    }
private:
    node *root;
    int n;
};