欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AVL树的旋转剖析、插入实现、以及判断是不是一棵平衡树或二叉搜索树

程序员文章站 2022-06-07 08:15:23
...

AVL树(平衡树)是绝对平衡的。

1.概念:

左右子树的高度之差的绝对值不超过1。
一棵AVL树可以为空树,或者具有以下性质的树:
(1)左右子树都为AVL树。
(2)左右子树的高度之差的绝对值不超过1。
AVL树的旋转剖析、插入实现、以及判断是不是一棵平衡树或二叉搜索树

2.旋转

旋转 场景
左单旋 较高右子树的右侧
右单旋 较高左子树的左侧
先右旋后左旋 插入结点在较高左子树的右侧
先左旋后右旋 插入结点在较高右子树的左侧

左单旋:较高右子树的右侧

AVL树的旋转剖析、插入实现、以及判断是不是一棵平衡树或二叉搜索树

//左单旋(插入在较高右子树的右侧)
     void RotateL(PNode pParent)
     {
          PNode subR = pParent->_pRight;
          PNode subRL = subR->_pLeft;
          PNode ppParent = pParent->_parent;
          pParent->_pRight = subRL;
          subR->_pLeft = pParent;
          if (subRL)//subRL存在
              subRL->_parent = pParent;

          if (pParent == _pRoot)
              _pRoot = subR;
          else if (ppParent->_pLeft ==pParent)
          {
              subR->_parent = ppParent;
              ppParent->_pLeft = subR;
          }
          else
          {
              subR->_parent = ppParent;
              ppParent->_pRight = subR;
          }
          //更新平衡因子
          pParent->bf = subR->bf = 0;
     }

右单旋:较高左子树的左侧

AVL树的旋转剖析、插入实现、以及判断是不是一棵平衡树或二叉搜索树

//右单旋(插入在较高左子树的左侧)
     void RotateR(PNode pParent)
     {
          PNode subL = pParent->_pLeft;
          PNode subLR = subL->_pRight;
          PNode ppParent = pParent->_parent;
          pParent->_pLeft = subLR;
          subL->_pRight = pParent;
          if (subLR)
              subLR->_parent = pParent;
          if (pParent == _pRoot)
              _pRoot = subL;
          else if (ppParent->_pLeft == pParent)
          {
              subLR->_parent = ppParent;
              ppParent->_pLeft = subL;
          }
          else
          {
              subLR->_parent = ppParent;
              ppParent->_pRight = subL;
          }
          //更新平衡因子
          pParent->bf = subL->bf = 0;
     }

先右旋后左旋:插入结点在较高左子树的右侧

AVL树的旋转剖析、插入实现、以及判断是不是一棵平衡树或二叉搜索树

//先右单旋后左单旋(插入在较高左子树的右侧)
     void RotateRL(PNode pParent)
     {
          PNode subR = pParent->_pRight;
          PNode subRL = subR->_pLeft;
          int bf = 0;
          if (subRL)
              bf = subRL->bf;
          RotateR(subR);
          RotateL(pParent);
          //更新平衡因子
          if (bf == 1 || bf == -1)
              subR->bf = pParent->bf = 0;
     }

先左旋后右旋:插入结点在较高右子树的左侧

AVL树的旋转剖析、插入实现、以及判断是不是一棵平衡树或二叉搜索树

//先左单旋后右单旋(插入在较高右子树的左侧)
     void RotateLR(PNode pParent)
     {
          PNode subL = pParent->_pLeft;
          PNode subLR = subL->_pRight;
          int bf = 0;
          if(subLR)
              bf = subLR->bf;
          RotateL(subL);
          RotateR(pParent);
          //更新平衡因子
          if (bf == 1)
              subL->bf = -1;
          else if (bf == -1)
              pParent->bf = 1;
     }

3.插入

①空树—->直接插入
②非空—->找待插入的位置—>更新(平衡因子)

双亲的平衡因子 插入左子树 插入右子树
-1 -2 0
0 -1 1
1 0 2

调整双亲的平衡因子后如果为0,不需更新。
如果为-1/1,向上更新,不满足平衡因子,分情况旋转

//插入结点
     bool Insert(const K& key, const V& value)
     {
          PNode pCur = _pRoot;
          PNode pParent = NULL;
          //树为空
          if (_pRoot == NULL)
          {
              _pRoot = new Node(key, value);
              return true;
          }
          //树非空
          //1.找到待插入的结点的位置
          while (pCur)
          {
              if (key == pCur->_key)
                   return false;
              else if (key < pCur->_key)
              {
                   pParent = pCur;
                   pCur = pCur->_pLeft;
              }
              else
              {
                   pParent = pCur;
                   pCur = pCur->_pRight;
              }
              if (pCur)
                   pCur->_parent = pParent;
          }

          //2.插入
          pCur =new Node(key, value);
          if (key<pParent->_key)
              pParent->_pLeft = pCur;
          if (key>pParent->_key)
              pParent->_pRight = pCur;
          //3.更新平衡因子
          while (pParent)
          {
              if (key < pParent->_key)
                   pParent->bf--;
              else
                   pParent->bf++;
              if (pParent->bf == 0)//结束平衡化处理
                   break;
              else if (pParent->bf == -1 || pParent->bf == 1)
              {
                   //向上更新
                   pCur = pParent;
                   pParent = pCur->_parent;
              }
              else
              {
                   //分情况旋转
                   if (pParent->bf == 2)//右子树高
                   {
                        if (pCur->bf == 1)
                             RotateL(pParent);//左单旋转
                        else
                             RotateRL(pParent);//先右后左旋转
                   }
                   else//左子树高
                   {
                        if (pCur->bf == -1)
                             RotateR(pParent);//右单旋转
                        else
                             RotateLR(pParent);//先左后右旋转
                   }
                   break;
              }
          }
          return true;
     }

4.判断是否为一棵平衡树或二叉搜索树

判断一个树是否为二叉搜索树:中序遍历—>有序
判断二叉搜索树是否为平衡树:IsBalanced
空树—>平衡
树存在—->求左右子树的高度,判断是否平衡(abs(左,右)<2)

public:
//中序遍历,检查是否为二叉搜索树
     void InOrder()
     {
          if (_pRoot)
              _InOrder(_pRoot);
     }
     //判断是否平衡
     void IsBalance()
     {
          if (_pRoot)
              _IsBalance(_pRoot);
     }
private:
     bool _IsBalance(PNode pRoot)
     {
          if (pRoot == NULL)
              return true;

          else
          {
              int hL = Height(pRoot);
              int hR = Height(pRoot);
              int a = hR - hL;
              if (abs(a) >= 2)
                   return false;
              return _IsBalance(pRoot->_pLeft) && _IsBalance(pRoot->_pRight);
          }
     }
     //求二叉树的高度
     size_t Height(PNode& pRoot)
     {
          if (pRoot == NULL)
              return 0;
          else if (pRoot->_pLeft == NULL&&pRoot->_pRight == NULL)
              return 1;
          else
              return Height(pRoot->_pLeft) > Height(pRoot->_pRight) ? (Height(pRoot->_pLeft) + 1): (Height(pRoot->_pRight) + 1);
     }

5.删除

空树—->跳出

双亲的平衡因子 删除左子树 删除右子树
-1 0 -2
0 1 -1
1 2 0

完整代码:

#pragma once
#include <iostream>
using namespace std;
#include <math.h>
template <class K, class V>
struct AVLNode
{
     AVLNode(const K& key, const V& value)
     : _pLeft(NULL)
     , _pRight(NULL)
     , _parent(NULL)
     , _key(key)
     , _value(value)
     , bf(0)
     {}
     AVLNode<K, V>* _pLeft;
     AVLNode<K, V>* _pRight;
     AVLNode<K, V>* _parent;
     K _key;
     V _value;
     int bf;
};
template <class K, class V>
class AVLTree
{
public:
     typedef AVLNode<K, V> Node;
     typedef Node* PNode;
     //构造函数
     AVLTree()
          :_pRoot(NULL)
     {}
     //插入结点
     bool Insert(const K& key, const V& value)
     {
          PNode pCur = _pRoot;
          PNode pParent = NULL;
          //树为空
          if (_pRoot == NULL)
          {
              _pRoot = new Node(key, value);
              return true;
          }
          //树非空
          //1.找到待插入的结点的位置
          while (pCur)
          {
              if (key == pCur->_key)
                   return false;
              else if (key < pCur->_key)
              {
                   pParent = pCur;
                   pCur = pCur->_pLeft;
              }
              else
              {
                   pParent = pCur;
                   pCur = pCur->_pRight;
              }
              if (pCur)
                   pCur->_parent = pParent;
          }

          //2.插入
          pCur =new Node(key, value);
          if (key<pParent->_key)
              pParent->_pLeft = pCur;
          if (key>pParent->_key)
              pParent->_pRight = pCur;
          //3.更新平衡因子
          while (pParent)
          {
              if (key < pParent->_key)
                   pParent->bf--;
              else
                   pParent->bf++;
              if (pParent->bf == 0)//结束平衡化处理
                   break;
              else if (pParent->bf == -1 || pParent->bf == 1)
              {
                   //向上更新
                   pCur = pParent;
                   pParent = pCur->_parent;
              }
              else
              {
                   //分情况旋转
                   if (pParent->bf == 2)//右子树高
                   {
                        if (pCur->bf == 1)
                             RotateL(pParent);//左单旋转
                        else
                             RotateRL(pParent);//先右后左旋转
                   }
                   else//左子树高
                   {
                        if (pCur->bf == -1)
                             RotateR(pParent);//右单旋转
                        else
                             RotateLR(pParent);//先左后右旋转
                   }
                   break;
              }
          }
          return true;
     }
     //中序遍历,检查是否为二叉搜索树
     void InOrder()
     {
          if (_pRoot)
              _InOrder(_pRoot);
     }
     //判断是否平衡
     void IsBalance()
     {
          if (_pRoot)
              _IsBalance(_pRoot);
     }
private:
     //左单旋(插入在较高右子树的右侧)
     void RotateL(PNode pParent)
     {
          PNode subR = pParent->_pRight;
          PNode subRL = subR->_pLeft;
          PNode ppParent = pParent->_parent;
          pParent->_pRight = subRL;
          subR->_pLeft = pParent;
          if (subRL)//subRL存在
              subRL->_parent = pParent;

          if (pParent == _pRoot)
              _pRoot = subR;
          else if (ppParent->_pLeft ==pParent)
          {
              subR->_parent = ppParent;
              ppParent->_pLeft = subR;
          }
          else
          {
              subR->_parent = ppParent;
              ppParent->_pRight = subR;
          }
          //更新平衡因子
          pParent->bf = subR->bf = 0;
     }
     //右单旋(插入在较高左子树的左侧)
     void RotateR(PNode pParent)
     {
          PNode subL = pParent->_pLeft;
          PNode subLR = subL->_pRight;
          PNode ppParent = pParent->_parent;
          pParent->_pLeft = subLR;
          subL->_pRight = pParent;
          if (subLR)
              subLR->_parent = pParent;
          if (pParent == _pRoot)
              _pRoot = subL;
          else if (ppParent->_pLeft == pParent)
          {
              subLR->_parent = ppParent;
              ppParent->_pLeft = subL;
          }
          else
          {
              subLR->_parent = ppParent;
              ppParent->_pRight = subL;
          }
          //更新平衡因子
          pParent->bf = subL->bf = 0;
     }
     //先右单旋后左单旋(插入在较高左子树的右侧)
     void RotateRL(PNode pParent)
     {
          PNode subR = pParent->_pRight;
          PNode subRL = subR->_pLeft;
          int bf = 0;
          if (subRL)
              bf = subRL->bf;
          RotateR(subR);
          RotateL(pParent);
          //更新平衡因子
          if (bf == 1 || bf == -1)
              subR->bf = pParent->bf = 0;
     }
     //先左单旋后右单旋(插入在较高右子树的左侧)
     void RotateLR(PNode pParent)
     {
          PNode subL = pParent->_pLeft;
          PNode subLR = subL->_pRight;
          int bf = 0;
          if(subLR)
              bf = subLR->bf;
          RotateL(subL);
          RotateR(pParent);
          //更新平衡因子
          if (bf == 1)
              subL->bf = -1;
          else if (bf == -1)
              pParent->bf = 1;
     }
     //中序遍历
     void _InOrder(PNode pRoot)
     {
          if (!pRoot)
              return;
          _InOrder(pRoot->_pLeft);
          cout << "<" << pRoot->_key << "," << pRoot->_value << ">" << endl;
          _InOrder(pRoot->_pRight);
     }
     bool _IsBalance(PNode pRoot)
     {
          if (pRoot == NULL)
              return true;

          else
          {
              int hL = Height(pRoot);
              int hR = Height(pRoot);
              int a = hR - hL;
              if (abs(a) >= 2)
                   return false;
              return _IsBalance(pRoot->_pLeft) && _IsBalance(pRoot->_pRight);
          }
     }
     //求二叉树的高度
     size_t Height(PNode& pRoot)
     {
          if (pRoot == NULL)
              return 0;
          else if (pRoot->_pLeft == NULL&&pRoot->_pRight == NULL)
              return 1;
          else
              return Height(pRoot->_pLeft) > Height(pRoot->_pRight) ? (Height(pRoot->_pLeft) + 1): (Height(pRoot->_pRight) + 1);
     }
private:
     PNode _pRoot;
};
void AVLTreeTest()
{
     int array[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
     AVLTree<int, int> tree;
     for (size_t i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
          tree.Insert(array[i], array[i]);
     tree.InOrder();
     tree.IsBalance();
}