温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

平衡搜索树—AVLTree

发布时间:2020-07-15 02:41:33 来源:网络 阅读:396 作者:无心的执着 栏目:编程语言

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


      下面就是一个AVL树:

平衡搜索树—AVLTree

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


      下面是AVLTree中节点的结构:

template <class K, class V>
struct AVLTreeNode
{
     K _key;
     V _value;
     int _bf;     //节点的平衡因子
     AVLTreeNode<K, V>* _parent;     //指向节点的父节点
     AVLTreeNode<K, V>* _left;       //指向节点的左孩子
     AVLTreeNode<K, V>* _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)左单旋


平衡搜索树—AVLTree


(2)右单旋


平衡搜索树—AVLTree


(3)左右双旋


平衡搜索树—AVLTree

(4)右左双旋


平衡搜索树—AVLTree


       针对上面的情况,下面是具体的程序实现:

#pragma once
#include <assert.h>
#include <math.h>
//实现平衡搜索二叉树
//构造AVL树的节点(使用三叉链表)

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

template <class K, class V>
class AVLTree
{
     typedef AVLTreeNode<K, V> 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<int, int> 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<<ht.IsBalance()<<endl;
     cout << ht.Heigth() << endl;
}




向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI