平衡搜索树—AVLTree

       AVL是平衡搜索二叉树，它的主要特点在于：（1）左子树和右子树的高度差绝对值<1,（2）树中的每个子树都是AVL树，（3）每个节点都有一个平衡因子（-1、0、1），平衡因子的大小等于右子树的高度减左子树的高度

公司主营业务：网站设计制作、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联建站是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联建站推出海阳免费做网站回馈大家。

      下面就是一个AVL树：

其中，这个树满足左子树和右子树的高度差绝对值小于1，每个节点的平衡因子都满足条件。

      下面是AVLTree中节点的结构：

template 
struct AVLTreeNode
{
     K _key;
     V _value;
     int _bf;     //节点的平衡因子
     AVLTreeNode* _parent;     //指向节点的父节点
     AVLTreeNode* _left;       //指向节点的左孩子
     AVLTreeNode* _right;      //指向节点的右孩子
     
     AVLTreeNode(const K& key = K(), const V& value = V())    //构造节点
          :_key(key)
          , _value(value)
          , _parent(NULL)
          , _left(NULL)
          , _right(NULL)
          , _bf(0)
     { }
};

      下面讨论一下AVLTree中插入节点的情况：

           当插入一个节点时，如果这个节点的父节点的平衡因子不满足AVLTree的特点，这时就需要对AVLTree进行调整，直到满足AVLTree的条件。

（1）左单旋

（2）右单旋

（3）左右双旋

（4）右左双旋

       针对上面的情况，下面是具体的程序实现：

#pragma once
#include 
#include 
//实现平衡搜索二叉树
//构造AVL树的节点（使用三叉链表）

template 
struct AVLTreeNode
{
     K _key;
     V _value;
     int _bf;
     AVLTreeNode* _parent;
     AVLTreeNode* _left;
     AVLTreeNode* _right;
     
     AVLTreeNode(const K& key = K(), const V& value = V())    //构造节点
          :_key(key)
          , _value(value)
          , _parent(NULL)
          , _left(NULL)
          , _right(NULL)
          , _bf(0)
     { }
};

template 
class AVLTree
{
     typedef AVLTreeNode Node;
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;
          Node* tmp = new Node(key, value);
          while (cur)
          {
               if (cur->_key < key)
               {
                    parent = cur;
                    cur = cur->_right;
               }
               else if (cur->_key > key)
               {
                    parent = cur;
                    cur = cur->_left;
               }
               else
               {
                    return false;
               }
          }
          if (parent->_key > key)
          {
               parent->_left = tmp;
               tmp->_parent = parent;
          }
          if (parent->_key < key)
          {
               parent->_right = tmp;
               tmp->_parent = parent;
          }
          
          //对树进行调整
          cur = tmp;
          parent = cur->_parent;
          bool isRotate = false;
          while (parent)
          {
               if (parent->_left == cur)     //插入左节点，父亲节点的平衡因子-1
               {
                    parent->_bf--;
               }
               if (parent->_right == cur)   //插入右节点，父亲节点的平衡因子+1
               {
                    parent->_bf++;
               }
               if (parent->_bf == 0)     
                //调整过程中，若碰到平衡因子为0的节点，就不用在继续调整
               {
                    break;
               }
               else if (parent->_bf == -1 || parent->_bf == 1)   //更新平衡因子
               {
                    cur = parent;
                    parent = cur->_parent;
               }
               else
               {
                    if (parent->_bf == 2)
                    {
                         if (cur->_bf == 1)      //左单旋
                         {
                              _RotateL(parent);
                         }
                         else       //右左单旋
                         {
                              _RotateRL(parent);
                         }
                    }
                    else           //=-2
                    {
                         if (cur->_bf == -1)      //右单旋
                         {
                              _RotateR(parent);
                         }
                         else                     //左右单旋
                         {
                              _RotateLR(parent);
                         }  
                    }
                    isRotate = true;
               }
               break;
          }
          
          if (isRotate)
          {
               if (parent->_parent == NULL)
               {
                    _root = parent;
                    return true;
               }
          }
          return true;
     }
     
     void InOrder()     //后序遍历
     {
          _InOrder(_root);
          cout << endl;
     }
     
     bool IsBalance()
     {
          if (_root == NULL)
          {
               cout << "root is null!" << endl;
               return false;
          }
          return _IsBalance(_root);
     }
     
     int Heigth()
     {
          int heigthTree = 0;
          Node* cur = _root;
          while (cur)
          {
               if (cur != NULL)
               {
                    heigthTree++;
               }
               cur = cur->_left;
          }
          return _Heigth(_root, heigthTree, 0);
     }
    
protected:
     int _Heigth(Node* root, int heigthTree, int countNum)
     { 
          if (root == NULL)
          {
               if (countNum > heigthTree)
               {
                    heigthTree = countNum;
               }
               return heigthTree;
          }
          _Heigth(root->_left, heigthTree, countNum++);
          _Heigth(root->_right, heigthTree, countNum++);
     }
     
     bool _IsBalance(Node* root)
     {
          int bf = root->_right->_bf - root->_right->_bf;
          if (bf == 0 || bf == 1 || bf == -1)
          {
               return true;
          }
          else
          {
               return false;
          }
          _IsBalance(root->_left);
          _IsBalance(root->_right);
     }
    
     void _RotateL(Node*& parent)     //左单旋
     {
          Node* SubR = parent->_right;    //新建两个节点指针
          Node* SubRL = SubR->_left;
          parent->_right = SubRL;        //进行调整
          if (SubRL)
          {
               SubRL->_parent = parent;
          }
          SubR->_left = parent;
          SubR->_parent = parent->_parent;
          parent->_parent = SubR;
          parent->_bf = SubR->_bf = 0;    //更改引用计数
          parent = SubR;
     }
     
     void _RotateR(Node*& parent)     //右单旋
     {
          Node* SubL = parent->_left;   //新建两个节点指针
          Node* SubLR = SubL->_right;
          parent->_left = SubLR;    //进行调整
          if (SubLR)
          {
               SubLR->_parent = parent;
          }
          SubL->_right = parent;
          SubL->_parent = parent->_parent;
          parent->_parent = SubL;
          parent->_bf = SubL->_bf = 0;
          parent = SubL;
     }
     
     void _RotateRL(Node*& parent)     //右左单旋
     {
          Node* pNode = parent;
          Node* subRNode = parent->_right;
          Node* subRLNode = subRNode->_left;
          int bf = subRLNode->_bf;
          _RotateR(parent->_right);
          _RotateL(parent);
          if (bf == -1)
          {
               subRNode->_bf = 0;
               pNode->_bf = -1;
          }
          else if (bf == 1)
          {
               subRNode->_bf = 1;
               pNode->_bf = 0;
          }
          else
          {
               subRNode->_bf = 0;
               pNode->_bf = 0;
          }
          subRNode->_bf = 0;
     }
     
     void _RotateLR(Node*& parent)     //左右单旋
     {
          Node* pNode = parent;
          Node* subLNode = parent->_left;
          Node* subLRNode = subLNode->_right;
          int bf = subLRNode->_bf;
          _RotateL(parent->_left);
          _RotateR(parent);
          if (bf == -1)
          {
               subLNode->_bf = 0;
               pNode->_bf = 1;
          }
          else if (bf == 1)
          {
               subLNode->_bf = -1;
               pNode->_bf = 0;
          }
          else
          {
               subLNode->_bf = 0;
               pNode->_bf = 0;
          }
          subLNode->_bf = 0;
     }
     
     void _InOrder(Node* root)
     {
          if (root == NULL)
          {
               return;
          }
          _InOrder(root->_left);
          cout << root->_key << " ";
          _InOrder(root->_right);
     }
     
protected:
     Node* _root;
};

void Test()
{
     AVLTree ht;
     /*ht.Insert(16, 1);
     ht.Insert(3, 1);
     ht.Insert(7, 1);
     ht.Insert(11, 1);
     ht.Insert(9, 1);
     ht.Insert(26, 1);
     ht.Insert(18, 1);
     ht.Insert(14, 1);
     ht.Insert(15, 1);*/
     
     ht.Insert(4, 1);
     ht.Insert(2, 1);
     ht.Insert(6, 1);
     ht.Insert(1, 1);
     ht.Insert(3, 1);
     ht.Insert(5, 1);
     ht.Insert(15, 1);
     ht.Insert(7, 1);
     ht.Insert(16, 1);
     ht.Insert(14, 1);
     
     ht.InOrder();
     cout<
            
            
                        

            网页题目：平衡搜索树—AVLTree            

            URL地址：http://shouzuofang.com/article/igjigi.html