AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

C++实现AVL树

2023-11-24 62
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： C++实现AVL树

前言

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一、AVL树的概念

AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。


AVL树的定义：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。


AVL树的性质：

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O ( l o g 2 n ) O(log_2 n)O(log 2 n)，搜索时间复杂度O ( l o g 2 n ) O(log_2 n)O(log 2 n)。

二、AVL树节点的定义

AVL树节点的定义：

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

三、AVL树的插入操作

AVL树就是在二叉搜索树的基础之上引入了平衡因子，因此AVL树也可以看出是二叉搜索树。那么AVL树的插入过程可以分成两部分：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整平衡因子，若遇到平衡因子不符合AVL树的规则，则需要进行旋转操作
  bool Insert(const pair<K, V>& kv)
  {
    // 1、搜索树的插入规则
    // 2、看是否违反平衡规则，若违反则需要“旋转”处理
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_bf = 0;
      return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
    //找到了插入位置
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
    //更新平衡因子
    while (parent) //最远更新到parent
    {
      if (cur == parent->_right)
      {
        parent->_bf++;
      }
      else
      {
        parent->_bf--;
      }
      //判断是否继续更新
      if (parent->_bf == 0)
      {
        break;
      }
      else if (parent->_bf == -1 || parent->_bf == 1) // 此时插入结点的那边变高了
      {
        //继续更新祖先
        cur = cur->_parent;
        parent = parent->_parent;
      }
      else if (parent->_bf == -2 || parent->_bf == 2) // 插入结点使得本来高的一边又变高了 -> 旋转
      {
        if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
        {
          // 左单旋
        }
        else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋
        {
          // 右单旋
        }
        else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋
        {
          // 左右双旋
        }
        else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
        {
          // 右左双旋
        }
        else
        {
          assert(false);
        }
        break;
      }
      else
      {
        assert(false);  // 树本来就存在问题
      }
    }
    return true;
  }


四、AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种。

1. 左单旋

新节点插入较高右子树的右侧—右右，即需要左单旋。

图示：

左单旋代码;

  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if(subRL)
      subRL->_parent = parent;
    Node* grandParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (parent == grandParent->_left)
      {
        grandParent->_left = subR;
      }
      else
      {
        grandParent->_right = subR;
      }
      subR->_parent = grandParent;
    }
    subR->_bf = parent->_bf = 0; //更新平衡因子
  }

2. 右单旋

新节点插入较高左子树的左侧—左左，即需要右单旋。

图示:

右单旋代码：

  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    Node* grandParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (parent == grandParent->_left)
      {
        grandParent->_left = subL;
      }
      else
      {
        grandParent->_right = subL;
      }
      subL->_parent = grandParent;
    }
    subL->_bf = parent->_bf = 0;
  }


3. 左右双旋

新节点插入较高左子树的右侧—左右，即需要先左单旋再右单旋。

图示：

此时在60的子树插入一个新节点就会引起左右双旋，插入分为左子树插入和右子树插入。这两种情况的插入完成之后对其平衡因子的更新有所不同，因此旋转完成后需要讨论更新其平衡因子。

当60结点不存在时也需要单独讨论

实现代码：复用左、右单旋。

  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    //更新平衡因子
    if (1 == bf)
      subL->_bf = -1;
    else if (-1 == bf)
      parent->_bf = 1;
    else
    {
      assert(false);
    }
  }


4. 右左双旋

新节点插入较高右子树的左侧—右左，即需要先右单旋再左单旋。

右左双旋与左右双旋类似。

代码实现：

  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    //更新平衡因子
    if (1 == bf)
    {
      parent->_bf = -1;
    }
    else if(-1 == bf)
    {
      subR->_bf = 1;
    }
    else
    {
      assert(false);
    }
  }


5. 总结

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


  1. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋；当subR的平衡因子为-1时，执行右左双旋。
  2. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋；当subL的平衡因子为1时，执行左右双旋。
  3. 旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。

五、AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1、验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。

验证代码如下：

  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
    void _InOrder(Node* root)
  {
    if (root == nullptr)
      return;
    _InOrder(root->_left);
    cout << root->_kv.first << " ";
    _InOrder(root->_right);
  }

2、验证其为平衡树

验证规则：

  1. 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子的情况)
  2. 节点的平衡因子是否计算正确

验证代码如下：

bool IsBalanceTree()
{
  return _IsBalanceTree(_root);
}
bool _IsBalanceTree(Node* root)
  {
    // 空树也是AVL树
    if (nullptr == root)
      return true;
    // 计算root节点的平衡因子：即root左右子树的高度差
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;
    // 如果计算出的平衡因子与root的平衡因子不相等，或者
    // root平衡因子的绝对值超过1，则一定不是AVL树
    if (abs(diff) >= 2) //每个节点子树高度差的绝对值不超过1
    {
      cout << root->_kv.first << "节点平衡因子异常" << endl;
      return false;
    }
    if (diff != root->_bf) //节点的平衡因子是否计算正确
    {
      cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
      return false;
    }
    // root的左和右如果都是AVL树，则该树一定是AVL树
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
  }


六、AVL树的性能分析

  • AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O ( l o g 2 n ) O(log_2 n)O(log 2 n)。
  • 但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

实现AVL树的完整代码

#pragma once
#include<assert.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
  pair<K, V> _kv;
  AVLTreeNode<K, V>* _left; //该节点的左孩子
  AVLTreeNode<K, V>* _right;  //该节点的右孩子
  AVLTreeNode<K, V>* _parent;  //该节点的双亲
  int _bf; //平衡因子
  AVLTreeNode(const pair<K,V>& kv) //构造函数
    :_kv(kv)
    ,_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_bf(0)
  {}
};
template <class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K,V> Node;
public:
  bool Insert(const pair<K, V>& kv)
  {
    // 1、搜索树的插入规则
    // 2、看是否违反平衡规则，若违反则需要“旋转”处理
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_bf = 0;
      return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
    //找到了插入位置
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
    //更新平衡因子
    while (parent) //最远更新到parent
    {
      if (cur == parent->_right)
      {
        parent->_bf++;
      }
      else
      {
        parent->_bf--;
      }
      //判断是否继续更新
      if (parent->_bf == 0)
      {
        break;
      }
      else if (parent->_bf == -1 || parent->_bf == 1) // 此时插入结点的那边变高了
      {
        //继续更新祖先
        cur = cur->_parent;
        parent = parent->_parent;
      }
      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) // 左右双旋
        {
          RotateLR(parent);
        }
        else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
        {
          RotateRL(parent);
        }
        else
        {
          assert(false);
        }
        break;
      }
      else
      {
        assert(false);  // 树本来就存在问题
      }
    }
    return true;
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  bool IsBalanceTree()
  {
    return _IsBalanceTree(_root);
  }
  vector<vector<int>> levelOrder() {
    vector<vector<int>> vv;
    if (_root == nullptr)
      return vv;
    queue<Node*> q;
    int levelSize = 1;
    q.push(_root);
    while (!q.empty())
    {
      // levelSize控制一层一层出
      vector<int> levelV;
      while (levelSize--)
      {
        Node* front = q.front();
        q.pop();
        levelV.push_back(front->_kv.first);
        if (front->_left)
          q.push(front->_left);
        if (front->_right)
          q.push(front->_right);
      }
      vv.push_back(levelV);
      for (auto e : levelV)
      {
        cout << e << " ";
      }
      cout << endl;
      // 上一层出完，下一层就都进队列
      levelSize = q.size();
    }
    return vv;
  }
  int Height()
  {
    return _Height(_root);
  }
private:
  bool _IsBalanceTree(Node* root)
  {
    // 空树也是AVL树
    if (nullptr == root)
      return true;
    // 计算root节点的平衡因子：即root左右子树的高度差
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;
    // 如果计算出的平衡因子与root的平衡因子不相等，或者
    // root平衡因子的绝对值超过1，则一定不是AVL树
    if (abs(diff) >= 2) // 每个节点子树高度差的绝对值不超过1
    {
      cout << root->_kv.first << "节点平衡因子异常" << endl;
      return false;
    }
    if (diff != root->_bf) // 节点的平衡因子是否计算正确
    {
      cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
      return false;
    }
    // root的左和右如果都是AVL树，则该树一定是AVL树
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
      return;
    _InOrder(root->_left);
    cout << root->_kv.first << " ";
    _InOrder(root->_right);
  }
  int _Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    int lh = _Height(root->_left);
    int rh = _Height(root->_right);
    return lh > rh ? lh + 1 : rh + 1;
  }
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if(subRL)
      subRL->_parent = parent;
    Node* grandParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (parent == grandParent->_left)
      {
        grandParent->_left = subR;
      }
      else
      {
        grandParent->_right = subR;
      }
      subR->_parent = grandParent;
    }
    subR->_bf = parent->_bf = 0; //更新平衡因子
  }
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    Node* grandParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (parent == grandParent->_left)
      {
        grandParent->_left = subL;
      }
      else
      {
        grandParent->_right = subL;
      }
      subL->_parent = grandParent;
    }
    subL->_bf = parent->_bf = 0;
  }
  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    //更新平衡因子
    if (1 == bf)
      subL->_bf = -1;
    else if (-1 == bf)
      parent->_bf = 1;
    else
    {
      assert(false);
    }
  }
  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    //更新平衡因子
    if (1 == bf)
    {
      parent->_bf = -1;
    }
    else if(-1 == bf)
    {
      subR->_bf = 1;
    }
    else
    {
      assert(false);
    }
  }
private:
  Node* _root = nullptr;
};
文章标签：
C++
关键词：
C++ avl
C++ avl树
求知.
目录
相关文章
源码星辰
|
2月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树：它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
源码星辰
27 2
枫叶丹4
|
3月前
|
C++ 容器
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树
枫叶丹4
32 5
დ旧言~
|
4月前
|
C++
【C++】手撕AVL树（下）
【C++】手撕AVL树（下）
დ旧言~
51 1
Eternity._
|
4月前
|
算法 测试技术 C++
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
Eternity._
35 2
დ旧言~
|
4月前
|
Java C++ Python
【C++】手撕AVL树（上）
【C++】手撕AVL树（上）
დ旧言~
52 0
GR鲸鱼
|
6月前
|
C语言 C++
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)（下）
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)
GR鲸鱼
49 2
嘎嘎旺
|
5月前
|
C++
【c++】avl树
【c++】avl树
嘎嘎旺
33 0
ephemerals__
|
8天前
|
存储 编译器 C++
【c++】类和对象（中）（构造函数、析构函数、拷贝构造、赋值重载）
本文深入探讨了C++类的默认成员函数，包括构造函数、析构函数、拷贝构造函数和赋值重载。构造函数用于对象的初始化，析构函数用于对象销毁时的资源清理，拷贝构造函数用于对象的拷贝，赋值重载用于已存在对象的赋值。文章详细介绍了每个函数的特点、使用方法及注意事项，并提供了代码示例。这些默认成员函数确保了资源的正确管理和对象状态的维护。
ephemerals__
34 4
ephemerals__
|
9天前
|
存储 编译器 Linux
【c++】类和对象（上）（类的定义格式、访问限定符、类域、类的实例化、对象的内存大小、this指针）
本文介绍了C++中的类和对象，包括类的概念、定义格式、访问限定符、类域、对象的创建及内存大小、以及this指针。通过示例代码详细解释了类的定义、成员函数和成员变量的作用，以及如何使用访问限定符控制成员的访问权限。此外，还讨论了对象的内存分配规则和this指针的使用场景，帮助读者深入理解面向对象编程的核心概念。
ephemerals__
32 4
白子寰
|
1月前
|
存储 编译器 对象存储
【C++打怪之路Lv5】-- 类和对象（下）
【C++打怪之路Lv5】-- 类和对象（下）
白子寰
27 4