✅<1>主页：我的代码爱吃辣

📃<2>知识讲解：数据结构——AVL树

☂️<3>开发环境：Visual Studio 2022

💬<4>前言：AVL树是对二叉搜索树的严格高度控制，所以AVL树的搜索效率很高，但是这是需要付出很大的代价的，要维护父亲指针，和平衡因子。

1. 先按照二叉搜索树的规则将节点插入到AVL树中

2.根据插入的位置调整平衡因子

编辑

一.AVL的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii

和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

编辑

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

O( )，搜索时间复杂度O( )

二. AVL树节点及整体结构的定义

//AVL树结点
template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode(pair<K,V> kv)
    :_kv(kv),
    _bf(0),
    _left(nullptr),
    _right(nullptr),
    _parent(nullptr)
  {}
  pair<K, V> _kv;              //Key/Value数据
  int _bf;                     //平衡因子
  AVLTreeNode<K, V>* _left;    //结点的左子树
  AVLTreeNode<K, V>* _right;   //结点的右子树
  AVLTreeNode<K, V>* _parent;  //结点的双亲
};
//AVL树定义
template<class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
  bool insert(pair<K,V> kv){}
private:
  Node* _root = nullptr;
};

三. AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么

AVL树的插入过程可以分为两步：

按照二叉搜索树的方式插入新节点
调整节点的平衡因子

插入过程：

1. 先按照二叉搜索树的规则将节点插入到AVL树中

bool insert(pair<K,V> kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      return true;
    }
    Node* cur = _root;//记录当前结点
    Node* parent = nullptr;//记录父亲结点
    while (cur)
    {
      if (kv.first < cur->_kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (kv.first > cur->_kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    //找到了合适的位置，创建新节点，出入位置
     cur = new Node(kv);
    //修改新节点的指向
    if (kv.first < parent->_kv.first)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
        //未完待续....
    }

2.根据插入的位置调整平衡因子

平衡因子：右子树高度减去左子树高度。

cur 插入后，parent 的平衡因子一定需要调整，在插入之前，pParent 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
如果cur插入到parent的右侧，只需给parent的平衡因子+1即可

此时：parent的平衡因子可能有三种情况：0，正负1，正负2

如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足 AVL树的性质，插入成功。
如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新。
如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。

while (parent)
    {
            //cur插入到parent的左侧
      if (parent->_left == cur)
      {
        parent->_bf--;
      }
      else//cur插入到parent的右侧
      {
        parent->_bf++;
      }
            //需向上调整平衡因子
      if (parent->_bf == 1||parent->_bf==-1)
      {
        cur = parent;
        parent = cur->_parent;
      }
            //无需向上调整平衡因子
      else if(parent->_bf==0)
      {
        break;
      }
            //无需向上调整平衡因子，直接旋转处理
      else if (parent->_bf == 2||parent->_bf==-2)
      {
        //旋转,旋转之后平衡因子已经平衡，可以直接推出
        break;
      }
      else//出现的其他的错误情况
      {
        assert(0);
      }
    }

四.AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，

使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1.左单旋

新节点插入较高右子树的右侧

编辑

上图在插入前，AVL树是平衡的，新节点插入到60的右子树中，30右子树增加了一层，导致以60为根的二叉树不平衡，要让30平衡，只能将30右子树的高度减少一层，左子树增加一层，即将右子树往上提，这样30转下来，因为30比60小，只能将其放在60的左子树，而如果60有左子树，左子树根的值一定大于30，小于60，只能将其放在30的右子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

60节点的左孩子可能存在，也可能不存在。
30可能是整棵树根节点，也可能是子树根节点。

如果是整棵树根节点，旋转完成后，要更整棵树新根节点；如果是子树根节点，可能是某个节点的左子树，也可能是右子树。

void RotateL(Node* parent)
  {
    //  a
    //     b
    //        c
    //找到需要旋转的结点
    Node* curR = parent->_right;
    Node* curRL = curR->_left;
    //调整结点，并且修改其父亲结点指针
    parent->_right = curRL;
    if (curRL)//可能为空
    {
      curRL->_parent = parent;
    }
    //在修改子树根节点之前，保存子树根节点的父亲
    Node* pparent = parent->_parent;
    //修改子树根节点
    curR->_left = parent;
    parent->_parent = curR;
    //子树根节点有可能是整棵树的根节点
    if (pparent == nullptr)
    {
      _root = curR;
      _root->_parent = nullptr;
    }
    else//子树根节点不是整棵树的根节点
    {
      //还要看子树是它父亲的左孩子还是右孩子
      if (pparent->_left == parent)
      {
        pparent->_left = curR;
      }
      else
      {
        pparent->_right = curR;
      }
      curR->_parent = pparent;
    }
    //修改平衡因子
    curR->_bf = parent->_bf = 0;
  }

2.右单旋

新节点插入较高左子树的左侧

编辑

右单旋过程和左单旋转过程一模一样仅仅只是反过来。

void RotateR(Node* parent)
  {
    Node* curL = parent->_left;
    Node* curLR = curL->_right;
    parent->_left = curLR;
    if (curLR)
    {
      curLR->_parent = parent;
    }
    Node* pparent = parent->_parent;
    curL->_right = parent;
    parent->_parent = curL;
    if (parent == _root)
    {
      _root = curL;
      _root->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = curL;
      }
      else
      {
        pparent->_right = curL;
      }
      curL->_parent = pparent;
    }
    curL->_bf = parent->_bf = 0;
  }

3.左右双旋

新节点插入较高左子树的右侧---左右：先左单旋再右单旋

编辑

将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再

考虑平衡因子的更新。

注意：旋转之前，60的平衡因子可能是 -1 / 0 / 1，旋转完成之后，根据情况对其他节点的平衡因子进行调整。

编辑

当h=0,时60自己就是一个新插入的结点，此时他的平衡因子就是。

所以旋转之前，需要保存curLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节

点的平衡因子。

void RotateLR(Node* parent)
  {
    Node* curL = parent->_left;
    Node* curLR = curL->_right;
    //旋转之前，保存curLR的平衡因子，旋转完成之后，
    //需要根据该平衡因子来调整其他节点的平衡因子
    int curLR_bf = curLR->_bf;
    //先左单旋
    RotateL(curL);
        //再右单旋
    RotateR(parent);
        //保存curLR的平衡因子，判断插入结点的位置，根据插入结点的位置，
        //判断出其他结点的平衡因子
    if (curLR_bf == -1)
    {
      parent->_bf = 1;
      curLR->_bf = 0;
      curL->_bf = 0;
    }
    else if (curLR_bf == 1)
    {
      parent->_bf = 0;
      curL->_bf = -1;
      curLR->_bf = 0;
    }
    else if (curLR_bf == 0)
    {
      parent->_bf = 0;
      curL->_bf = 0;
      curLR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }

4.右左双旋

右左双旋和左右双旋过程一模一样，仅仅只是反过来。

编辑

void RotateRL(Node* parent)
  {
    Node* curR = parent->_right;
    Node* curRL = curR->_left;
    int curRL_bf = curRL->_bf;
    RotateR(curR);
    RotateL(parent);
    if (curRL_bf == -1)
    {
      parent->_bf = 0;
      curRL->_bf = 0;
      curR->_bf = 1;
    }
    else if (curRL_bf == 1)
    {
      parent->_bf = -1;
      curRL->_bf = 0;
      curR->_bf = 0;
    }
    else if (curRL_bf == 0)
    {
      parent->_bf = 0;
      curRL->_bf = 0;
      curR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }

5.总结：

假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

1. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为curR

当curR的平衡因子为1时，执行左单旋
当curR的平衡因子为-1时，执行右左双旋

2. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为curL

当curL的平衡因子为-1是，执行右单旋
当curL的平衡因子为1时，执行左右双旋

旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。

//调整平衡因子
    while (parent)
    {
      if (parent->_left == cur)
      {
        parent->_bf--;
      }
      else
      {
        parent->_bf++;
      }
      if (parent->_bf == 1||parent->_bf==-1)//需向上调整平衡因子
      {
        cur = parent;
        parent = cur->_parent;
      }
      else if(parent->_bf==0)//无需向上调整平衡因子
      {
        break;
      }
      else if (parent->_bf == 2||parent->_bf==-2)//无需向上调整平衡因子，直接旋转
      {
        if (parent->_bf == 2 && parent->_right->_bf == 1)
        {
          RotateL(parent);//左单旋
        }
        else if (parent->_bf == -2 && parent->_left->_bf == -1)
        {
          RotateR(parent);//右单旋
        }
        else if (parent->_bf == 2 && parent->_left->_bf == -1)
        {
          RotateRL(parent);//右左双旋
        }
        else if (parent->_bf == -2 && parent->_left ->_bf== 1)
        {
          RotateLR(parent);//左右双旋
        }
        else
        {
          assert(false);//其他错误情况
        }
        break;
      }
      else
      {
        assert(0);
      }

五.AVL树的删除(了解)

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不

错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

具体实现学生们可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

六.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这

样可以保证查询时高效的时间复杂度，即。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

七.完整代码及测试

AVL.hpp

#pragma once
#include<iostream>
#include<cassert>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode(pair<K,V> kv)
    :_kv(kv),
    _bf(0),
    _left(nullptr),
    _right(nullptr),
    _parent(nullptr)
  {
  }
  pair<K, V> _kv;              //Key/Value数据
  int _bf;                     //平衡因子
  AVLTreeNode<K, V>* _left;    //结点的左子树
  AVLTreeNode<K, V>* _right;   //结点的右子树
  AVLTreeNode<K, V>* _parent;  //结点的双亲
};
template<class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
  bool insert(pair<K,V> kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (kv.first < cur->_kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (kv.first > cur->_kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    //找到了合适的位置
     cur = new Node(kv);
    //
    if (kv.first < parent->_kv.first)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    //调整平衡因子
    while (parent)
    {
      if (parent->_left == cur)
      {
        parent->_bf--;
      }
      else
      {
        parent->_bf++;
      }
      if (parent->_bf == 1||parent->_bf==-1)//需向上调整平衡因子
      {
        cur = parent;
        parent = cur->_parent;
      }
      else if(parent->_bf==0)//无需向上调整平衡因子
      {
        break;
      }
      else if (parent->_bf == 2||parent->_bf==-2)//无需向上调整平衡因子，直接旋转
      {
        if (parent->_bf == 2 && cur->_bf == 1)
        {
          RotateL(parent);//左单旋
        }
        else if (parent->_bf == -2 && cur->_bf == -1)
        {
          RotateR(parent);//右单旋
        }
        else if (parent->_bf == 2 && cur->_bf == -1)
        {
          RotateRL(parent);//右左双旋
        }
        else if (parent->_bf == -2 && cur ->_bf== 1)
        {
          RotateLR(parent);//左右双旋
        }
        else
        {
          //cout << parent->_bf << ":" << /*parent->_left->_bf << ":" <<*/ parent->_right->_bf << endl;
          assert(false);//其他错误情况
        }
        break;
      }
      else
      {
        assert(false);
      }
    }
    return true;
  }
  void Inorder()
  {
    _inorder(_root);
    cout << endl;
  }
  bool Isbalance()
  {
    return _Isbalance(_root);
  }
private:
  int _Height(Node* root)
  {
    if (root == nullptr)
    {
      return 0;
    }
    int Hleft = _Height(root->_left);
    int Hright = _Height(root->_right);
    return Hleft > Hright ? Hleft + 1 : Hright + 1;
  }
  bool _Isbalance(Node* root)
  {
    if (root == nullptr)
    {
      return true;
    }
    int Hleft = _Height(root->_left);
    int Hright = _Height(root->_right);
    return (Hright - Hleft <= 1) && _Isbalance(root->_left) && _Isbalance(root->_right);
  }
  void _inorder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _inorder(root->_left);
    cout << root->_kv.first << " ";
    _inorder(root->_right);
  }
  void RotateL(Node* parent)
  {
    //  a
    //     b
    //        c
    //找到需要旋转的结点
    Node* curR = parent->_right;
    Node* curRL = curR->_left;
    //调整结点，并且修改其父亲结点指针
    parent->_right = curRL;
    if (curRL)//可能为空
    {
      curRL->_parent = parent;
    }
    //在修改子树根节点之前，保存子树根节点的父亲
    Node* pparent = parent->_parent;
    //修改子树根节点
    curR->_left = parent;
    parent->_parent = curR;
    //子树根节点有可能是整棵树的根节点
    if (pparent == nullptr)
    {
      _root = curR;
      _root->_parent = nullptr;
    }
    else//子树根节点不是整棵树的根节点
    {
      //还要看子树是它父亲的左孩子还是右孩子
      if (pparent->_left == parent)
      {
        pparent->_left = curR;
      }
      else
      {
        pparent->_right = curR;
      }
      curR->_parent = pparent;
    }
    //修改平衡因子
    curR->_bf = parent->_bf = 0;
  }
  void RotateR(Node* parent)
  {
    Node* curL = parent->_left;
    Node* curLR = curL->_right;
    parent->_left = curLR;
    if (curLR)
    {
      curLR->_parent = parent;
    }
    Node* pparent = parent->_parent;
    curL->_right = parent;
    parent->_parent = curL;
    if (parent == _root)
    {
      _root = curL;
      _root->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = curL;
      }
      else
      {
        pparent->_right = curL;
      }
      curL->_parent = pparent;
    }
    curL->_bf = parent->_bf = 0;
  }
  void RotateLR(Node* parent)
  {
    Node* curL = parent->_left;
    Node* curLR = curL->_right;
    //旋转之前，保存pSubLR的平衡因子，旋转完成之后，
    //需要根据该平衡因子来调整其他节点的平衡因子
    int curLR_bf = curLR->_bf;
    //
    RotateL(curL);
    RotateR(parent);
    if (curLR_bf == -1)
    {
      parent->_bf = 1;
      curLR->_bf = 0;
      curL->_bf = 0;
    }
    else if (curLR_bf == 1)
    {
      parent->_bf = 0;
      curL->_bf = -1;
      curLR->_bf = 0;
    }
    else if (curLR_bf == 0)
    {
      parent->_bf = 0;
      curL->_bf = 0;
      curLR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  void RotateRL(Node* parent)
  {
    Node* curR = parent->_right;
    Node* curRL = curR->_left;
    int curRL_bf = curRL->_bf;
    RotateR(curR);
    RotateL(parent);
    if (curRL_bf == -1)
    {
      parent->_bf = 0;
      curRL->_bf = 0;
      curR->_bf = 1;
    }
    else if (curRL_bf == 1)
    {
      parent->_bf = -1;
      curRL->_bf = 0;
      curR->_bf = 0;
    }
    else if (curRL_bf == 0)
    {
      parent->_bf = 0;
      curRL->_bf = 0;
      curR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  Node* _root = nullptr;
};

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"AVL.hpp"
int main()
{
  AVLTree<int, int> a;
  int i = 1000;
  while(i--)
  {
    int num = rand() + i;
    a.insert(make_pair(num,num));
  }
  cout << a.Isbalance() << endl;
  return 0;
}

编辑

AVL——平衡搜索树

一.AVL的概念

二. AVL树节点及整体结构的定义

三. AVL树的插入

1. 先按照二叉搜索树的规则将节点插入到AVL树中

2.根据插入的位置调整平衡因子

四.AVL树的旋转

1.左单旋

2.右单旋

3.左右双旋

4.右左双旋

5.总结：

五.AVL树的删除(了解)

六.AVL树的性能

七.完整代码及测试

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

AVL——平衡搜索树

一.AVL的概念

二. AVL树节点及整体结构的定义

三. AVL树的插入

1. 先按照二叉搜索树的规则将节点插入到AVL树中

2.根据插入的位置调整平衡因子

四.AVL树的旋转

1.左单旋

2.右单旋

3.左右双旋

4.右左双旋

5.总结：

五.AVL树的删除(了解)

六.AVL树的性能

七.完整代码及测试

热门文章

最新文章

相关电子书