AVL樹是高度平衡的二叉搜索樹，較搜索樹而言降低了樹的高度；時(shí)間復(fù)雜度減少了使其搜索起來更方便；

創(chuàng)新互聯(lián)成立與2013年，公司以成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、系統(tǒng)開發(fā)、網(wǎng)絡(luò)推廣、文化傳媒、企業(yè)宣傳、平面廣告設(shè)計(jì)等為主要業(yè)務(wù)，適用行業(yè)近百種。服務(wù)企業(yè)客戶上千多家，涉及國(guó)內(nèi)多個(gè)省份客戶。擁有多年網(wǎng)站建設(shè)開發(fā)經(jīng)驗(yàn)。為企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、創(chuàng)意設(shè)計(jì)、宣傳推廣等服務(wù)。 通過專業(yè)的設(shè)計(jì)、獨(dú)特的風(fēng)格，為不同客戶提供各種風(fēng)格的特色服務(wù)。

1.性質(zhì)：

（1）左子樹和右子樹高度之差絕對(duì)值不超過1；

（2）樹中每個(gè)左子樹和右子樹都必須為AVL樹；

（3）每一個(gè)節(jié)點(diǎn)都有一個(gè)平衡因子（-1,0,1：右子樹-左子樹）

（4）遍歷一個(gè)二叉搜索樹可以得到一個(gè)遞增的有序序列

2.結(jié)構(gòu)：

 平衡二叉樹是對(duì)二叉搜索樹(又稱為二叉排序樹)的一種改進(jìn)。二叉搜索樹有一個(gè)缺點(diǎn)就是，樹的結(jié)構(gòu)是無法預(yù)料的。任意性非常大。它僅僅與節(jié)點(diǎn)的值和插入的順序有關(guān)系。往往得到的是一個(gè)不平衡的二叉樹。在最壞的情況下。可能得到的是一個(gè)單支二叉樹，其高度和節(jié)點(diǎn)數(shù)同樣，相當(dāng)于一個(gè)單鏈表。對(duì)其正常的時(shí)間復(fù)雜度有O(lb n)變成了O(n)。從而喪失了二叉排序樹的一些應(yīng)該有的長(zhǎng)處。

  當(dāng)插入一個(gè)新的節(jié)點(diǎn)的時(shí)候。在普通的二叉樹中不用考慮樹的平衡因子，僅僅要將大于根節(jié)點(diǎn)的值插入到右子樹，小于節(jié)點(diǎn)的值插入到左子樹，遞歸就可以。

  而在平衡二叉樹則不一樣，在插入節(jié)點(diǎn)的時(shí)候，假設(shè)插入節(jié)點(diǎn)之后有一個(gè)節(jié)點(diǎn)的平衡因子要大于2或者小于-2的時(shí)候，他須要對(duì)其進(jìn)行調(diào)整。如今僅僅考慮插入到節(jié)點(diǎn)的左子樹部分（右子樹與此同樣）。主要分為下面三種情況：

(1)若插入前一部分節(jié)點(diǎn)的左子樹高度和右子樹高度相等。即平衡因子為0。插入后平衡因子變?yōu)?。仍符合平衡的條件不用調(diào)整。

(2)若插入前左子樹高度小于右子樹高度。即平衡因子為-1，則插入后將使平衡因子變?yōu)?，平衡性反倒得到調(diào)整，所以不必調(diào)整。

(3)若插入前左子樹的高度大于右子樹高度。即平衡因子為1。則插入左子樹之后會(huì)使得平衡因子變?yōu)?，這種情況下就破壞了平衡二叉樹的結(jié)構(gòu)。所以必須對(duì)其進(jìn)行調(diào)整，使其加以改善。

調(diào)整二叉樹首先要明確一個(gè)定義。即最小不平衡子樹。最小不平衡子樹是指以離插入節(jié)點(diǎn)近期、且平衡因子絕對(duì)值大于1的節(jié)點(diǎn)做根的子樹。

 在構(gòu)建AVL樹的時(shí)候使用三叉鏈：parent,left,right方便回溯，也可以用遞歸或者棧解決；

在插入一個(gè)新節(jié)點(diǎn)后，一個(gè)平衡二叉樹可能失衡，失衡情況下相應(yīng)的調(diào)整方法

（1）右旋

（2）左旋

（3）右左雙旋

（4）左右雙旋

#include<iostream>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
           AVLTreeNode<K ,V>*_left;
           AVLTreeNode<K ,V>*_right;
           AVLTreeNode<K ,V>*_parent;
           K _key;
           V _value;
           int _bf;//平衡因子
          AVLTreeNode( const K & key,const V& value ):_bf(0)
                                                       ,_left(NULL)
                                                                                                          ,_right( NULL)
                                                                                                          ,_parent( NULL)
                                                                                                          ,_key( key)
                                                                                                          ,_value( value)
                                                                                                          
          {}
};
template<class K,class V>
class AVLTree
{
           typedef AVLTreeNode <K,V> Node;
protected:
           Node* _root;
public:
          AVLTree():_root( NULL)
          {}
           bool Insert(const K& key,const V& value)
          {
            if(_root==NULL )
            {
                     _root= new Node (key,value);
                     return true ;
            }
                    Node* cur=_root;
                    Node* parent=NULL ;
                    while(cur)
                   {
                              if(cur->_key>key )
                             {
                                      parent=cur;
                                      cur=cur->_left;
                             }
                              else if (cur->_key<key)
                             {
                                      parent=cur;
                                      cur=cur->_right;
                             }
                              else
                             {
                              return false ;
                             }
                   }
                    //插入
                   cur= new Node (key,value);
                    if(parent->_key<key )
                   {
                             parent->_right=cur;
                             cur->_parent=parent;
                   }
                    else
                   {
                   parent->_left=cur;
                   cur->_parent=parent;
                   }
                    //檢查是否平衡
                    //1更新平衡因子，不滿足條件時(shí)進(jìn)行旋轉(zhuǎn)
                    while(parent)
                   {
                    if(cur==parent->_left)
                              parent->_bf --;
                    else
                             parent->_bf ++;
                    if(parent->_bf ==0)
                    {
                              break;
                    }
                    // -1 1
                    else if (parent->_bf ==-1||parent->_bf ==1)
                    {
                    cur=parent;
                    parent=cur->_parent;
                    }
                              else
                              {
                              //旋轉(zhuǎn)處理2 -2
                                       if(cur->_bf ==1)
                                      {
                                                 if(parent->_bf==2)
                                                 RotateL(parent);
                                                 else//-2
                                                 RotateLR(parent);
                                      }
                                       else
                                      {
                                       if(parent->_bf ==-2)
                                         RotateR(parent);
                                       else//2
                                                RotateRL(parent);
                                      }
                                       break;
                              }
                   }
                    return true ;
          }
           //左單旋
           void RotateL(Node * parent)
          {
                     Node* subR=parent ->_right;
                     Node* subRL=subR->_left;
                     if(subRL)
                     subRL->_parent = parent;
                     subR->_left= parent;
                     Node* ppNode=parent ->_parent;
                     parent->_parent=subR;
                     if(ppNode==NULL )
                     {
                                      _root=subR;
                     }
                     else
                     {
                                       if(ppNode->_left=parent )
                                      {
                                                 ppNode->_left=subR;
                                      }
                                       else
                                      {
                                                 ppNode->_right=subR;
                                      }
                     }
                     parent->_bf=subR->_bf=0;
          }
           //右單旋
           void RotateR(Node * parent)
          {
                    Node* subL=parent ->_left;
                    Node* subLR=subL->_right;
                    if(subLR)
                    subLR->_parent = parent;
                    subL->_right = parent;
                    Node* ppNode=parent ->_parent;
                    if(ppNode==NULL )
                    {
                             _root=subL;
                    }
                    else
                    {
                     if(ppNode->_left==parent )
                               ppNode->_left=subL;
                     else
                               ppNode->_right=subL;
                    }
                    parent->_bf =subL->_bf =0;
          }
           //左右雙旋
           void RotateLR(Node * parent)
          {
           Node* subL=parent ->_left;
           Node* subLR=subL->_right ;
           int bf=subLR->_bf ;
          RotateL( parent->_left);
          RotateR( parent);
           //根據(jù)subLR的平衡因子修正其他節(jié)點(diǎn)的平衡因子
                    if(bf==-1)
                   {
                             subL->_bf =0;
                              parent->_bf =1;
                   }
                    else if (bf==1)
                   {
                     subL->_bf =-1;
                     parent->_bf=0;
                   }
          }
           //右左雙旋
           void RotateRL(Node * parent)
          {
                    Node* subR=parent ->_right ;
                    Node* subRL=subR->_left ;
                    int bf=subRL->_bf ;
                   RotateR( parent->_right);
                   RotateL( parent);
                    if(bf==1)
                   {
                    subR->_bf =0;
                    parent->_bf =-1;
                   }
                    else if (bf==-1)
                   {
                   subR->_bf = 1;
                    parent->_bf = 0;
                   }
          }
           //中序遍歷
           void Inorder()
          {
             _Inorder(_root);
             cout<<endl;
          }
           void _Inorder(Node * root)
          {
           if(_root==NULL )
                    return;
           _Inorder( root->_left);
           cout<< root->_key <<" " ;
           _Inorder( root->_right );
          }
           //判斷是否平衡
           bool IsBalence()
          {
             return _IsBalence(_root);
          }
          
           bool _IsBalence(Node * root)
          {
            if(root ==NULL)
                     return true ;
            int left=_Height(root ->_left );
            int right= _Height(root ->_right );
            if(right-left!=root ->_bf || abs(right-left)>1)
            {
             cout<< "節(jié)點(diǎn)的平衡因子異常" <<endl;
             cout<< root->_key ;
             return false ;
            }
            return _IsBalence(root ->_left)&&_IsBalence(root->_left);
          }
//求子樹的高度
           int _Height(Node * root)
          {
            if(root ==NULL)
             return 0;
           int left=_Height(root ->_left );
           int right= _Height(root ->_right );
           return left>right?left+1:right+1;
          }
           //前邊方法的優(yōu)化
           //后續(xù)遍歷先求子書的高度的同時(shí)就可以
           //判斷出子樹是否平衡，然后依次求根節(jié)點(diǎn)的高度
           bool _Isbalence(Node * root, int& height )
          {
             if(root ==NULL)
                      {
                                height=0;
                                return true ;
                      }
             if(root ->_left ==NULL&& root->_right ==NULL )
                      {
                                height=1;
                                returnn true;
                      }
             int leftheight=0;
            if(_Isbalence(root ->_left ,leftheight)==false)
                     return false ;
            int rightheight=0;
            if(_Isbalence(root ->_right ,rightheight)==false)
                     return false ;
            height=leftheight>rightheight?leftheight:rightheight;
          }
};
void TestTree()
{
           int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
           AVLTree<int , int> t;
           for (size_t i = 0; i < sizeof(a)/ sizeof(a[0]); ++i)
          {
                   t.Insert(a[i], i);
          }
          t.Inorder();
          cout<< "是否平衡?" <<t.IsBalence()<<endl;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站欄目：數(shù)據(jù)結(jié)構(gòu)--AVL樹-創(chuàng)新互聯(lián)
瀏覽地址：http://chinadenli.net/article0/gcjio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、全網(wǎng)營(yíng)銷推廣、定制開發(fā)、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)