#includeusing 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 = 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;}