从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)(上)

简介: 从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)

1. AVL树的概念

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

       二叉搜索树虽然可以提高我们查找数据的效率,但如果插入二叉搜索树的数据是有序或接近有序的,此时二叉搜索树会退化为单支树,在单支树当中查找数据相当于在单链表当中查找数据,效率是很低下的。


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

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

树的左右子树都是AVL树。

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


       如果一棵二叉搜索树的高度是平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(logN),搜索时间复杂度也是O(logN)。注意: 这里所说的二叉搜索树的高度是平衡的是指,树中每个结点左右子树高度之差的绝对值不超过1,因为只有满二叉树才能做到每个结点左右子树高度之差均为0。

2. AVL树结点和树的定义

       下面来模拟实现一下AVL树,直接实现KV模型的AVL树,为了方便后续的操作,这里将AVL树中的结点定义为三叉链结构,并在每个结点当中引入平衡因子,(右子树高度-左子树高度)。

        除此之外,还需编写一个构造新结点的构造函数,由于新构造结点的左右子树均为空树,于是将新构造结点的平衡因子初始设置为0即可。(平衡因子并不是AVL树所必须的,这里只是其中一种实现方法)

AVLTree.h:

#pragma once
 
#include <iostream>
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; // 存的键值
  int _bf; // balance factor 平衡因子
 
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};
 
template <class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
 
protected:
  Node* _root = nullptr; // 给缺省值直接在初始化列表初始化
};

3. AVL树的插入(未包含旋转)

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

那么AVL树的插入过程可以分为两步:

① 按照二叉搜索树的方式插入新节点

与根结点比较如果比根大就往右子树插入,如果比根小就往左子树插入,

直到走到合适的位置就插入,由于这里是三叉链所以需要处理结点之间的关联关系

② 调整节点的平衡因子

当左右子树的高度发生了变化,那么就需要对父亲及祖先路径上的所有结点的平衡因子进行调整

插入结点后需要倒着往上更新平衡因子,更新规则如下:

1. 新增结点在parent的右边,parent的平衡因子+ +。

2. 新增结点在parent的左边,parent的平衡因子− −。

每更新完一个结点的平衡因子后,都需要进行以下判断:

如果parent的平衡因子等于0,表明无需继续往上更新平衡因子了。

如果parent的平衡因子等于-1或者1,表明还需要继续往上更新平衡因子。

如果parent的平衡因子等于-2或者2,表明此时以parent结点为根结点的子树已经不平衡了,

需要进行旋转处理。

  bool Insert(const 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 (cur == parent->_left)
      {
        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) // 不平衡了,需旋转
      {
        // 后面写
      }
      else // 理论不可能走到这,除非之前就错了
      {
        assert(false); // 报个错
      }
    }
    return true;
  }

4. AVL树的旋转

       若是在更新平衡因子的过程当中,出现了平衡因子为-2/2的结点,这时需要对以该结点为根结点的树进行旋转处理,而旋转处理分为四种,在进行分类之前我们首先需要进行以下分析:

当parent的平衡因子为-2/2时,cur的平衡因子必定是-1/1而不会是0。

理由如下:

       若cur的平衡因子是0,那么cur一定是新增结点,而不是上一次更新平衡因子时的parent,否则在上一次更新平衡因子时,会因为parent的平衡因子为0而停止继续往上更新。


       而cur是新增结点的话,其父结点的平衡因子更新后一定是-1/0/1,而不可能是-2/2,因为新增结点最终会插入到一个空树当中,在新增结点插入前,其父结点的状态有以下两种可能:


其父结点是一个左右子树均为空的叶子结点,其平衡因子是0,新增结点插入后其平衡因子更新为-1/1。

其父结点是一个左子树或右子树为空的结点,其平衡因子是-1/1,新增结点插入到其父结点的空子树当中,使得其父结点左右子树当中较矮的一棵子树增高了,新增结点后其平衡因子更新为0。

综上所述,当parent的平衡因子为-2/2时,cur的平衡因子必定是-1/1而不会是0。

根据此结论,我们可以将旋转处理分为以下四类:

  1. 当parent的平衡因子为-2,cur的平衡因子为-1时,进行右单旋。
  2. 当parent的平衡因子为-2,cur的平衡因子为1时,进行左右双旋。
  3. 当parent的平衡因子为2,cur的平衡因子为-1时,进行右左双旋。
  1. 当parent的平衡因子为2,cur的平衡因子为1时,进行左单旋。

       并且,在进行旋转处理后就无需继续往上更新平衡因子了,因为旋转后树的高度变为插入之前了,即树的高度没有发生变化,也就不会影响其父结点的平衡因子了。具体原因请看下面的旋转讲解。


4.1 右右_左单旋

可以看到,经过左单旋后,树的高度变为插入之前了,即树的高度没有发生变化,

所以左单旋后无需继续往上更新平衡因子。

左单旋的步骤如下:

  1. subR的左子树作为parent的右子树。
  2. 让parent作为subR的左子树。
  3. 让subR作为整个子树的根。
  4. 更新平衡因子。

左单旋后满足二叉搜索树的性质:

  1. subR的左子树当中结点的值本身就比parent的值大,因此可以作为parent的右子树。
  2. parent及其左子树当中结点的值本身就比subR的值小,因此可以作为subR的左子树。

左单旋代码:

  void RotateL(Node* parent)
  {
    Node* subR = parent->_right; // 动了三个标记了的结点,共更新六个指针,这更新两个指针
    Node* subRL = subR->_left;
 
    parent->_right = subRL;
    if (subRL) // subRL不为空才更新
    {
      subRL->_parent = parent;
    }
 
    Node* ppNode = parent->_parent; // 记录parent的parent,防止parent是一颗子树的头结点
 
    subR->_left = parent; // 再更新两个指针
    parent->_parent = subR;
 
    if (_root == parent)  // 最后更新两个指针
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else // parent是一颗子树的头结点
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subR;
      }
      else
      {
        ppNode->_right = subR;
      }
      subR->_parent = ppNode;
    }
 
    subR->_bf = parent->_bf = 0; // 更新平衡因子
  }

4.2 左左_右单旋

经过右单旋后,树的高度变为插入之前了,即树的高度没有发生变化,

所以右单旋后无需继续往上更新平衡因子。

右单旋的步骤如下:

  1. 让subL的右子树作为parent的左子树。
  2. 让parent作为subL的右子树。
  3. 让subL作为整个子树的根。
  4. 更新平衡因子。

右单旋后满足二叉搜索树的性质:

  1. subL的右子树当中结点的值本身就比parent的值小,因此可以作为parent的左子树。
  2. parent及其右子树当中结点的值本身就比subL的值大,因此可以作为subL的右子树。

右单旋代码:

  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
 
    parent->_left = subLR; // 更新两个节点
    if (subLR)
    {
      subLR->_parent = parent;
    }
 
    Node* ppNode = parent->_parent;
 
    subL->_right = parent; // 再更新两个节点
    parent->_parent = subL;
 
    if (_root == parent) // 最后更新两个结点
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      } 
 
      subL->_parent = ppNode;
    }
 
    subL->_bf = parent->_bf = 0; // 更新平衡因子
  }

4.3 左右双旋

左右双旋步骤示意图

1、插入新结点。这里可能插入到b / c下面,还可能h等于0,插入到60下面

(以上三种插入的后两步都是一样的,只是最后平衡因子不同:)

2、以30为旋转点进行左单旋。

3、以90为旋转点进行右单旋。

左右双旋的步骤如下:

  1. 以subL为旋转点进行左单旋。(前两步都可以复用上面的代码)
  2. 以parent为旋转点进行右单旋。
  3. 更新平衡因子。(左右双旋复杂的地方)

左右双旋后满足二叉搜索树的性质:

左右双旋后,实际上就是让subLR的左子树和右子树,分别作为subL和parent的右子树和左子树,再让subL和parent分别作为subLR的左右子树,最后让subLR作为整个子树的根(结合图理解)。


1. subLR的左子树当中的结点本身就比subL的值大,因此可以作为subL的右子树。


2. subLR的右子树当中的结点本身就比parent的值小,因此可以作为parent的左子树。


3. 经过步骤1/2后,subL及其子树当中结点的值都就比subLR的值小,而parent及其子树当中结点的值都就比subLR的值大,因此它们可以分别作为subLR的左右子树。

观察发现,左右双旋后,平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况:

1、当subLR原始平衡因子是-1时,左右双旋后subLR,parent、subL的平衡因子分别更新为0、1、0。



2、当subLR原始平衡因子是1时,左右双旋后subLR、parent、subL的平衡因子分别更新为0、0、-1。

3、当subLR原始平衡因子是0时,左右双旋后subLR、parent、subL的平衡因子分别更新为0、0、0。


       可以看到,经过左右双旋后,树的高度变为插入之前了,即树的高度没有发生变化,所以左右双旋后无需继续往上更新平衡因子。

从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)(下):https://developer.aliyun.com/article/1522271?spm=a2c6h.13148508.setting.21.50c04f0edmwqiI

目录
相关文章
|
4天前
|
C++
【C++】手撕AVL树(下)
【C++】手撕AVL树(下)
15 1
|
11天前
|
算法 测试技术 C++
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
13 2
|
12天前
|
C++ 开发者
C++一分钟之-概念(concepts):C++20的类型约束
【7月更文挑战第4天】C++20引入了Concepts,提升模板编程的类型约束和可读性。概念定义了模板参数需遵循的规则。常见问题包括过度约束、约束不完整和重载决议复杂性。避免问题的关键在于适度约束、全面覆盖约束条件和理解重载决议。示例展示了如何用Concepts限制模板函数接受的类型。概念将增强模板的安全性和灵活性,但需谨慎使用以防止错误。随着C++的发展,Concepts将成为必备工具。
32 2
|
4天前
|
Java C++ Python
【C++】手撕AVL树(上)
【C++】手撕AVL树(上)
12 0
|
10天前
|
C++ 开发者
C++一分钟之-概念(concepts):C++20的类型约束
【7月更文挑战第6天】C++20引入了Concepts,提升模板编程的精确性和可读性。概念允许设定模板参数的编译时约束。常见问题包括过度约束、不完整约束及重载决议复杂性。要避免这些问题,需适度约束、全面覆盖约束条件并理解重载决议。示例展示了如何定义和使用`Incrementable`概念约束函数模板。概念是C++模板编程的强大力量,但也需谨慎使用以优化效率和代码质量。
37 0
|
16天前
|
算法 程序员 编译器
C++一分钟之概念(concepts):C++20的类型约束
【6月更文挑战第30天】C++20的Concepts革新了模板编程,允许更清晰地表达类型要求,提升代码可读性和编译错误反馈。本文探讨Concepts基础、应用场景、易错点及避免策略,展示如何通过概念定义如Iterable、Addable,创建更健壮的泛型代码,强调了理解和利用编译器错误信息的重要性,以及概念与类型别名的区别。Concepts现已成为现代C++程序员的关键技能。
17 0
|
4天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
24 10
|
9天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
40 9
|
4天前
|
存储 编译器 C语言
【C++基础 】类和对象(上)
【C++基础 】类和对象(上)
|
13天前
|
编译器 C++
【C++】string类的使用④(字符串操作String operations )
这篇博客探讨了C++ STL中`std::string`的几个关键操作,如`c_str()`和`data()`,它们分别返回指向字符串的const char*指针,前者保证以&#39;\0&#39;结尾,后者不保证。`get_allocator()`返回内存分配器,通常不直接使用。`copy()`函数用于将字符串部分复制到字符数组,不添加&#39;\0&#39;。`find()`和`rfind()`用于向前和向后搜索子串或字符。`npos`是string类中的一个常量,表示找不到匹配项时的返回值。博客通过实例展示了这些函数的用法。