数据结构--AVL树-创新互联

AVL树是高度平衡的二叉搜索树，较搜索树而言降低了树的高度；时间复杂度减少了使其搜索起来更方便；

1.性质：

（1）左子树和右子树高度之差绝对值不超过1；

（2）树中每个左子树和右子树都必须为AVL树；

（3）每一个节点都有一个平衡因子（-1,0,1：右子树-左子树）

（4）遍历一个二叉搜索树可以得到一个递增的有序序列

2.结构：

 平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是，树的结构是无法预料的。任意性非常大。它仅仅与节点的值和插入的顺序有关系。往往得到的是一个不平衡的二叉树。在最坏的情况下。可能得到的是一个单支二叉树，其高度和节点数同样，相当于一个单链表。对其正常的时间复杂度有O(lb n)变成了O(n)。从而丧失了二叉排序树的一些应该有的长处。

  当插入一个新的节点的时候。在普通的二叉树中不用考虑树的平衡因子，仅仅要将大于根节点的值插入到右子树，小于节点的值插入到左子树，递归就可以。

  而在平衡二叉树则不一样，在插入节点的时候，假设插入节点之后有一个节点的平衡因子要大于2或者小于-2的时候，他须要对其进行调整。如今仅仅考虑插入到节点的左子树部分（右子树与此同样）。主要分为下面三种情况：

(1)若插入前一部分节点的左子树高度和右子树高度相等。即平衡因子为0。插入后平衡因子变为1。仍符合平衡的条件不用调整。

(2)若插入前左子树高度小于右子树高度。即平衡因子为-1，则插入后将使平衡因子变为0，平衡性反倒得到调整，所以不必调整。

(3)若插入前左子树的高度大于右子树高度。即平衡因子为1。则插入左子树之后会使得平衡因子变为2，这种情况下就破坏了平衡二叉树的结构。所以必须对其进行调整，使其加以改善。

调整二叉树首先要明确一个定义。即最小不平衡子树。最小不平衡子树是指以离插入节点近期、且平衡因子绝对值大于1的节点做根的子树。

 在构建AVL树的时候使用三叉链：parent,left,right方便回溯，也可以用递归或者栈解决；

在插入一个新节点后，一个平衡二叉树可能失衡，失衡情况下相应的调整方法

（1）右旋

（2）左旋

（3）右左双旋

（4）左右双旋

#include
using namespace std;
template
struct AVLTreeNode
{
           AVLTreeNode*_left;
           AVLTreeNode*_right;
           AVLTreeNode*_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 AVLTree
{
           typedef AVLTreeNode  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_right;
                             }
                              else
                             {
                              return false ;
                             }
                   }
                    //插入
                   cur= new Node (key,value);
                    if(parent->_key_right=cur;
                             cur->_parent=parent;
                   }
                    else
                   {
                   parent->_left=cur;
                   cur->_parent=parent;
                   }
                    //检查是否平衡
                    //1更新平衡因子，不满足条件时进行旋转
                    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
                              {
                              //旋转处理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);
           //根据subLR的平衡因子修正其他节点的平衡因子
                    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<_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<< "节点的平衡因子异常" <_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;
          }
           //前边方法的优化
           //后续遍历先求子书的高度的同时就可以
           //判断出子树是否平衡，然后依次求根节点的高度
           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 t;
           for (size_t i = 0; i < sizeof(a)/ sizeof(a[0]); ++i)
          {
                   t.Insert(a[i], i);
          }
          t.Inorder();
          cout<< "是否平衡?" <
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            当前名称：数据结构--AVL树-创新互联            

            转载来源：http://cqcxhl.cn/article/gcjio.html