#include <iostream>
#include "AVLtree.cpp"
using namespace std;
int main()
{
    AVLtree <int> a;
    int i,n;
    cin>>n;
    for (i=0; i<n; i++)
        a.insert_(i+i*10);
    a.traversal();
    cout<<endl;
    a.delete_(55);
    a.traversal();
}

#include "AVLtree.h"
template <class T>
int AVLtree<T>::height(treenode<T>*node)
{
    if (node!=NULL)
    {
        return node->hgt;
    }
    return -1;
}

template <class T>
int AVLtree<T>::max_(int cmpa,int cmpb)
{
    return cmpa>cmpb?cmpa:cmpb;
}

//左左情况下的旋转
template <class T>
void AVLtree<T>::singRotateLeft(treenode<T>*&k2)
{
    treenode<T>*k1;
    k1=k2->lson;
    k2->lson=k1->rson;
    k1->rson=k2;

    k2->hgt=max_(height(k2->lson),height(k2->rson))+1;
    k1->hgt=max_(height(k1->lson),k2->hgt)+1;
}

//右右情况下的旋转
template <class T>
void AVLtree<T>::singRotateRight(treenode<T>*&k2)
{
    treenode<T>*k1;
    k1=k2->rson;
    k2->rson=k1->lson;
    k1->lson-k2;

    k2->hgt=max_(height(k2->lson),height(k2->rson))+1;
    k1->hgt=max_(height(k1->rson),k2->hgt)+1;
}

//左右情况下的旋转
template <class T>
void AVLtree<T>::doubleRotateLR(treenode<T>*&k3)
{
    singRotateRight(k3->lson);
    singRotateLeft(k3);
}

//右左情况下的旋转
template <class T>
void AVLtree<T>::doubleRotateRL(treenode<T>*&k3)
{
    singRotateLeft(k3->rson);
    singRotateRight(k3);
}

//插入
template <class T>
void AVLtree<T>::insertpri(treenode<T>*&node,T x)
{
    if (node==NULL)
    {
        node=new treenode<T>();
        node->data=http://www.mamicode.com/x;
        return;
    }
    if (node->data>x)  //如果x小于节点的值，就继续在节点的左子树中插入x
    {
        insertpri(node->lson,x);
        if (2==height(node->lson)-height(node->rson))
        {
            if (x<node->lson->data)
            {
                singRotateLeft(node);
            }
            else
            {
                doubleRotateLR(node);
            }
        }
    }
    else if (node->data<x)
    {
        insertpri(node->rson,x);
        if (2==height(node->rson)-height(node->lson))
        {
            if (x>node->rson->data)
            {
                singRotateRight(node);
            }
            else
            {
                doubleRotateRL(node);
            }
        }
    }
    else ++(node->freq);
    node->hgt=max_(height(node->lson),height(node->rson));
}

template <class T>
void AVLtree<T>::insert_(T x)
{
    insertpri(root,x);
}
template <class T>
treenode<T>*AVLtree<T>::findpri(treenode <T>*node,T x)
{
    if (node==NULL)
    {
        return NULL;
    }
    if (node->data>x)
    {
        return findpri(node->lson,x);
    }
    else if (node->data<x)
    {
        return findpri(node->rson,x);
    }
    else
        return node;
}

template <class T>
treenode<T>*AVLtree<T>::find_(T x)
{
    return findpri(root,x);
}

//删除
template <class T>
void AVLtree<T>::deletepri(treenode<T>*&node,T x)
{
    if (node==NULL)
        return;
    if (x<node->data)
    {
        deletepri(node->lson,x);
        if (2==height(node->rson)-height(node->lson))
        {
            if (node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)))
                doubleRotateRL(node);
            else
                singRotateRight(node);
        }
    }
    else if(x>node->data)
    {
        deletepri(node->rson,x);
        if(2==height(node->lson)-height(node->rson))
        {
            if(node->lson->rson!=NULL&&(height(node->lson->rson)>height(node->lson->lson)))
                doubleRotateLR(node);
            else
                singRotateLeft(node);
        }
    }
    else
    {
        if(node->lson&&node->rson)
        {
            treenode<T>*temp=node->rson;
            while(temp->lson!=NULL)
                temp=temp->lson;
            node->data=http://www.mamicode.com/temp->data;
            node->freq=temp->freq;
            deletepri(node->rson,temp->data);
            if (2==height(node->lson)-height(node->rson))
            {
                if(node->lson->rson!=NULL&&(height(node->lson->rson)>height(node->lson->lson)))
                    doubleRotateLR(node);
                else
                    singRotateLeft(node);
            }
        }
        else
        {
            treenode<T>*temp=node;
            if(node->lson==NULL)
            {
                node=node->rson;
            }
            else if (node->rson==NULL)
                node=node->lson;
            delete(temp);
            temp=NULL;
        }
    }
    if(node==NULL)
        return;
    node->hgt=max_(height(node->lson),height(node->rson))+1;
    return;
}


template <class T>
void AVLtree<T>::delete_(T x)
{
    deletepri(root,x);
}

template <class T>
void AVLtree<T>::insubtree(treenode<T>*node)
{
    if (node==NULL)
        return;
    insubtree(node->lson);
    std::cout<<node->data<<" ";
    insubtree(node->rson);
}

template <class T>
void AVLtree<T>::traversal()
{
    insubtree(root);
}

#ifndef AVLTREE_H_INCLUDED
#define AVLTREE_H_INCLUDED

template <class T>
class treenode
{
public:
    treenode()
    {
        lson=NULL;
        rson=NULL;
        freq=1;
        hgt=0;
    }
    T data;
    int hgt;  //以此节点为根的树的高度
    unsigned int freq;
    treenode*lson;
    treenode*rson;
};

template <class T>
class AVLtree
{
private:
    treenode<T>*root;
    void insertpri(treenode<T>*&node,T x);  //插入
    treenode<T>*findpri(treenode<T>*node,T x);  //查找
    void insubtree(treenode<T>*node);  //中序遍历
    void deletepri(treenode<T>*&node,T x);  //删除
    int height(treenode<T>*node);   //求树的高度
    void singRotateLeft(treenode <T>*&k2);  //左左情况下的旋转
    void singRotateRight(treenode<T>*&k2);  //右右情况下的旋转
    void doubleRotateLR(treenode<T>*&k3);   //左右情况下的旋转
    void doubleRotateRL(treenode<T>*&k3);   //右左情况下的旋转
    int max_(int cmpa,int cmpb);   //求最大值

public:
    AVLtree()
    {
        root=NULL;
    }
    void insert_(T x);
    treenode<T>*find_(T x);
    void delete_(T x);
    void traversal();
};
#endif // AVLTREE_H_INCLUDED

AVLtree