二叉查找树是个好东西，他让查找，插入，删除，这些常用操作变得高效，但是，他是存在问题的，那就是，在坏的输入序列下，树会退化成链表，这就很尴尬了，于是为了避免这种情况的发生，我们需要一种数据结构，可以自动对树进行调整，我们希望树尽量平衡，于是我们使用平衡因子作为指标，保持任意节点左右子树深度差不超过1，这就可以让树的深度很理想了（接近log2N)，如何对树进行调整呢？我们通过旋转来完成他。

#include 
      
       #include 
       
        class AVLT{
    //小于向左，大于等于向右,元素类型需支持 
        
         nodeInsect(e);        if (right){            if (left->Deepth - right->Deepth > 1){                if (e
         
          data){                    this->SingleRightRotation();                }                else{                    this->DoubleLeftRightRotation();                }            }        }        else{            if (left->Deepth > 1){                if (e
          
           data){                    this->SingleRightRotation();                }                else{                    this->DoubleLeftRightRotation();                }            }        }        renewDeepth();    }    else{        if (right == NULL){            right = new AVLTNode;        }        right->nodeInsect(e);        if (left){            if (right->Deepth - left->Deepth > 1){                if (e
           
            data){ this->DoubleRightLeftRotation(); } else{ this->SingleLeftRotation(); } } } else{ if (right->Deepth > 1){ if (e
            
             data){ this->DoubleRightLeftRotation(); } else{ this->SingleLeftRotation(); } } } renewDeepth(); } return;}void AVLT::AVLTNode::nodeDelete(const Element &e){ if (e
             
              isLeaf()){ delete left; left = NULL; } else left->nodeDelete(e); { int rd = right ? right->Deepth : 0; int ld = left ? left->Deepth : 0; if (rd - ld >1){ if (right->left){ DoubleRightLeftRotation(); } else{ SingleLeftRotation(); } } renewDeepth(); } } return; } else{ if (data
              
               isLeaf()){ delete right; right = NULL; } else right->nodeDelete(e); { int rd = right ? right->Deepth : 0; int ld = left ? left->Deepth : 0; if (ld - rd >1){ if (left->right){ DoubleLeftRightRotation(); } else{ SingleRightRotation(); } } renewDeepth(); } return; } } else{ if (left == NULL&&right){ AVLTNode *t = right; if (left) delete left; left = t->left; right = t->right; data = t->data; Deepth -= 1; t->left = t->right = NULL; delete t; return; } else{ if (right == NULL && left){ AVLTNode *t = left; if (right) delete right; right = t->right; left = t->left; data = t->data; Deepth -= 1; t->left = t->right = NULL; delete t; return; } else{ AVLTNode *t = left; while (t->right) t = t->right; Element te = t->data; if (left->isLeaf()){ delete left; left = NULL; } else left->nodeDelete(te); data = te; return; } } } } std::cout << "return false" << std::endl; return;}AVLT::AVLTNode const *AVLT::AVLTNode::Find(const Element &e)const{ if (e
               
                Find(e); } else{ if (data
                
                 Find(e); } else{ return this; } } return NULL;}const AVLT::Element& AVLT::AVLTNode::Max()const{ const AVLTNode *t = this; while (t->right) t = t->right; return t->data;}const AVLT::Element& AVLT::AVLTNode::Min()const{ const AVLTNode *t = this; while (t->left) t = t->left; return t->data;}void AVLT::AVLTNode::nodeTraverseFrist(std::ostream& os)const{ os << this->data << ' '; if (left) this->left->nodeTraverseFrist(); if (right) this->right->nodeTraverseFrist();}void AVLT::AVLTNode::nodeTraverseMid(std::ostream& os )const{ if (left) this->left->nodeTraverseMid(); os << this->data << ' '; if (right) this->right->nodeTraverseMid();}void AVLT::AVLTNode::nodeTraverseLast(std::ostream& os )const{ if (left) this->left->nodeTraverseLast(); if (right) this->right->nodeTraverseLast(); os << this->data << ' ';}void AVLT::AVLTNode::nodeTraverselevel(std::ostream& os)const{ std::queue
                 
                   q; q.push(*this); while (!q.empty()){ AVLTNode p = q.front(); q.pop(); os << p.data << ' '; if (p.left){ q.push(*(p.left)); } if (p.right){ q.push(*(p.right)); } }}const AVLT::AVLTNode & AVLT::AVLTNode::operator =(const AVLTNode &T){ if (Deepth == 0){ Deepth = 1; data = T.data; } if (T.left){ if (left == NULL){ left = new AVLTNode; } *left = *T.left; if (right){ Deepth = max(left->Deepth, right->Deepth) + 1; } else{ Deepth = left->Deepth + 1; } } if (T.right){ if (right == NULL){ right = new AVLTNode; } *right = *T.right; if (left){ Deepth = max(left->Deepth, right->Deepth) + 1; } else{ Deepth = right->Deepth + 1; } } return *this;}void AVLT::AVLTNode::swapdata(AVLTNode&a, AVLTNode&b)const{ Element t; t = a.data; a.data = b.data; b.data = t;}void AVLT::AVLTNode::SingleLeftRotation(){ AVLTNode *a = right; right = a->right; a->right = a->left; a->left = left; left = a; if (a->right&&a->left){ a->Deepth = max(a->left->Deepth, a->right->Deepth) + 1; } else if (a->left){ a->Deepth = a->left->Deepth + 1; } else{ a->Deepth = 1; } swapdata(*this, *a);}void AVLT::AVLTNode::SingleRightRotation(){ AVLTNode *a = left; left = a->left; a->left = a->right; a->right = right; right = a; if (a->right&&a->left){ a->Deepth = max(a->left->Deepth, a->right->Deepth) + 1; } else if (a->left){ a->Deepth = a->left->Deepth + 1; } else{ a->Deepth = 1; } swapdata(*this, *a);}void AVLT::AVLTNode::DoubleLeftRightRotation(){ this->left->SingleLeftRotation(); this->SingleRightRotation();}void AVLT::AVLTNode::DoubleRightLeftRotation(){ this->right->SingleRightRotation(); this->SingleLeftRotation();}inline void AVLT::AVLTNode::renewDeepth(){ Deepth = max(left ? left->Deepth : 0, right ? right->Deepth : 0) + 1;}inline int AVLT::AVLTNode::max(int a, int b)const{ return a > b ? a : b;}AVLT::AVLT():node(NULL), number_of_Node(0){}AVLT::AVLT(Element *arr, int size) : node(NULL), number_of_Node(0){ node = new AVLTNode; for (int i = 0; i < size; i++) this->Insect(arr[i]);}AVLT::AVLT(const AVLT &T) : node(NULL), number_of_Node(0){ *this = T;}AVLT::~AVLT(){ delete node;}bool AVLT::empty()const{ return node == NULL;}const AVLT::Element& AVLT::Max()const{ return node->Max();}const AVLT::Element& AVLT::Min()const { return node->Min();}const AVLT &AVLT::operator = (const AVLT&T){ delete node; node = new AVLTNode; number_of_Node = T.number_of_Node; *node = *T.node; return *this;}void AVLT::TraverseFrist(std::ostream& os )const{ if (node) node->nodeTraverseFrist(os);}void AVLT::TraverseLast(std::ostream& os )const{ if (node) node->nodeTraverseLast(os);}void AVLT::TraverseMid(std::ostream& os )const{ if (node) node->nodeTraverseMid(os);}void AVLT::Traverselevel(std::ostream& os )const{ if (node) node->nodeTraverselevel(os);}void AVLT::Insect(const AVLT::Element &e){ number_of_Node++; if (node == NULL){ node = new AVLTNode; } node->nodeInsect(e);}bool AVLT::Delete(const AVLT::Element &e){ if (node){ if (node->isLeaf()){ delete node; node = NULL; } else node->nodeDelete(e); number_of_Node--; return true; } else{ return false; }}int AVLT::Deepth(){ return node->Deepth;}int AVLT::Node(){ return number_of_Node;}const AVLT::AVLTNode*AVLT::find(const AVLT::Element &e)const { if (node) return node->Find(e); else return NULL;;}std::ostream& operator << (std::ostream& os, const AVLT& T){ T.TraverseFrist(os); return os;}const AVLT& find();
                 
                
               
              
             
            
           
          
         
        
       
      

这样看上去，AVL树似乎完胜普通的二叉查找树，但是现实是，坏的序列往往很少出现，很多时候，普通二叉树因为不需要判断平衡因子，旋转这些操作，效率反而更高，但是他一旦对上坏的序列就无计可施了，想能防住坏的序列，但又不想每次都旋转，于是就有伸展树这种数据结构，他只在坏的序列出现时旋转，但是只有“坏到一定

程度才旋转”，于是会出现比较坏但坏得不彻底的尴尬情况，伸展树无法保证每次操作都是O（log2N)，但是能保证M次操作时间复杂度为O（Mlog2N）。