【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)

简介: 【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)

前面我们对 map / multimap / set / multiset 进行了简单的介绍,可以发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的。

但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成 O(N),因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理,即采用 平衡树 来实现。

一、AVL树(高度平衡二叉搜索树)

1、概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下

  • 最优情况下,有 n 个结点的二叉搜索树为完全二叉树,查找效率为:O(log₂N)。
  • 最差情况下,有 n 个结点的二叉搜索树退化为单支树,查找效率为:O(N)。

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

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

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

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

为什么左右子树高度差不规定成0呢?

因为在 2、4 等节点数的情况下,不可能做到左右高度相等的情况。


2、AVL 树节点的定义

AVL 树节点的定义:

AVL 树节点是一个 三叉链结构,除了 指向左右孩子的指针,还有一个 指向其父亲的指针,数据域是键值对,即 pair 对象,还引入了平衡因子,用来判断是否需要进行平衡操作。

// AVL树节点的定义(KV模型)
template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode<T>* _left;   // 该节点的左孩子
    AVLTreeNode<T>* _right;  // 该节点的右孩子
    AVLTreeNode<T>* _parent; // 该节点的双亲指针
 
    pair<K, V> _kv;          // 键值对
    int _bf;                 // 该节点的平衡因子(balance factor) = 右子树高度-左子树高度
 
    // 构造函数
    AVLTreeNode(const pari<K, V>& kv)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _bf(0)
    {}
};
 
// AVL树的定义(KV模型)
template<class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
  // 成员函数
 
private:
  Node* _root;
}

3、AVL树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子,因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步:

  1. 按照二叉搜索树的方式插入新节点到 AVL 树中。
  2. 新节点插入后,AVL 树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否破坏了 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) // while循环结束,说明找到适合插入节点的空位置了
    {
        if(kv.first > cur->_kv.first) // 插入节点键值k大于当前节点
        {
            parent = cur;
            cur = cur->_right;
        }
        else if(kv.first < cur->_kv.first) // 插入节点键值k小于当前节点
        { 
            parent = cur;
            cur = cur->_left;
        }
        else // 插入节点键值k等于当前节点
        {
            return false;
        }
    }
    
    // 插入新节点
    cur = new Node(kv); // 申请新节点
    // 判断当前节点是父亲的左孩子还是右孩子
    if (cur->_kv.first > parent->_kv.first)
    {
        parent->_right = cur;     
 
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;
 
    // 控制平衡
  // 1、更新平衡因子
    
    // ...
 
    return true;
}

⚪更新平衡因子

(1)插入新节点cur 插入后,parent 的平衡因子一定需要调整,在插入之前,parent 的平衡因子分为三种情况:-1,0,1,分以下两种情况:
  • 如果 cur 插入到 新节点父亲parent) 的左侧,只需给 父亲(parent) 的平衡因子--_bf--即可。
  • 如果 cur 插入到 新节点父亲parent) 的右侧,只需给 父亲(parent) 的平衡因子++(_bf++即可。

(2)新节点父亲的平衡因子更新以后,又会分为 3 种情况:

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

  1. 如果更新以后,parent 的平衡因子是 0(则说明插入之前 parent 的平衡因子之前一定为 1/-1),说明父亲所在子树高度没变(因为把矮的那边给填补上了),此时满足 AVL 树的性质,插入成功,不需要继续往上更新
  2. 如果更新以后,parent 的平衡因子是 1/-1(则说明插入之前 parent 的平衡因子 一定为 0),说明父亲所在子树高度增加,需要继续往上更新。(最坏情况:往上一直更新到根节点)。
  3. 如果更新以后,parent 的平衡因子是 2/-2,说明父亲所在子树出现了不平衡,需要对其进行旋转处理
// 插入节点
bool Insert(const pair<K, V>& kv)
{
    // 控制平衡
  // 1、更新平衡因子
    
    while (parent) // 最坏情况:更新到根节点
    {
        // 更新双亲的平衡因子
        if (cur == parent->_left) // 新节点插入在父亲的左边
            parent->_bf--;
        else // 新节点插入在父亲的右边
            parent->_bf++;
 
        // 更新后检测双亲的平衡因子
        if (0 == pParent->_bf)
        {    
            break;
        }
 
        //else if (1 == parent->_bf || -1 == parent->_bf)
        else if (abs(parent->_bf) == 1) // 插入前双亲的平衡因子是0,插入后双亲的平衡因为为1 或者 -1 ,说明以双亲为根的二叉树的高度增加了一层,因此需要继续向上调整
        {
            cur = parent;
            parent = cur->_parent;
        }
 
        else if (abs(parent->_bf) == 2) // 双亲的平衡因子为正负2,违反了AVL树的平衡性,需要对以parent为根的树进行旋转处理
        {
            // 1、父节点的右边高,左边低,需要往左旋
            if (parent->_bf == 2 && cur->_bf == 1) 
        {
        RotateL(parent); // 左单旋
      }
 
            // 2、父节点的左边高,右边低,需要往右旋
      else if ((parent->_bf == -2 && cur->_bf == -1))
      {
        RotateR(parent); // 右单旋
      }
            
            // 3、父节点的左边高,且父节点左孩子的右边高
      else if (parent->_bf == -2 && cur->_bf == 1) 
      {
        RotateLR(parent); // 左右双旋
      }
 
            // 4、父节点的右边高,且父节点右孩子的左边高
            else if (parent->_bf == 2 && cur->_bf == -1)
      {
        RotateRL(parent); // 右左双旋
      }
 
      break; // 旋转完成,树已平衡,退出循环
        }
 
        // 除了上述3种情况,平衡因子不可能有其它的值,报错处理
        else
        {
            assert(false);
        }
    }
    return true;
}

4、AVL树的旋转

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

根据节点插入位置的不同,AVL 树的旋转分为四种:

旋转的本质:在遵循二叉搜索树的规则下,让左右均衡,降低整棵树的高度。

该进行哪种旋转操作?

引发旋转的路径是直线就是单旋,如果是折线就是双旋

注意:此处看到的树,可能是一颗完整的树,也可能是一颗子树。


(1)新节点插入较高左子树的左侧 —— 左左:右单旋

将新的节点插入到了 parent 左孩子的左子树上,导致的不平衡的情况。

上图在插入前,AVL 树是平衡的,新节点插入到 30 的左子树(注意:此处不是左孩子)中,30 左子树增加了一层,导致以 60 为根的二叉树不平衡,要让 60 平衡,只能将 60 左子树的高度减少一层,右子树增加一层,即将左子树往上提,这样 60 转下来,因为 60 比 30 大,只能将其放在 30 的右子树,而如果 30 有右子树,右子树根的值一定大于 30,小于 60,只能将其放在 60 的左子树,旋转完成后,更新节点的平衡因子即可。


【引发右单旋的条件】

  • 父亲左边高,右边低,所以要让父亲往右旋
  • parent 的平衡因子为 -2,parent 左孩子平衡因子为 -1,观察发现,平衡因子都是负数,说明是左边高,也说明了引发旋转的路径是一条直线,所以我们要右旋操作。

【右单旋操作】

1、让 subL 的右子树 subLR 成为 parent 的左子树(因为 subLR 的右子树根节点值 > 30,< 60)。
2、让 parent 成为 subL 的右子树(因为 60 > 30)。
3、让 subL 变成这个子树的根。

这一步操作前需要先判断下:parent 是根节点,还是一个普通子树

  • 如果是根节点,旋转完成后,则更新 subL 为新的根节点。
  • 如果是普通子树(可能是某个节点的左子树,也可能是右子树,这里作一个判断),然后更新 subL 为这个子树的根节点。

4、根据树的结构,更新 parent 和 subL 的平衡因子为 0。


在旋转过程中,更新双亲指针的指向,有以下几种情况需要考虑:

  • 30 节点的右孩子可能存在,也可能不存在。(subL 的右子树 subLR 可能存在,也可能为空。当不为空时才更新 subL 右子树 subLR 的双亲指针指向)。
  • 60 可能是根节点,也可能是子树。(旋转完成后,subL 的双亲节点,可能是空,也可能是 parent 原先的父节点。所以在更新 subL 的双亲指针前需要判断下)。

依次调整 subLR、parent、subL 的位置和双亲指针的指向。

// 右单旋
void _RotateR(Node* parent)
{  
    Node* subL = parent->_left; // subL : parent的左孩子
  Node* subLR = subL->_right; // subLR : parent左孩子的右孩子
 
    // 旋转完成之后,让subL的右子树subLR成为parent的左子树
    parent->_left = subLR;
    // 如果subLR存在,更新subLR的双亲指针,指向parent
    if (subLR)
  {
    subLR->_parent = parent;
  }
    
    // 因为parent可能是棵子树,因此在更新其双亲前必须先保存parent的父节点
    Node* ppNode = parent->_parent;
    
    // 让parent成为subL的右子树
    subL->_right = parent;
    // 更新parent的双亲指针,指向subL
    parent->_parent = subL;
 
    // 如果parent是根节点,根新指向根节点的指针
    if (_root == parent)
  {
    _root = subL;            // 更新subL为新的根
    subL->_parent = nullptr; // 更新subL的双亲指针,指向空
  }
    // parent不是根节点,就是一个普通子树
    else
    {
        // 判断parent原先是左孩子还是右孩子
        if (ppNode->_left == parent)
    {
      ppNode->_left = subL; // parent原先的双亲节点接管subL,subL为这个子树的根
    }
    else
    {
      ppNode->_right = subL;
    }
        subL->_parent = ppNode; // 更新subL的双亲指针
    }
 
    // 根据调整后的结构更新部分节点的平衡因子
    parent->_bf = pSubL->_bf = 0;
}

【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)https://developer.aliyun.com/article/1515239?spm=a2c6h.13148508.setting.28.11104f0e63xoTy

相关文章
|
8天前
|
存储 安全 Java
Java集合详解:Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素,如ArrayList(适合读取)和LinkedList(适合插入删除)。Set不允许重复,有HashSet(无序)和TreeSet(排序)。Map存储键值对,HashMap(无序)和TreeMap(排序)。Vector是线程安全的ArrayList替代品,但在多线程环境下使用。选择集合类型应根据应用场景,如有序、无序、键值对需求及线程安全考虑。
|
11天前
|
存储 安全 Java
Java 集合(List、Set、Map 等)相关问答归纳再整理
HashMap 中使用键对象来计算 hashcode 值 HashSet 使用成员对象来计算 hashcode 值,对于两个对象来说hashcode 可能相同,所以 equals() 方法用来判断对象的相等性,如果两个对象不同的话,那么返回 false。 HashMap 比较快,因为是使用唯一的键来获取对象,HashSet 较 HashMap 来说比较慢。 4.1.3 HashMap 与 TreeMap
9 2
|
12天前
|
存储 人工智能 C++
map容器在C++中的具体用法以及相关注意点
map容器在C++中的具体用法以及相关注意点
15 1
|
12天前
|
算法 C++
C++中的结构应用:Josephus问题
C++中的结构应用:Josephus问题
10 1
|
12天前
|
存储 测试技术 C++
C++中的结构
C++中的结构
9 2
|
20天前
|
存储 安全 Java
Java list set map等接口及其实现类
Java list set map等接口及其实现类
|
21天前
|
存储 C语言
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(下)
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)
19 1
|
21天前
|
编译器 C语言 C++
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(中)
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)
20 2
|
21天前
|
存储 C语言 C++
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(上)
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)
22 3
|
21天前
|
C语言
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(下)
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现
24 3