#include <iostream>using namespace std;int chy_max(int  t1,int t2){    if(t1 < t2)        return t2;    return t1;}int chy_min(int t1,int t2){    if(t1 < t2)        return t1;    return t2;}struct chy_avl_t{    chy_avl_t(unsigned v):value(v),left(0),right(0),high(0){}    unsigned            value;    struct chy_avl_t    *left;    struct chy_avl_t    *right;    int                    high;};class chy_avl{    public:        chy_avl(unsigned v):root(new chy_avl_t(v)){}        chy_avl():root(NULL){}        ~chy_avl(){ destroy(root);}        void destroy(chy_avl_t *n);        void insert(unsigned v){root = insert(root,v);}        void remove(unsigned v){ root = remove(root,v);}        void print(){print(root);}        void print(chy_avl_t *n){            if(n){                print(n->left);                cout << n->value  << endl;                print(n->right);            }        }    private:        int height(chy_avl_t *n);        chy_avl_t *insert(chy_avl_t *n,unsigned v);        chy_avl_t *remove(chy_avl_t *n,unsigned v);        chy_avl(const chy_avl&);        chy_avl_t *left_rotate(chy_avl_t *n);        chy_avl_t *right_rotate(chy_avl_t *n);        chy_avl_t *left_right(chy_avl_t *n);        chy_avl_t *right_left(chy_avl_t *n);        chy_avl_t *root;        chy_avl_t *avl_min(chy_avl_t *n){            while(n){                if(n->left == 0)                    return n;                n = n->left;            }        }};int chy_avl::height(chy_avl_t* n){    if(n == 0){        return -1;    }else{        return n->high;    }}void chy_avl::destroy(chy_avl_t *n){    if(n){        destroy(n->left);        destroy(n->right);        delete n;    }}chy_avl_t*  chy_avl::left_rotate(chy_avl_t *n){//左旋    chy_avl_t *l;    l = n->left;    n->left = l->right;    l->right = n;    n->high = 1 + chy_max(height(n->left),height(n->right));//first ,becase n is l child    l->high = 1 + chy_max(height(l->left),height(l->right));//second    return l;}chy_avl_t* chy_avl::right_rotate(chy_avl_t *n){//右旋    chy_avl_t *r;    r = n->right;    n->right = r->left;    r->left = n;    n->high = 1 + chy_max(height(n->left),height(n->right));    r->high = 1 + chy_max(height(r->left),height(r->right));    return r;}chy_avl_t* chy_avl::left_right(chy_avl_t *n){//左右旋    chy_avl_t *l;    l = right_rotate(n->left);    return left_rotate(l);}chy_avl_t* chy_avl::right_left(chy_avl_t *n){//右左旋    chy_avl_t *r;    r = left_rotate(n->right);    return right_rotate(r);}chy_avl_t* chy_avl::insert(chy_avl_t *n,unsigned v){    if(n == 0){        return new chy_avl_t(v);    }else if(n->value < v){        n->right = insert(n->right,v);        if(height(n->right) - height(n->left) == 2){            if(v < n->right->value){                n = right_left(n);            }else{                n = right_rotate(n);            }        }    }else if(n->value > v){        n->left = insert(n->left,v);        if(height(n->left) - height(n->right) == 2){            if(v < n->left->value){                n = left_rotate(n);            }else{                n = left_right(n);            }        }    }    n->high = 1 + chy_max(height(n->left),height(n->right));    return n;}chy_avl_t* chy_avl::remove(chy_avl_t *n,unsigned v){    if(n ==0){        return 0;    }    if(v == n->value){        if(n->left && n->right){            chy_avl_t *tmp;            tmp = avl_min(n->right);            n->value = http://www.mamicode.com/tmp->value;            n->right = remove(n->right,tmp->value);            if(height(n->left) - height(n->right) == 2){                if(n->left->right && height(n->left->right)>height(n->left->left))                    n = left_right(n);                else                    n = left_rotate(n);            }        }else {            chy_avl_t *tmp;            tmp = n;            if(n->right == 0)                n = n->left;            else if(n->left == 0)                n = n->right;            delete tmp;            tmp = 0;        }    }else if(n->value < v){        n->right = remove(n->right,v);        if(height(n->left) - height(n->right) == 2){            if(n->left->right && (height(n->left->right)>height(n->left->left)) )                n = left_right(n);            else                n = left_rotate(n);        }    }else {        n->left =  remove(n->left,v);        if(height(n->right) - height(n->left) == 2){            if(n->right->left && (height(n->right->left) > height(n->right->right)) )                n = right_left(n);            else                n = right_rotate(n);        }    }    if(n)        n->high = 1 + chy_max(height(n->left),height(n->right));    return n;}void f1(){    chy_avl a1;    for(unsigned i = 1;i < 100;i ++){        a1.insert(i);    }    a1.print();    for(unsigned i = 1;i < 100;i ++){        a1.remove(i);    }}void f2(){    chy_avl a1;    for(unsigned i = 1;i < 100;i ++){        a1.insert(i);    }    a1.print();    for(unsigned i = 1;i < 100;i ++){        a1.remove(i);    }}void f3(){    chy_avl a1;    for(unsigned i = 1;i < 100;i ++){        a1.insert(i);    }}void f4(){    chy_avl a1;    for(unsigned i = 1;i < 100;i ++){        a1.insert(i);    }}int main(){    f1();//    f2();//    f3();//    f4();    return 0;}