AVL树

AVL树也叫平衡二叉搜索树，通过旋转解决了搜索二叉树的不确定性，让整颗树趋近于一颗满二叉树。

1.左右都是一颗AVL树

2.平衡因子的绝对值不会超过1

上图的蓝字表示平衡因子，平衡因子=右子树的高度-左子树的高度

AVL树节点的定义

template<class K,class V>
struct AVLTreeNode
{
  ALVTreeNode<K,V>* _left;
  AVLTreeNode<K,V>* _right;
  AVLTreeNode<K,V>* _parent;//父亲节点
  pair<K, V> _kv;//  key / value
  //构造函数
  AVLTreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {}
  int _bf;//平衡因子
};

AVL树的定义

template<class K,class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
private:
  Node* _root=nullptr;
};

AVL树的插入

AVL树的插入和二叉搜索树一样，小的在左边，大的在右边，只是当平衡因子绝对值大于1的时候需要对树进行旋转。

bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first < kv.second)
      {
        //当前值小于要插入的值，往右边走
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.second)
      {
        //当前值大于要插入的值，往左边走
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        //有相同的值了，退出插入
        return false;
      }
    }
    //当cur走到了nullptr，就是找到了要插入的点了
    cur = new Node(kv);
    //判断插入在左边还是右边
    if (parent->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;//确定父子关系
  }

插入后更新平衡因子

平衡因子，如果在左边插入节点，那么它的父节点的平衡因子要-1，反之+1

case1:parent节点的平衡因子为0，说明整棵树的高度并没有发生改变，只是补齐了原本缺节点的位置，所以遇到parent->_bf=0的时候，就不需要在修改平衡因子了

case2:parent节点的平衡因子的绝对值为-1，就说明往上走可能存在abs(parent->_bf)=2的，所以要往上一直找。

parent=parent->_parent;

cur=cur->_parent;

如果abs(parent->_bf)=2就需要对其进行旋转来调整树的结构了。

while (parent)
    {
      //更新平衡因子
      if (cur == parent->_left)
      {
        parent->_bf--;
      }
      else
      {
        parent->_bf++;
      }
      if (parent->_bf == 0)
      {
        //没有新增高度
        break;
      }
      else if(abs(parent->_bf)==1)
      {
        //平衡因子为1，往上面继续找
        parent = parent->_parent;
        cur = cur->_parent;
      }
      else if (abs(parent->_bf) == 2)
      {
        //需要旋转了
      }
    }

AVL树的右单旋

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

例如上面的抽象图，当平衡树失衡的时候就需要调节平衡了，过程如上图所示。

具体图如下：

这里的操作就是将subL作为一个根节点，将subLR作为parent的左节点(如果subLR存在的话)，parent作为subL的右子节点。

左旋的条件是parent->_bf==-2&&cur->_bf==-1

旋转之后parent的平衡因子为0，subL的平衡因子也是0。

void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    Node* pparent = parent->_parent;
    //防止空指针
    if (subLR)
    {
      subLR->_parent = parent;
    }
        subL->_right = parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      //如果parent就是根节点
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      //如果parent只是一颗子树的根节点，就还需要连接好parent
      //判断是左还是右节点
      if (pparent->_left == parent)
      {
        pparent->_left = subL;
      }
      else
      {
        pparent->_right = subL;
      }
      subL->_parent = pparent;
    }
    subL->_bf = parent->_bf = 0;
  }

AVL树的左单旋

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

方法和右单旋类似。

当**parent->_bf==2&&cur->_bf==1**的时候触发左单旋

void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pparent = parent->_parent;
    parent->_right = subRL;
    if (subRL)
    {
      subRL->_parent = subR;
    }
    subR->_left = parent;
    parent->_parent = subR;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = subR;
      }
      else
      {
        pparent->_right = subR;;
      }
      subR->_parent = pparent;
    }
    subR->_bf = parent->_bf = 0;
  }

可以发现，如果满足左/右单旋的条件都是在同一条直线上，那如果路径不是在同一条直线上呢？

先左单旋再右单旋

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

如果将节点插入到c当中，平衡因子就会发生改变，所以这里的平衡因子需要分情况讨论。

这里通过subLR的平衡因子来确定是在左边插入还是在右边插入。

两种情况下subLR都是0。

下图是最简单的双旋：

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

先右单旋再左单旋

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

C增加节点之后高度和d一样都是h，将其全部旋转到右边去，然后再通过左旋把30压下去，将60作为根节点。

void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL-> _right;
    int bf = subLR->_bf;//提前存好，旋转后会subLR会发生改变
    RotateL(parent->_left);
    RotateR(parent);
    subLR->_bf = 0;
    if (bf == 1)
    {
      //在右边插入
      parent->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1)
    {
      parent->_bf = 1;
      subL->_bf = 0;
    }
    else if (bf == 0)
    {
      //已经平衡了
      parent->_bf = 0;
      subL->_bf = 0;
    }
    else
    {
      //插入存在问题
      assert(false);
    }
  }

检查是否满足AVL树

通过计算左右子树的高度来确定是否满足AVL树，因为平衡因子是自己设置的，如果还通过平衡因子来确定的话会不太准。

bool _IsBalance(Node* root)
  {
    if (root == nullptr)
    {
      return true;
    }
    int leftHT = Height(root->_left);
    int rightHT = Height(root->_right);
    int diff = rightHT - leftHT;
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
      return false;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)//递归左子树
      && _IsBalance(root->_right);//递归右子树
  }
  int Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    int left = Height(root->_left);
    int right = Height(root->_right);
    return max(left, right) + 1;
  }

手写旋转过程：

总代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
  AVLTreeNode<K,V>* _left;
  AVLTreeNode<K,V>* _right;
  AVLTreeNode<K,V>* _parent;//父亲节点
  pair<K, V> _kv;//  key / value
  //构造函数
  AVLTreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {}
  int _bf;//平衡因子
};
template<class K,class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first < kv.second)
      {
        //当前值小于要插入的值，往右边走
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.second)
      {
        //当前值大于要插入的值，往左边走
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        //有相同的值了，退出插入
        return false;
      }
    }
    //当cur走到了nullptr，就是找到了要插入的点了
    cur = new Node(kv);
    //判断插入在左边还是右边
    if (parent->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;//确定父子关系
    //控制平衡因子
    while (parent)
    {
      if (cur == parent->_right)
      {
        parent->_bf++;
      }
      else
      {
        parent->_bf--;
      }
      if (parent->_bf == 0)
      {
        break;
      }
      else if (abs(parent->_bf) == 1)
      {
        parent = parent->_parent;
        cur = cur->_parent;
      }
      else if (abs(parent->_bf) == 2)
      {
        // 说明parent所在子树已经不平衡了，需要旋转处理
        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)
        {
          RotateLR(parent);
        }
        else if (parent->_bf == 2 && cur->_bf == -1)
        {
          RotateRL(parent);
        }
        else
        {
          assert(false);
        }
        break;
      }
      else
      {
        assert(false);
      }
    }
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  bool IsBalance()
  {
    return _IsBalance(_root);
  }
private:
  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    subRL->_bf = 0;
    if (bf == 1)
    {
      subR->_bf = 0;
      parent->_bf = -1;
    }
    else if (bf == -1)
    {
      subR->_bf = 1;
      parent->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL-> _right;
    int bf = subLR->_bf;//提前存好，旋转后会subLR会发生改变
    RotateL(parent->_left);
    RotateR(parent);
    subLR->_bf = 0;
    if (bf == 1)
    {
      //在右边插入
      parent->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1)
    {
      parent->_bf = 1;
      subL->_bf = 0;
    }
    else if (bf == 0)
    {
      //已经平衡了
      parent->_bf = 0;
      subL->_bf = 0;
    }
    else
    {
      //插入存在问题
      assert(false);
    }
  }
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pparent = parent->_parent;
    parent->_right = subRL;
    if (subRL)
    {
      subRL->_parent = subR;
    }
    subR->_left = parent;
    parent->_parent = subR;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = subR;
      }
      else
      {
        pparent->_right = subR;;
      }
      subR->_parent = pparent;
    }
    subR->_bf = parent->_bf = 0;
  }
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    Node* pparent = parent->_parent;
    //防止空指针
    if (subLR)
    {
      subLR->_parent = parent;
    }
    subL->_right = parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      //如果parent就是根节点
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      //如果parent只是一颗子树的根节点，就还需要连接好parent
      //判断是左还是右节点
      if (pparent->_left == parent)
      {
        pparent->_left = subL;
      }
      else
      {
        pparent->_right = subL;
      }
      subL->_parent = pparent;
    }
    subL->_bf = parent->_bf = 0;
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
    {
      return true;
    }
    int leftHT = Height(root->_left);
    int rightHT = Height(root->_right);
    int diff = rightHT - leftHT;
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
      return false;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }
  int Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    int left = Height(root->_left);
    int right = Height(root->_right);
    return max(left, right) + 1;
  }
private:
  Node* _root=nullptr;
};
void TestAVLTree1()
{
  int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 测试双旋平衡因子调节
  //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  AVLTree<int, int> t1;
  for (auto e : a)
  {
    t1.Insert(make_pair(e, e));
  }
  t1.InOrder();
  cout << "IsBalance:" << t1.IsBalance() << endl;
}

可以看到是满足AVL树的。

【C++】AVL树的实现及测试

AVL树节点的定义

AVL树的定义

AVL树的插入

插入后更新平衡因子

AVL树的右单旋

AVL树的左单旋

先左单旋再右单旋

先右单旋再左单旋

检查是否满足AVL树

总代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++】AVL树的实现及测试

AVL树节点的定义

AVL树的定义

AVL树的插入

插入后更新平衡因子

AVL树的右单旋

AVL树的左单旋

先左单旋再右单旋

先右单旋再左单旋

检查是否满足AVL树

总代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景