【C++】set和map的底层AVL树的实现(上)

简介: 【C++】set和map的底层AVL树的实现(上)

前言



上一篇文章对 map/multimap/set/multiset 进行了简单的介绍,在其文档介绍中发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的 ,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成 O(N) ,因此map 、 set 等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现。


AVL树的概念:


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


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

它的左右子树都是 AVL 树左右子树高度之差 ( 简称平衡因子 ) 的绝对值不超过 1(-1/0/1)如果一棵二叉搜索树是高度平衡的,它就是 AVL 树。如果它有 n 个结点,其高度可保持在O(logN),搜索时间复杂度O(logN).


一、AVL树的实现



首先我们直接实现KV结构的AVL树,因为如果KV结构的树都会了那么在写K的就很简单了,只需要在KV结构上修改一些值即可。


要注意:AVL数相比原先的二叉搜索树多了一个平衡因子,只有平衡因子的绝对值不超过1或者小于-1才是AVL树,如下图所示:


983a4ae9a3f24947a93e84dc3662fb7a.png


这里默认是新增节点在右树平衡因子就+1,新增节点在左树平衡因子就-1,这里为什么让AVL树的高度差不超过1呢,因为没有办法让一颗二叉搜索树完全平衡。注意:AVL树不一定有平衡因子,使用平衡因子只是一种实现方式。


下面我们先创建树的节点:


为了避免冲突,我们将我们写的树放在命名空间中:


template<class K,class V>
  struct AVLTreeNode
  {
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  pair<K, V> _kv;
  int _bf;   
  AVLTreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {
  }
  };

首先我们相比二叉平衡树不一样的地方在于我们需要加入一个parent指针,这个指针用来记录每个节点的父节点,因为后期调整平衡因子需要从新增节点往上查找。然后就是我们在map中见到的键值对pair了,同时还有一个变量是平衡因子。然后我们给树的节点写一个构造函数,在构造函数中我们的参数为pair,然后在初始化列表中将left,right,parent指针初始化为nullptr,然后将节点中的键值对用参数初始化,并且每个新节点的平衡因子都是0.


下面我们实现AVL树的主体:


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

我们将AVL树的节点typedef一下,这样在后面的使用会更方便,然后树中有一个根节点,我们给一个缺省参数让根节点为空,下面我们就实现AVL树的插入,插入的前面和二叉搜索树一样,下面的代码我先放出来:


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.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)
    {
    if (parent->_left == cur)
    {
      parent->_bf--;
    }
    else if (parent->_right == cur)
    {
      parent->_bf++;
    }
    if (parent->_bf == 0)
    {
      //已经平衡了
      break;
    }
    else if (parent->_bf == 1 || parent->_bf == -1)
    {
      //需要继续向上调节
      parent = parent->_parent;
      cur = cur->_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;
  }

上面是AVL树的插入实现,下面我们一点一点代码慢慢讲解:


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.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;
    }


首先和我们实现二叉搜索树一样,先判断根节点是否为空,如果根节点为空则需要直接将新增的节点给根节点,然后返回true即可。接下来需要一个用于遍历的节点cur和parent节点,因为我们在遍历的时候最后cur会变成空指针,这个时候cur已经失效了即使让cur开一个新节点也没法链接到cur的父节点,所以我们需要一个parent节点来记录遍历的那个节点的父节点。接下来就是二叉搜索树的正常步骤,如果要插入的元素比当前节点的元素大就去当前节点的右子树寻找,如果要插入的元素比当前节点的元素小就去当前节点的左子树找,如果碰到相同元素我们就返回false,当出循环后我们让cur指向新节点,并且判断要插入的节点是在父节点的左边还是右边,以上都是二叉搜索树的内容,下面我们进入AVL树的内容:


while (parent)
    {
    if (parent->_left == cur)
    {
      parent->_bf--;
    }
    else if (parent->_right == cur)
    {
      parent->_bf++;
    }
    if (parent->_bf == 0)
    {
      //已经平衡了
      break;
    }
    else if (parent->_bf == 1 || parent->_bf == -1)
    {
      //需要继续向上调节
      parent = parent->_parent;
      cur = cur->_parent;
    }

首先我们控制平衡因子必须以parent节点作为循环条件,因为在从新增节点到节点的祖先的遍历中parent节点最先有可能变成nullptr(走到根节点就变成了nullptr).下面我们用图进行讲解:


96afacef06a74fa0b5cd693871e0fa48.png5ca331f3d5804ba2962c03b44ca2b444.png


由于新增节点的位置不同所以平衡因子的改变也不同,就比如上图中有的节点平衡因子变成了2已经不平衡了,有的平衡因子变成了0变的平衡了,那么如何改变平衡因子呢,下面我们给出结果:


1.如果我们新增的节点是父节点的左子树,那么父节点的平衡因子就-1,如果我们新增的节点是父节点的右子树,那么父节点的平衡因子就+1.


2.如果我们的父节点的平衡因子由于新增节点变成0了,这就说明原先这个父节点是不平衡的,新增节点后变的平衡了这个时候满足AVL树的要求。如第二种图。


3.如果我们的父节点的平衡因子由于新增节点变成1或者-1了,这就说明原先这个父节点是0也就是平衡的,经过新增节点后才变的不平衡,但是这个时候的父节点高度差没有超过1所以当前这个父节点不需要管了,我们要去这个父节点的父节点查看平衡因子是否满足要求,只有当某个祖先的平衡因子变成2或者-2这个时候就需要通过旋转使这棵树更加的平衡。就如第一张图一样,新增节点插入后9的平衡因子满足要求,但是8的平衡因子不满足要求了所以需要调整。


知道了以上三点大家应该就可以看懂代码了,当新增节点为父节点的左边我们就让父节点的平衡因子-1,当新增节点为父节点的右边我们就让父节点的平衡因子+1.修改为当前平衡因子后我们需要考虑向上更新平衡因子,当新增后父节点的平衡因子为0时我们就不需要调整了直接退出循环即可,当新增后父节点的平衡因子为1或者-1时,我们就需要往上继续更新平衡因子,继续看下面的代码:


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);
    }


当新增后平衡因子为2或者为-2时,我们就需要旋转控制了,下面我们讲解四种旋转的方式:


第一种:当新增节点后这棵树的纯粹的右边的高度高于左边的高度时,需要左单旋(就是将右边高的节点旋转到左边):


3cf60ead7728470dad1baa4f406f278d.png


如上图所示,首先我们要明白左单旋的意义,左单旋就是为了降低高度并且让树变的平衡,比如上图中把30这个根节点放到60的左边就会降低一层的高度,那么为了将30变成60的子树必须让30及30的所有子树都小于60才可以,所有选择让60的左树去当30的右树(因为60的左树一定是小于60大于30的,为了放入60的左树正好满足小于60的要求),然后再将修改后的30这棵树放到60的左边。理解了如何单旋后我们看当上图中h等于0时新增1节点在哪个位置一定会引发旋转,并且旋转后一定能降低高度,经过画图得知只有新增节点在C的位置才一定会引发旋转并且旋转一定可以降低高度,这也验证了我们上面所说的只有纯粹的右边高度高时才需要左单旋,当h==0,新增节点在60的左边这个时候60的平衡因子为-1说明60的左边高度高,所以不满足我们的要求旋转后也没有降低高度。当h==0新增节点在60的右边这个时候60的平衡因子为1,30的平衡因子为2满足我们的要求,旋转后也成功降低了高度。


下面我们看看当h==1的情况:


4164d3912a8b490d91161bb6bd28e268.png


当h==1时我们同样在C的位置插入,不管插入到C的左子树还是右子树,根节点的平衡因子都为2并且根节点的右子树的平衡因子都为1,所以在C的位置插入节点都会引发旋转。


下面我们看h==2的情况:

a460c76404154f929926570696316903.png



下面是在C的任意位置插入都会引发旋转的图:

a72f558d304f453dbab66e62dac6c4b8.png

我们可以看到不管在C的哪个位置插入,最终根节点的平衡因子都是2,根节点右边的平衡因子都是1,有了上面的图相信大家知道了左单旋以及左单旋的条件,只有当父节点的平衡因子为2并且cur的平衡因子为1才会左单旋,因为这样的数是纯粹的右边高度高。下面是左单旋的代码:


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

要看上面的代码我们单独画一张左单旋的图为例:


54eaefd7ea9546a28c1c08af8b2347b0.png


以上图为例,我们需要保存父节点的右边节点以及父节点右边节点的左边节点,我们将父节点的右边节点记录为subR,将fsubR的左边节点记录为subRL,然后我们还需要保存父节点的父节点,因为有可能我们旋转的不是一整颗树,而是一棵树的一个子树,我们先让父节点的右边连接上subRL,因为有可能subRL这个节点是空,所以我们需要先判断subRL不为空然后让subRL的父节点连接到parent上,然后再将subR的左边连接parent,同样将parent的父节点连接到subR,这里就体现了我们提前保存父节点的父节点的好处(因为parent的父节点变了)。这个时候我们就该判断ppnode是否为空了,如果ppnode为空就说明subR就是根节点了,如果不为空说明我们旋转的只是一颗子树,我们需要判断ppnode的哪边链接着以前的父节点,然后将subR正确链接,同时在最后我们还需要将subR链接到ppnode上,这样就完成了旋转,因为旋转后parent和subR的平衡因子都变成0了,所以我们记得将这两个的平衡因子改为0.


下面是右单旋的图,右单旋大体与左单旋一模一样,只不过右单旋是纯粹的左边高度高才会右单旋,并且右单旋的条件为parent的平衡因子为-2,cur的平衡因子为-1:


d14d3e161b7943b1914a1dcdb7732e93.png


右单旋一定是在b的位置插入才会一定引发旋转,下面看代码:


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


从代码可以看到右单旋与左单旋的思路一模一样,只不过旋转需要移动的节点变了而已,大家对照着图和代码完全可以看明白(当然是已经看懂左单旋的前提下)


下面我们分析双旋的情况:


ecb86c63274d47e48a6e5a93ee2ae5da.png


首先触发双旋的条件一定是上图中60这个节点的变化,当h==0时说明60这个节点就是新增节点,这个时候一个单旋已经搞不定了,必须先将parent的左节点左单旋,再将整个parent右旋,并且当h==0的时候新增节点的平衡因子默认为0,这个时候parent,subL,subLR的平衡因子都为0.



目录
相关文章
|
28天前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
2月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
35 6
【数据结构】map&set详解
|
1月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
31 1
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
35 5
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
|
2月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
|
3月前
|
存储 安全 Java
java集合框架复习----(4)Map、List、set
这篇文章是Java集合框架的复习总结,重点介绍了Map集合的特点和HashMap的使用,以及Collections工具类的使用示例,同时回顾了List、Set和Map集合的概念和特点,以及Collection工具类的作用。
java集合框架复习----(4)Map、List、set
|
2月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树:它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
25 2
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。
|
3月前
|
存储 Java 索引

热门文章

最新文章