二叉树的查找，插入和删除操作的时间与树的高度有关，如果树尽量的矮胖，那么时间就短，那就要是满二叉树，或者说满N叉树，对于一颗M个节点的满N叉树时间复杂度为，但是维护满叉树，难度是很大的。所以AVL树(平衡树)放宽了条件，允许左右子树的高度差在一定的范围之内，avl树平衡条件是左右子树高度相差不能为2，而不是满叉树左右子树高度相同。AVL是以提出它的两位苏联数学家的名字头字母命名的。一棵N个节点的AVL树，高度最高为1.44logx(N+1)-0.328，比满二叉树高度增加44%。

                  在avl树中通过对不满足限制条件的子树就行旋转规格来确保av树的平衡条件一直成立。在AVL树中有LL，LR，RR和RL四种旋转方式。

                  下面给出几个示例：

                  依次插入3，5，6，2，1，4

                  按照和二叉树插入的方式一样，插入3，5，6：

                  现在不平横了，3节点左子树的高度为-1（空树为-1），右子树为1，相差为2，不平衡，插入在3节点的右子树的右子树，这种情况称为RR，转换为，这样就平衡了。继续插入2和1，情况如下：节点3失去平衡，1插在3的左子树的左子树，LL情况，需要旋转，如下：树重新平衡，现在继续插入4，如下：，节点5失去平衡，4插在它的左子树的右子树上，这种情况为LR，需要两次旋转，第一次为RR，5的左子树，然后LL5这棵树。变换后如下：

就不一一分析了，下面是实现代码。

/**************************************************author:周翔*e-mail:604487178@qq.com*blog:http://blog.csdn.net/zhx6044***************************************************/#ifndef AVLTREE_HPP#define AVLTREE_HPP#include "linkQueue.hpp"template 
    
     T max(const T &t1, const T &t2){    return (t1 < t2) ? t2 : t1 ;}template 
     
      class AvlTree{public:    AvlTree();    ~AvlTree();    bool find(const T& t) const;    bool insert(const T &t);    void remove(const T &t);    bool isEmpty() const;    void clear();    int height(typename AvlTree::node *n);    /**     * @brief levelTraverse 层虚遍历     * @param os     */    void levelTraverse(std::ostream &os = std::cout) const;private:    typedef enum {LEFT, RIGHT} TreeType;    struct node {        T data;        node *lc,*rc;        int height;//高度        node():lc(0),rc(0),height(0){        }        node(const T &t,node *_lc = 0, node *_rc = 0,int _hei = 0):            data(t),            lc(_lc),            rc(_rc),            height(_hei){        }    };    node *root;    bool insert(const T &t, node *&n);    bool remove(const T &t, node *&n);    void clear(node *n);    //四种旋转，    void LL(node *&n);    void RR(node *&n);    void LR(node *&n);    void RL(node *&n);};template 
      
       inlineAvlTree
       
        ::AvlTree():root(0){}template 
        
         AvlTree
         
          ::~AvlTree(){ clear();}template 
          
           void AvlTree
           
            ::clear(node *n){ if (n->lc != 0) { clear(n->lc); } if (n->rc != 0) { clear(n->rc); } delete n;}template 
            
             void AvlTree
             
              ::clear(){ if (!isEmpty()) clear(root);}template 
              
               inlinebool AvlTree
               
                ::isEmpty() const{ return root == 0;}template 
                
                 inlineint AvlTree
                 
                  ::height(node *n){ return (n == 0) ? -1 : n->height;}template 
                  
                   void AvlTree
                   
                    ::LL(node *&n){ node *p = n;//暂存n n = n->lc;//左子树作为根节点 p->lc = n->rc;//右子树作为原来根的左子树 n->rc = p;//原来根节点作为新节点的右子树 p->height = max(height(p->lc),height(p->rc)) + 1;//先做子树的高度 n->height = max(height(n->lc),height(n->rc)) + 1;}template 
                    
                     void AvlTree
                     
                      ::RR(node *&n){ node *p = n; n = n->rc; p->rc = n->lc; n->lc = p; p->height = max(height(p->lc),height(p->rc)) + 1; n->height = max(height(n->lc),height(n->rc)) + 1;}template 
                      
                       void AvlTree
                       
                        ::LR(node *&n){ RR(n->lc); LL(n);}template 
                        
                         void AvlTree
                         
                          ::RL(node *&n){ LL(n->rc); RR(n);}template 
                          
                           bool AvlTree
                           
                            ::find(const T &t) const{ node *p = root; while (p != 0 && p->data != t) { if (p->data < t) { p = p->rc; } else { p = p->lc; } } return ((p == 0) ? false:true);}template 
                            
                             bool AvlTree
                             
                              ::insert(const T &t){ return insert(t,root);}template 
                              
                               bool AvlTree
                               
                                ::insert(const T &t, node *&n){ bool re = false; if (n == 0) { n = new node(t); re = true; } else { if (t < n->data) { re = insert(t,n->lc);//插入到左子树 if (height(n->lc) - height(n->rc) == 2) {//子树高度差超过1 if (t < n->lc->data) {//插入的值小于左子树的值，说明还要插在左子树的左子树 LL(n);//做LL旋转 } else { LR(n);//做LR旋转 } } } else { re = insert(t,n->rc); if (height(n->rc) - height(n->lc) == 2) { if (t < n->rc->data) { RL(n); } else { RR(n); } } } } n->height = max(height(n->lc),height(n->rc)) + 1; return re;}template 
                                
                                 void AvlTree
                                 
                                  ::remove(const T &t){ remove(t,root);}template 
                                  
                                   /** * @brief AvlTree
                                   
                                    ::remove * @param t * @param n * @return * 只讨论左子树，右子树情况对称，删除的节点都在P的左子树上 * 1.P节点平衡因子为0，删除节点x，使其某棵子树变矮，p的平衡因子变为-1或1，树的高度不变，整棵树也不变 * 2.P节点平衡因子为-1或1，删除P较高子树的节点，P平衡因子为0，树高发生了变化，需要继续向上规格 * 3.P节点平衡因子为-1或1，删除P较矮子树的节点，P不平横，需要规格，树高如果变化，需要继续向上规格 * 3.1P的右子树的平衡因子为0，做RR，子树高度不变，不许要规格 * 3.2P的右子树的平衡因子与P相同，做一个RR，子树高度变化，需要继续规格 * 3.2P的右子树的平衡因子与P相反，RL，子树高度变化，需要贵徐规格 */bool AvlTree
                                    
                                     ::remove(const T &t, node *&n){ bool re = true;//是否需要规格 TreeType flag;//标识是左子树还是右子树 if (n == 0) { re = false; } else { if (t < n->data) { re = remove(t,n->lc); flag = LEFT; } else { if (t > n->data) { re = remove(t,n->rc); flag = RIGHT; } else { //t = n->data if (n->lc != 0 && n->rc != 0) { node *p = n->rc; while (p->lc != 0) p = p->lc; n->data = p->data; re = remove(p->data,n->rc);                    flag = RIGHT;                    } else { node *p = n; n = (n->rc == 0) ? n->lc : n->rc; delete p; re = false; } } } } if (re) { int t; switch (flag) { case LEFT://左子树 t = height(n->lc) + 1 - height(n->rc);//左子树删除一个节点，现在的+1原来的 if (t == 0) {// re = false; } else { if (re == 1) {//说明左子树较高 re = true; } else { int t2 = height(n->rc->lc) - height(n->rc->rc); switch (t2) { case 0: RR(n); re = false; break; case -1://左子树矮,连个平衡因子相同,为-1 RR(n); re = true; break; default: RL(n); re = true; break; } } } break; case RIGHT://右子树 t = height(n->lc) - (height(n->rc)+1);//右子树删除一个节点，现在的+1原来的 if (t == 0) {// re = false; } else { if (re == -1) {//说明右子树较高 re = true; } else {//较矮的树 int t2 = height(n->lc->lc) - height(n->lc->rc); switch (t2) { case 0: LL(n); re = false; break; case 1://右子树矮,连个平衡因子相同,为1 LL(n); re = true; break; default: LR(n); re = true; break; } } } break; default: break; } } return re;}template 
                                     
                                      void AvlTree
                                      
                                       ::levelTraverse(std::ostream &os) const{ LinkQueue
                                       
                                         queue; queue.enqueue(root); while(!queue.isEmpty()) { node *t = queue.dequeue(); if (t != NULL) { os << t->data << " "; queue.enqueue(t->lc); queue.enqueue(t->rc); } }}#endif // AVLTREE_HPP#include "avlTree.hpp"int main(){ AvlTree
                                        
                                          avlt; int arr[]={3,5,6}; for(int i = 0;i < 3;++i) { avlt.insert(arr[i]); } avlt.levelTraverse(); avlt.insert(2); std::cout << '\n'; avlt.levelTraverse(); avlt.insert(1); std::cout << '\n'; avlt.levelTraverse(); avlt.insert(4); std::cout << '\n'; avlt.levelTraverse();}