『 C++ 』AVL树详解 ( 万字 )

🦈STL容器类型

请添加图片描述

在STL的容器中,分为几种容器:

  1. 序列式容器(Sequence Containers):
    • 这些容器以线性顺序存储元素,保留了元素的插入顺序。
    • 支持随机访问,因此可以使用索引或迭代器快速访问任何位置的元素。
    • 主要的序列式容器包括vector、list、deque、array和forward_list。
  2. 关联式容器(Associative Containers):
    • 这些容器不保留元素的插入顺序,而是根据元素的键进行排序和组织。
    • 元素以键值对的形式存储,键通常用于快速查找元素。
    • 主要的关联式容器包括set、multiset、map和multimap。
  3. 无序关联容器(Unordered Associative Containers):
    • 这些容器也是键值对容器,但与关联式容器不同,它们不维护元素的排序顺序。
    • 使用哈希表(hash table)来组织元素,以便快速查找。
    • 主要的无序关联容器包括unordered_set、unordered_multiset、unordered_map和unordered_multimap。
  4. 容器适配器(Container Adapters):
    • 容器适配器是一种特殊类型的容器,它们提供了一种不同于传统容器的接口,通常用于特定的数据结构需求。
    • stack是一个适配器,提供了栈(后进先出)的操作。
    • queue是一个适配器,提供了队列(先进先出)的操作。
    • priority_queue是一个适配器,提供了优先队列的操作,通常用于实现优先级队列。

🦈键值对

请添加图片描述

键值对,顾名思义其用来表示具有一一对应的关系的一种结构,该结构中一般只包含两个成员变量,即KeyValue;

在STL中存在一种这样的容器template <class T1, class T2> struct pair;;

这个容器是一个类模板,其源码中的底层构造大致为:

template <class T1, class T2>
struct pair {typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()) {}pair(const T1& a, const T2& b) : first(a), second(b) {}
};

可以看到模板参数共有两个分别为T1与T2;

其成员变量只有两个分别为firstsecond从而能够使该容器具有keyvalue一对一的关系;


🦈AVL树概念

请添加图片描述

AVL树(Adelson-Velsky and Landis Tree)它是一种自平衡的二叉搜索树,由苏联的数学家Georgy Adelson-Velsky和Evgenii Landis于1962年首次提出;

AVL树又被称为高度平衡搜索二叉树,它是基于搜索二叉树的基础上的高度平衡搜索二叉树,其性质主要为:

  • 它可能是一棵空树(空树可以被看作是一棵AVL树)
  • 若该树的左子树不为空,则左子树的所有节点的值都小于根节点的值;若该树的右子树不为空时,该右子树的所有节点都大于根节点的值(搜索二叉树的条件);
  • 其左子树与右子树的高度差不超过1;
  • AVL树的左右子树也一样为AVL树,意思是每棵’AVL树中的所有子树都应该符合该条件;

AVL树示例图

以该图为例,该图即为一棵AVL树,其每个节点的左右子树高度差都不超过1;

那么在AVL树的结构中就有几个需要注意的点:

  • 如何判断左右子树高度差?
  • 如何在插入过程中判断AVL树在插入之后其树的结构是否符合AVL树的规则?
  • 当AVL树出现不平衡的状态应该如何调整致使树从不平衡变回AVL树?

🦈AVL树的节点结构

请添加图片描述

在实现容器或数据结构的过程中可以尽量的使用模板来保证其泛型;对于一棵简单的AVL实现可以根据需要(key模型 或 是key,value模型)来确定实现该数据结构的模板参数个数;

而该篇文章的AVL树实现将针对后者,即key,value模型来进行实现;

AVL树中的节点一般为三叉链结构,即节点内存在三个指针来控制指向,分别为:

  • _left节点,指向节点的左子树;
  • _right节点,指向节点的右子树;
  • _parent节点,指向节点的父亲节点;

设定义一个变量使用pair<T1,T2>容器来存放插入的数据,其中pair<T1,T2>中的T1对应着key,value模型中的key,T2对应着模型中的value数据;

同时可以设置一个平衡因子变量,以平衡因子的变化来判断该树是否要进行调整,当该树不平衡时则使用某种方式将该树调整回平衡状态,使其结构恢复为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树的定义与平衡搜索二叉树的结构上呈现类似;

template<class K,class V>
class AVLTree{typedef AVLTreeNode<K,V> Node;//将节点进行typedef
public:bool Insert(const K& key);
protected:
private:Node *_root = nullptr;//节点指针
};

该篇文章中重点实现AVL树中的插入操作;


🦈AVL树的插入操作

请添加图片描述

AVL树的插入操作与搜索二叉树的插入操作类似,唯独不同的是AVL树在进行插入操作时需要对树的结构进行判断,即判断插入过后该树是否还符合AVL树的规则(节点的左右子树高度差不超过1);

当树的结构规则被破坏时则需要采用一些特定的方式对树的结构进行调整;


🐡节点插入逻辑

请添加图片描述

新节点所插入的位置必是为空节点nullprtr,判断所插入数据pair<K,V>中的key值是否大于当前节点;

  • 大于当前节点

    当所插入数据的key值大于当前节点数据说明需要插入在该节点的右子树区域;

  • 小于当前节点

    当所插入数据的key值小于当前节点数据说明需要插入在该节点的左子树区域;

  • 等于当前节点

    当所插入数据的key值等于当前节点中的数据时,根据搜索二叉树的定义即数据的唯一性,该数据的值已经存在于该树中,该新节点不予插入,返回false;

bool Insert(const std::pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node *parent = nullptr;Node *cur = _root;//while (cur){/*当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{//cur->_kv.first == kv.firstreturn false;}}/*与所插入的叶子节点进行链接*/cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;/*更新平衡因子...判断树的结构规则是否符合AVL树的规则1.符合 不影响下一个节点的插入2.不符合 使用旋转的方式对树进行调整*/return true;}//Insert函数反括号

🐡判断树是否符合AVL树的规则

请添加图片描述

判断树是否符合AVL树的规则有两种:

  • 创建子函数

    每当插入一个数据时调用子函数来判断树的整体结构是否符合节点的左右子树高度差不超过1;

  • 使用平衡因子

    使用平衡因子的方式即将AVL树节点的结构中加入一个变量来判断节点的平衡因子;

    当平衡因子为0时表示该节点左右子树高度差为0;

    当平衡因子为1-1时表示该节点的左右子树高度差为1;

    当平衡因子为2-2时表示该节点的左右子树高度差为2,已经不平衡,需要进行特定操作使其恢复AVL树的平衡状态;

在本文中所使用的方式为方式二,即采用平衡因子的方式来对树的节点进行判断;

在上文中提到了对与新节点的插入;

若是搜索二叉树对新节点进行插入时则不需要再对树的结构进行判断,但是在AVL树中则要对AVL树的结构进行判断;

当然再判断树的平衡因子前首先应该在插入节点之后对各个节点的平衡因子进行更新;

对于平衡因子的更新有三种情况:

  • 新插入节点的平衡因子

    新插入节点的平衡因子必定为0,因为其左右子树都为空节点nullptr;

  • 新节点在节点的左子树中

    当新节点在节点(新节点的祖先节点)的左子树中时,节点(新节点的祖先节点)的平衡因子需要进行--;

  • 新节点在节点的右子树中

    当新节点在节点(新节点的祖先节点)的右子树中时,节点(新节点的祖先节点)的平衡因子需要进行++;

一般平衡因子的更新与平衡因子的检查(树结构的检查)是同一时间的,检查的情况也会出现四种情况:

  • 平衡因子更新后为0

    当平衡因子在更新过后为0时则表示这次的插入对树(子树)的平衡状态反而起到了使其平衡的作用;

    在该次判断后可以直接跳出循环结束插入;

  • 平衡因子更新后为1

    当平衡因子更新过后为1时表示这次的插入对树(子树)的平衡状态从完全平衡(左右高度差为0)变成了高度平衡(左右高度差为1),这个变化可能影响到了这个节点的其他的祖先节点,所以应该继续往上进行更新,判断其它的祖先节点是否被影响成非高度平衡状态(左右子树高度差为2);

  • 平衡因子更新后为2

    当平衡因子更新过为2时表示可以不用再继续向上遍历判断,因为该树(子树)已经不平衡,需要对该树(子树)进行处理;

    当处理结束之后可直接跳出循环结束插入操作;

  • 平衡因子完全错乱

    这种情况是避免平衡因子完全错乱;

    当上面的三个条件都不满足时则表示平衡因子很可能已经混乱,整棵树的结构获取都变得不平衡,需要直接退出程序并对程序进行检查;

 while (parent){if (cur == parent->_left){//新节点为其parent->_bf--;}else // if (cur == parent->_right){parent->_bf++;}/*判断树的结构是否符合AVL树的规则*/if (parent->_bf == 0){// 更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){/* 继续往上更新可能影响到了该节点的其他祖先节点应继续向上更新并对其祖先节点进行判断其子树是否存在不平衡的状态;    */cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){/*子树不平衡需要进行旋转操作对树进行调整*/break;}else{/*平衡因子出现问题,对程序断死防止错误插入导致的更大问题*/assert(false);}

🐡旋转操作

请添加图片描述

AVL树中当其平衡因子的绝对值等于2时表示该节点左右子树的高度差为2,这时候表示这棵AVL树已经不平衡,需要对其进行调整;

那么当AVL树不平衡时如何对树进行操作?

  • 采用旋转操作将树的结构进行调整使其变回高度平衡搜索二叉树(AVL树);

对于旋转操作中分为四种操作:

  • 左单旋操作

    以树(子树)中的某个指定节点作为轴点,对这棵树进行左单旋操作;

  • 右单旋操作

    以树(子树)中的某个指定节点作为轴点,对这棵树进行右单旋操作;

  • 左右双旋操作

    以树(子树)中的某个指定节点作为轴点,对这棵树进行左单旋操作;

    再以该树(子树)中的另一个指定节点作为轴点,对这棵树进右单旋操作;

  • 右左双旋操作

    以树(子树)中的某个指定节点作为轴点,对这棵树进行左单旋操作;

    再以该树(子树)中的另一个指定节点作为轴点,对这棵树进右单旋操作;

当一棵树(子树)中节点的平衡因子的绝对值为2时将会出现几种情况:

该图分别对应着几种需要进行旋转操作的情况;

那么如何理解几种旋转操作?

  • 将以抽象图与实际图结合解释;

🦭右单旋操作

请添加图片描述

从上文可知,右单旋操作即为以树(子树)中的某个指定节点作为轴点,对这棵树进行右单旋操作;

该图为需要进行右单旋操作树(子树)的抽象图;

当子树a的高度由h变为h+1时由于60节点的左子树高于右子树,其平衡因子由-1变为-2;

a子树的高度变化影响到了其祖先节点;

具象图及变化操作:

  • h0

    h高度为0时,其红色节点即为新增节点,在该处节点新增时将会触发右单旋操作的情况;

    只需将cur节点所指向的右子树节点变成parent节点的左子树;

    parent节点变为cur节点的右子树;

    在该操作之后在h高度为0的情况下三个节点的平衡因子都将转化为0,使树的结构恢复为AVL树的结构;

  • h1

    h高度为1时,两个红色节点的任意一个节点为新增节点时都将触发右单旋操作的情况;

    再该中情况中,只需要将cur节点的右子树curright节点变为parent节点的左子树,再将parent节点变为cur节点的右子树即可;

    再该操作之后在h高度为1的情况下parent节点与cur的平衡因子将变为0;

  • h2

    相较上面两种场景当中,当h2时其的情况将会变得更多;

    以最单纯的抽象图为例:

    h2时,a子树的情况必定为情况①(只有当a子树为情况①时对a处进行新增节点才会触发右单旋操作);

    b子树与c子树的情况为①②③情况的其中一种;

    以该图为例,其旋转操作不再进行赘述;


  • 代码片段

    void RotateR(Node *parent){ //左高右旋Node *cur = parent->_left;Node *curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node *ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){/*该树若是不为子树其cur节点将更新为根节点*/_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}
    

🦭左单旋操作

请添加图片描述

左单旋与右单旋的操作相反,其几种情况与右单旋的几种情况相同,只不过节点(子树)位置不同;

此处只对左单旋情况中的抽象图进行解析;

该图为例,该图即为需要对左单旋进行操作的情况;

当右子树高度高于左子树且平衡因子等于2时则需要对子树进行旋转操作;

旋转结束之后其cur节点与parent节点的平衡因子将恢复为0;

其结构整体恢复为AVL树的结构状态;

  • 代码片段

    void RotateL(Node* parent){//右高左旋Node *cur = parent->_right;Node *curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node *ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}

🦭左右双旋操作

请添加图片描述

左右双旋操作,顾名思义在这种情况种需要用到两种单旋的方式使树的结构恢复为以往的AVL树的状态;

  • 抽象图

    该图即为左右双旋操作的抽象图;

    当这种情况时b子树或者c子树的高度由h转变为h+1时都将破坏该AVL树的结构;

    当出现这种情况时即需要使用双旋操作来完成对树结构的恢复;

  • 为什么当这种情况不能使用单旋操作对树的结构进行恢复?

    以该抽象图为例,该抽象图中的c子树的高度由h-1变为了h;

    对应的左子树的高度高于右子树,若是用单旋的话需要进行一个右单旋操作;

    而再该种情况下若是使用右单旋操作,最终的结果还是一个不平衡的状态;

    故在这种情况中不能使用单旋操作来解决AVL树中的不平衡状态;

根据上文所提,在该种情况中只能使用两种单旋操作的方式组合成双旋操作使得最终使得树的结构恢复为平衡状态;

该图即为左右双旋操作的大致操作流程;

从上面的抽象图中也可以衍生几个例子以加深对双旋操作的理解;

  • 当树的高度h0

    当红色节点为新增节点时需要触发左右双旋操作;


  • 当树的高度h1

    当红色节点或绿色节点为新增节点时需要触发左右双旋操作;

    该处旋转演示为绿色节点;


  • 当树的高度h2

    当树的高度h2时,将会有多种情况;

    其中a子树与d子树分别为①②③中的任意一种;

    下图为树的高度h2时的其中一种情况以及旋转方式;

    当绿色节点与红色节点其中一个节点为新增节点时需要进行左右双旋操作;

    此处旋转操作演示以绿色节点为例;


  • 代码段

    void RotateLR(Node *parent){Node *cur = parent->_left;Node *curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);/*对平衡因子重新进行调整*/if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}}
    

    对于双旋操作来说,该操作只需要去调用单旋操作的接口即可;

    但除此之外还需要对其中的平衡因子进行调整(在单旋中的平衡因子调整并不是双旋操作所期望的结果,故需要在最后对平衡因子进行调整);


🦭右左双旋操作

请添加图片描述

右左双旋操作与左右双旋操作相同,只不过调用左单旋接口与右单旋接口的顺序不同,其对应的平衡因子调整也与之不同;

该处直接对几种情况的具象图对右左双旋操作进行解析;

  • 具象图情况

    1. 当树的高度h0


    2. 当树的高度h1

      此处演示了其中的两种情况;


    3. 当树的高度h2

      该处可以类比于左右双旋操作,对此不再进行赘述;

  • 代码段

    void RotateRL(Node *parent){Node *cur = parent->_right;Node *curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);/*对平衡因子重新进行调整*/if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}
    

至此插入函数的逻辑到此结束;


🦈检查AVL树是否符合AVL树的规则

请添加图片描述

  • 当插入结束后如何判断所插入的数据以及树的结构是否符合AVL树的性质?

如上题,如何在插入过后对AVL树的结构进行检查,确保在数据插入后能检查此AVL树的实现是否存在问题;

从该问题中可以以上文了解到AVL树的性质规则:

  1. 左右子树的高度差不超过1;

  2. 符合搜索二叉树的规则;

左右子树的高度差的判断可以使用两种方法,即采用递归的方式判断该树是否符合AVL树的规则;

由于该树是基于搜索二叉树的规则进行设置,故对于树的存储规则可以不用过分追究;

同时由于树节点的结构中存储了平衡因子,为了防止特殊情况的平衡因子异常导致的树的结构紊乱,应该在检查过程中添加对于平衡因子检查的控制,即一个节点的左右子树的高度差是否符合该节点的平衡因子;

  • 代码段

     bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node *root){if(root == nullptr){return true;}int leftH = getHeight(root->_left); // the leftH is subtree height for left;int rightH = getHeight(root->_right);if(rightH - leftH != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}//return abs(rightH - leftH) < 2 && IsBalance(root->_left) && IsBalance(root->_right);}

🦈最终代码

请添加图片描述

#pragma once#include<iostream>#include<assert.h>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 std::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 (cur == parent->_left){parent->_bf--;}else // if (cur == parent->_right){parent->_bf++;}if (parent->_bf == 0){// 更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 继续往上更新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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}//Insert函数反括号bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node *root){if(root == nullptr){return true;}int leftH = getHeight(root->_left); // the leftH is subtree height for left;int rightH = getHeight(root->_right);if(rightH - leftH != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}//return abs(rightH - leftH) < 2 && IsBalance(root->_left) && IsBalance(root->_right);}void InOrder(){_InOrder(_root);}protected:int getHeight(){return getHeight(_root);}int getHeight(Node *root){if(root == nullptr){return 0;}int left = getHeight(root->_left);int right = getHeight(root->_right);return left>right?left+1:right+1;}void RotateL(Node* parent){//右高左旋Node *cur = parent->_right;Node *curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node *ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateR(Node *parent){ //左高右旋Node *cur = parent->_left;Node *curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node *ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateLR(Node *parent){Node *cur = parent->_left;Node *curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}}void RotateRL(Node *parent){Node *cur = parent->_right;Node *curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}void _InOrder(const Node *root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_kv.first << " : " << root->_kv.second << std::endl;_InOrder(root->_right);}private:Node *_root = nullptr;
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/238845.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ES6前端学习笔记

修正 ES6是ECMA为JavaScript制定的第6个标准版本&#xff0c;相关历史可查看此章节《ES6-ECMAScript6简介》。 标准委员会最终决定&#xff0c;标准在每年6月正式发布并作为当年的正式版本&#xff0c;接下来的时间里就在此版本的基础上进行改动&#xff0c;直到下一年6月草案…

在微服务架构中认证和授权的那些事儿

在微服务架构中认证和授权是最基础的服务能力&#xff0c;其中这一块行业类的标准就是OAuth2 和 SSO &#xff0c;而OAuth2 和 SSO 可以归类为“用户管理和身份验证”工具&#xff0c;OpenID Connect 1.0是 OAuth 2.0 协议之上的一个简单身份层。 Part.1 认识OAuth 2.0 OAuth…

【数据结构】C语言实现共享栈

共享栈的C语言实现 导言一、共享栈1.1 共享栈的初始化1.2 共享栈的判空1.3 共享栈的入栈1.3.1 空指针1.3.2 满栈1.3.3 入栈空间错误1.3.4 正常入栈1.3.5 小结 1.4 共享栈的查找1.5 共享栈的出栈1.6 共享栈的销毁 二、共享栈的实现演示结语 导言 大家好&#xff0c;很高兴又和大…

领域驱动设计——DDD领域驱动设计进阶

摘要 进阶篇主要讲解领域事件、DDD 分层架构、几种常见的微服务架构模型以及中台设计思想等内容。如何通过领域事件实现微服务解耦&#xff1f;、怎样进行微服务分层设计&#xff1f;、如何实现层与层之间的服务协作&#xff1f;、通过几种微服务架构模型的对比分析&#xff0…

基于Java (spring-boot)的社团管理系统

一、项目介绍 系统管理员的功能概述&#xff1a; ①用户管理 a.注册用户账户 当一个新用户注册时&#xff0c;用户填写基本信息并上传。用户基本信息包括账号、 姓名、密码、手机、地址等信息。 b.用户信息管理 管理员可以查看系统所有用户的基本信息&#xff0c;并修改和…

【征服redis2】redis的事务与lua

1.redis事务介绍 在前面我们介绍了redis的几种典型数据结构和应用&#xff0c;本文我们来看一下redis的事务问题。事务也是数据库的重要主题&#xff0c;熟悉关系型数据库的读者应该对事务比较了解&#xff0c;简单地说&#xff0c;事务表示一组动作&#xff0c;要么全部执行&…

基于Springboot的善筹网(众筹网-有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的善筹网(众筹网-有报告)。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring S…

2024年全网最全春招时间线

2024年全网最全春招时间线 春招&#xff0c;许多同学可能会误以为这是春天才会进行。 你可能会想&#xff0c;期末刚考完试&#xff0c;先享受下寒假&#xff0c;再欢度春节&#xff0c;收些红包&#xff0c;甚至还能抽空去理个发型。等到春日明媚时&#xff0c;再参加春招活…

【数据结构】归并排序的非递归写法和计数排序

前言 &#x1f493;作者简介&#xff1a; 加油&#xff0c;旭杏&#xff0c;目前大二&#xff0c;正在学习C&#xff0c;数据结构等&#x1f440; &#x1f493;作者主页&#xff1a;加油&#xff0c;旭杏的主页&#x1f440; ⏩本文收录在&#xff1a;再识C进阶的专栏&#x1…

表单验证 ---- 在Vue2中使用ElementUI进行表单验证

目录 前言 给表单绑定对应属性 在data中定义数据对象和表单的定义规则 与数据对象双向绑定 对整个表单进行验证 前言 在做项目时&#xff0c;对于表单进行验证是我们必不可少的 例如 搭建一个基本的登录界面 <div class"form"><h1>登录</h1>&…

电商物流查询:未来的发展方向

在电商日益繁荣的时代&#xff0c;物流信息查询不仅关乎消费者体验&#xff0c;更影响着电商运营的效率。快速、准确地追踪物流信息至关重要。本文将简述物流信息快速追踪的价值&#xff0c;并重点介绍固乔快递查询助手这一高效查询工具及其批量查询功能。 一、物流信息快速追踪…

一、docker的安装与踩坑

目录 一、安装docker&#xff08;centos7安装docker&#xff09;1.安装环境前期准备2.参考官网安装前准备3.参考官网安装步骤开始安装docker4.运行首个容器 二、安装一些软件的踩坑1.启动docker踩坑2.安装mysql踩坑3.罕见问题 三、关于我的虚拟机 一、安装docker&#xff08;ce…

鸿蒙开发(三)理解UIAbility

前文提到过&#xff0c;在使用DevEco创建鸿蒙项目的时候&#xff0c;会选择Empty Ability&#xff0c;那么这个Ability是什么呢&#xff1f;其实对比Android Studio创建Android羡慕时选择的Empty Activity&#xff0c;感觉Harmony的Ability更像是Android的Activity&#xff0c;…

持久双向通信网络协议-WebSocket-入门案例实现demo

1 介绍 WebSocket 是基于 TCP 的一种新的网络协议。它实现了浏览器与服务器全双工通信——浏览器和服务器只需要完成一次握手&#xff0c;两者之间就可以创建持久性的连接&#xff0c; 并进行双向数据传输。 HTTP协议和WebSocket协议对比&#xff1a; HTTP是短连接&#xff0…

利用人工智能和机器人技术实现复杂的自动化任务!

这篇mylangrobot项目由neka-nat创建&#xff0c;本文已获得作者Shirokuma授权进行编辑和转载。 https://twitter.com/neka_nat GitHub-mylangrobot &#xff1a;GitHub - neka-nat/mylangrobot: Language instructions to mycobot using GPT-4V 引言 本项目创建了一个使用GPT-4…

【K8S 云原生】Kurbernets集群的调度策略

目录 一、Kubernetes的list-watch机制 1、List-watch 2、创建pod的过程&#xff1a; 二、scheduler调度的过程和策略&#xff1a; 1、简介 2、预算策略&#xff1a;predicate 3、优先策略&#xff1a; 3.1、leastrequestedpriority&#xff1a; 3.2、balanceresourceal…

爬虫利器一览

前言 爬虫&#xff08;英文&#xff1a;spider&#xff09;&#xff0c;可以理解为简单的机器人&#xff0c;如此一个“不为名利而活&#xff0c;只为数据而生&#xff0c;目标单纯&#xff0c;能量充沛&#xff0c;不怕日晒雨淋&#xff0c;不惧寒冬酷暑”的家伙&#xff0c;…

含PEMFC的热电联供系统能量管理策略Simulink仿真

1.光伏发电系统 在直流微电网中&#xff0c;光伏电池系统经过升压DC/DC变换器接入直流微电网提供功率。在不同的系统运行条件下&#xff0c;光伏电池系统有三种工作模式&#xff1a;MPPT 模式、下垂模式和空闲模式。由于光伏阵列的输出特性随着环境条件影响&#xff0c;光伏电池…

【科技素养题】少儿编程 蓝桥杯青少组科技素养题真题及解析第22套

少儿编程 蓝桥杯青少组科技素养题真题及解析第22套 1、植物的叶子多为绿色,这主要是因为它们含有 A、绿色色素 B、叶绿素 C、花青素 D、细胞 答案:B 考点分析:主要考查小朋友们生物知识的储备;叶绿素是植物叶子中的一种色素,它可以吸收太阳光中的能量并转化为植物所…

数据库多表查询练习题

二、多表查询 1. 创建 student 和 score 表 CREATE TABLE student ( id INT ( 10 ) NOT NULL UNIQUE PRIMARY KEY , name VARCHAR ( 20 ) NOT NULL , sex VARCHAR ( 4 ) , birth YEAR , department VARCHAR ( 20 ) , address VARCHAR ( 50 ) ); 创建 s…