【C++】红黑树讲解及实现
前言:
AVL树与红黑树相似,都是一种平衡二叉搜索树,但是AVL树的平衡要求太严格,如果要对AVL树做一些结构修改的操作性能会非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此,如果要对一个结构经常修改,AVL树就不太适合,这时就需要运用对平衡要求不太严格的红黑树。
一,红黑树的认识
红黑树是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
红黑树确保没有一条路径会比其他路径长出俩倍的原因是由红黑树的性质决定。
红黑树的性质
1. 每个结点不是红色就是黑色。
2. 根节点是黑色的。
3. 如果一个节点是红色的,则它的两个孩子结点必须是黑色的。即从上层到下层不存在连续的红节点。
4. 对于每个结点,从该结点到其所有后代叶子结点的简单路径上(包含此节点),均包含相同数目的黑色结点,即每条路径均包含相同数量的黑色节点。
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。这里所到最终节点指的就是空节点。如上图中NIL空节点为黑色。
红黑树就是满足以上的性质才确保没有一条路径会比其他路径长出两倍。至于原因我们可来设想一下极端情况。由于任意一个节点到其所有后代叶子结点的黑色节点相同,且红色节点不能连续出现,所以极端情况下,我们令一个节点的左边为最短路径——全部黑色,高度h,右边为最长路径——黑色节点之间每隔一个都有一个红色节点,高度最大为2*h。这样我们得出最大路径刚好是最小路径的两倍。由此看来,红黑树下任意节点的路径之差在 [h,2h] 区间。
红黑树对比AVL树可得,红黑树对平衡的要求不是那么严格,比较宽松,虽说效率逊于AVL树,但是综合性能比AVL树高。而且AVL树的高度很接近 logN,红黑树高度很接近 2*logN,logN 的数值足够小,两者之间效率基本微乎其微,基本可忽略不计。
二,红黑树的插入操作
2-1,红黑树节点的定义
红黑树的结点定义大致跟AVL树一样,唯一要不同的是红黑树中没有平衡因子,只包含颜色。
//节点的颜色——这里用枚举表示
enum Color
{
RED, //红色
BLACK //黑色
};//红黑树节点的结构
template <class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _parent; //双亲节点
RBTreeNode<K, V>* _left; //左孩子节点
RBTreeNode<K, V>* _right; //右孩子节点
Color _color; //节点颜色
pair<K, V> _kv; //节点数据RBTreeNode(const pair<K, V>& kv) //为了后面插入方便,这里构造为红色节点
: _parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _color(RED)
, _kv(kv)
{ }
};
2-2,红黑树的插入操作
红黑树的插入跟AVL树一样,都是在二叉搜索树的基础上加上了平衡限制,因此可分为两步:1,按照二叉搜索树的规则进行插入。2,检测插入后的红黑树是否造到平衡破坏,若平衡被破坏,这里要进行旋转或变色(由于这里的平衡是根据颜色来控制的,插入后若平衡别破坏颜色管理一定失调,但插入后颜色失调不一定会导致平衡破坏,这里可想象一下当平衡满足AVL平衡时插入的场景)。
红黑树由于要满足左右所有路径上的黑色节点相同,若插入黑色节点会引发上面一系列结构问题和不平衡现象,因此这里最好插入红色节点。
首先我们先来考虑什么情况下插入新节点后不会发生旋转和变色。这里很显然,若我们在黑色节点后面插入新节点(红色节点)是不会影响颜色管理,至于是否影响平衡还要看极端情况。在极端情况下插入发生平衡失调,这绝对不会插入在黑色节点后面。因此若插入新节点在黑色节点后面我们可放任不管。
若我们插入的新节点cur在红色节点后面,此时的红色结点必然无孩子且一定要进行变色(恢复红黑树颜色规则),还可能要进行旋转(恢复红黑树平衡规则),因为若此时红色结点存在一个孩子,那么这个孩子必然是黑色的,这样一来就违背了红黑树的左右路径黑色结点数量相同的性质。此情况下,因为cur的双亲结点是红色的,所以必然会存在黑色的爷爷结点,所以,这里的情况可分为三类谈论:1,存在cur的叔叔节点(双亲结点的兄弟结点)且为红。2,不存在cur的叔叔结点。3,存在cur的叔叔结点且为黑。其中情况二和情况三在代码实现中可分为一种情况,具体原因下面会说明。
情况一:(存在cur的叔叔节点u且为红)
我们来看新插入结点cur的叔叔结点为红色时的情况。根据已有条件可知,cur的双亲结点parent(简写:p)为红色,那么cur的爷爷结点grandparent(简写:g)必为黑色,叔叔结点uncle(简写:u)为红色。如下图:
我们先来观察a结构。这里先只看以p为根节点的子树,由于p为红色,且插入cur之前p的左边路径为1,所以a要么为空,要么只有一个黑色结点。当为黑色结点时,左右路径的黑色结点数量不相等,所以a只能为空。b和c同理,只看以g为根节点的子树结构,b和c不能为黑色,但b和c为红色,这里也不能为红色,所以只能为空。如下:
这种情况下是否需进行旋转暂不明确,但显然违反了颜色规则——红色结点之间相连,需进行颜色变换。颜色变色这块需明白,当一个结点变色后是不会影响此节点的下层颜色规则,只会影响上面结构。因此,这里变色规则是p和u变黑色,g变红色,控制原本黑色结点的数量不变(保证上层结构)。如果g是根节点再将其变黑色,然后结束操作;如果g不是根节点,需要继续往上查看,因为这里虽说满足黑色结点数量的规则,但是g变成了红色,g的双亲结点可能为红色或黑色。当g的双亲结点为黑色时颜色变色后满足规则,可直接结束;当g的双亲结点为红色时,这里就要将重复操作,即将cur = g,继续排查,直到遇到p为黑色或cur为根节点为止。注意:这里往上排查过程中也可能遇到情况2(u结点不存在)或情况3(u结点存在且为黑色),这里先提前说一下,其实排查过程中不可能遇到情况2,至于原因和遇到情况3下面会详细说明。
这里有两个问题。1,p结点和g结点是否存在,即是否为空。2,平衡是否被破坏,即是否需要进行旋转。
问题一:
p结点可能为空,此时cur结点为根节点,对照上面cur为根节点直接处理情况,若在刚开始p为空,此时新插入结点cur为根节点,插入后直接返回即可。
g结点这里一定不为空,因为当g结点为空时,p结点就是根节点,p结点一定为黑色。我们使用g结点的前提条件是p结点为红色,若p是黑色直接退出,根本就没有g结点这一环节。
问题二:
这种条件下平衡一定不会被破坏。插入新节点后平衡被破坏的前提是插入前结构必为极端情况,而在极端情况下cur必有叔叔结点u且为黑或无叔叔结点u。因此,此种情况只需变色,无需旋转。从这可说明,发生旋转和变色的只有cur存在叔叔结点u且为黑色或无叔叔结点u。
注意,在情况一下又可划分为四种情况,如下:
1,p是g的左孩子,u是g的右孩子,新插入结点cur是p的左孩子。(如上图)
2,p是g的左孩子,u是g的右孩子,新插入结点cur是p的右孩子。
3,p是g的右孩子,u是g的左孩子,新插入结点cur是p的左孩子。
4,p是g的右孩子,u是g的左孩子,新插入结点cur是p的右孩子。
这里划分的四种情况都可看成一种情况,因为这里只需变色无需旋转,针对的目标是p、u、g三结点的颜色,至于谁是左孩子谁是右孩子根本不理会。
情况二:(不存在cur的叔叔结点u)
当不存在叔叔结点u时插入新节点cur时显然违反了平衡规则——左右最大高度与最小高度不满足二倍关系,至于怎么旋转我们从AVL树中可知需看cur、p的具体位置(前文中已有AVL树旋转的详细讲解以及原理,若这里不明白的请看前文AVL树讲解),然而这里存在四种小情景:
1,p是g的左孩子,新插入结点cur是p的左孩子。p一定没有右孩子,因为p为红色且插入前无左孩子。此种情景跟AVL树中插入在g的左子树的左侧相似,进行右单旋,旋转后还要变色。为了保证这里黑色结点数量不变(保证上层结构)且在此子树下的左右路径黑色结点数量相同(保证本层子树结构,即最底层结构),需将g变为红色,p变为黑色,如下图:
2,p是g的左孩子,新插入结点cur是p的右孩子。p一定没有左孩子,因为p为红色且插入前无右孩子。此种情景跟AVL树中插入在g的左子树的右侧相似,进行左右旋,旋转后也要变色。这里的变色规则跟上面一样,即将g变为红色,cur变为黑色,如下图:
3,p是g的右孩子,新插入结点cur是p的左孩子。与上同理,这里p一定无右孩子。此种情景跟AVL树中插入在g的右子树的左侧相似,进行右左旋,旋转后也要变色。这里的变色规则跟上面一样,即将g变为红色,cur变为黑色。
4,p是g的右孩子,新插入结点cur是p的右孩子。与上同理,p一定无左孩子。此种情景跟AVL树中插入在g的右子树的右侧相似,进行左单旋,旋转后还要变色,需将g变为红色,p变为黑色。
当出现此种情况时,cur绝不可能是往上排查中的情况,必定为新插入结点,因为在这种情况下,以g为根节点的子树左右路径之差根本不满足红黑树的性质,例如以上面情景四为例,当cur不是新插入的结点时,g的左边高度固定为1,右边高度大于3。
这里当发生这种情况时,旋转变色后可直接退出,因为无论出现以上哪四种场景,旋转后都将恢复原本平衡,变色后在g位置的结点都为黑色,根本不影响上层结点情况或g为根节点情况。
情况三:(存在cur的叔叔结点且为黑)
首先,我们先来观察cur为新插入结点时遇到此情况的时候。
我们来分析以上情况,这里叔叔结点u为黑色,根据红黑树性质,这里以g为根节点的子树中a结构必须有一个黑色结点,但在插入前图中p没有左孩子,这里以p为根节点的子树中情景跟上面一样,a结构必须为空,与上形成矛盾,因此cur为新插入结点的情况根本不可能出现,也就是说cur的叔叔结点为黑色的情况下只能是cur不为新插入的结点,即情况一中往上排查中遇到的情况(遇到情况二一步操作后直接退回)。
从情况一中的问题二可知,发生旋转和变色的情况只有在cur必有叔叔结点u且为黑色或无叔叔结点u的条件下,其中无叔叔结点只能是在刚插入时的情况,而此情况只能在上层中遇到,但注意,当遇到此种情况时还不能说明平衡一定被破坏,即平衡可能被破坏也可能没有被破坏。为了方便起见,这里处理的方式是无论平衡是否被破坏都进行旋转处理,因为旋转调节后我们严格遵守红黑树的颜色管理,也就间接不会破坏平衡;而且旋转的本质是将高度大的一方减一,高度小的一方加一,此种情况又是在上层结构中遇到的,当平衡时旋转调节后一定不会破坏这里的平衡。当平衡被破坏时,路径最长的是2*h+1(新插入结点的一方),路径最短的是h,旋转之后路径最长的变为2*h,路径最短的变为h+1,满足条件。
旋转之前我们来分析已确定的条件。首先,这里叔叔既然存在且为黑,那么必然存在g结点。其次,这里的cur结点是情况一中往上排查时上一次的g结点——原本是黑色的现在变成红色的,相当于又一次检验,因此cur是红色的,那么p结点也是红色的,如果p是黑色的,在情况一中就直接退出了,根本不会进行到下一轮,且就算叔叔结点u是黑色的,但若双亲结点p是黑色的根本不可能出现不平衡现象,即颜色失调现象。最后,由于p是红色的,那么g是黑色的。总的来说,当发生这种情况时,就已确定g结点和u结点是黑色的,p结点和cur结点是红色的。
此种情况跟情况二相似,对应的也有四种不同位置的场景,由于需要进行旋转,所以这里都要进行讨论。
1,cur是p的左孩子,p是g的左孩子,u是g的右孩子。
这里我们要明白是左右中的哪里高度出现了问题,需在哪里进行旋转。上面说过,存在叔叔节点u且为黑时进行旋转必然是插入前已处于极端情况下,此处高度大的一方就是cur的一方,因此此场景的旋转类似于AVL树中插入在g的左子树的左侧,进行右单旋。旋转后这里违背了颜色分配规则,具体的变化规则必须要依据插入前的原结构。插入前a、b、c、d、e结构尚未可知,但除去a、b、c、d、e结构外,g结点位置的左边无黑色结点,右边有一个黑色结点,g位置上是黑色结点(防止上面的双亲结点),除了这里已知结点外,还要注意a、b、c、d、e结构中头节点的颜色(为了周全,这里最好全部都看成不为空时的情况),即a、b、c的头节点必定为黑,d、e未知,因此这里需注意d、e为红的情况——若为红色,它们的双亲必须是黑色;若为黑色,它们的双亲可随意。旋转后必须也要满足此条件和以上注意情况,否则颜色分配这里可能就会出问题,因此,这里颜色的变化是将p变为黑色,g变为红色,如下图。
2,cur是p的右孩子,p是g的左孩子,u是g的右孩子。
这里高度大的一方还是cur的一方,原因与上一样。此时场景如同AVL树中插入在g的左子树的右侧,旋转的方式是左右旋——先左旋后右旋。颜色变化更上面场景原理一样,除去a、b、c、d、e结构,g位置的右边有一个黑色结点,g位置的左边没有黑色结点,g位置上是一个黑色结点(为了防止g位置的双亲结点)。这里还是将a、b、c、d、e子树结构看成都不为空时的情况,其中a、b、c的根节点必是黑色的,d、e的根节点可能是红色的,因此,这里旋转后连接d、e的结点必须也是黑色的。具体的颜色变化是将cur变成黑色,g变成红色,如下图:
3,cur是p的左孩子,p是g的右孩子,u是g的左孩子。
这里cur高度超出范围,与上一样。此时的旋转跟AVL树中插入在g的右子树的左侧时进行的旋转一样——进行左右旋(先左单旋后右单旋)。旋转后颜色的变化逻辑思想与上相同,g位置上是黑色结点,g位置左边有一个黑色结点,g位置右边没有黑色结点,且d、e子树结构的根节点可能是红色的。变色后应满足以上规则且连接d、e子树结构的结点必须是黑色的。因此,这里的颜色变色规则是g变成红色,cur变成黑色,如下图:
4,cur是p的右孩子,p是g的右孩子,u是g的左孩子。
这里cur高度超出范围,与上一样。此时的旋转跟AVL树中插入在g的右子树的右侧时进行的旋转一样——进行左单旋。旋转后颜色的变化逻辑思想与上相同,g位置上是黑色结点,g位置左边有一个黑色结点,g位置右边没有黑色结点,且d、e子树结构的根节点可能是红色的。变色后应满足以上规则且连接d、e子树结构的结点必须是黑色的。因此,这里的颜色变色规则是g变成红色,p变成黑色,如下图:
这里不难发现,处于这种情况下的无论哪种场景,叔叔结点u以及叔叔结点u下层的结构不做任何改变,至于p和cur下层的结构若不为空,根节点必为黑色,这里完全不影响上面结点的颜色。仔细思考可发现,这里发生的旋转和不同场景下颜色的改变跟情况二中无叔叔结点时一摸一样—,即g结点的位置是黑色的且满足颜色分配,旋转变色后可直接退出,可归为一类。
代码实现
总上所述,这里红黑树的插入操作逻辑大致是这样:当插入结点的双亲结点是黑色的不做任何处理;当插入结点的双亲结点是红色的,这时分两种情况来判断:1,存在叔叔结点且为红。2,存在叔叔结点且为黑或不存在叔叔结点。当存在叔叔结点且为红,这种情况只用于变色并向上做出排查,直到排查到根节点;当不存在叔叔结点或存在叔叔结点且为黑,直接进行旋转并变色后退出。由于情况一需要对叔叔结点进行变色,而情况二需要确定叔叔结点的位置以便确定哪种旋转,所以这里可再分两种小情况进行讨论——叔叔结点u是g的左孩子或叔叔结点u是g的右孩子。于情况一而言,这里只用变色,无需注意其它结点位置;于情况二而言,由于需要旋转,只确定p和u的位置还不够,还需确定cur的具体位置。代码如下:
bool Insert(const pair<K, V>& kv)
{
//1,插入节点
if (_root == nullptr)
{
_root = new Node(kv);
_root->_color = BLACK;
return true;
}
Node* cur = _root;
Node* parent = _root->_parent;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (parent->_kv.first > kv.first)
{
parent->_left = new Node(kv);
cur = parent->_left;
}
else
{
parent->_right = new Node(kv);
cur = parent->_right;
}
cur->_parent = parent;//2,旋转或变色
//只用处理插入结点cur的双亲结点是红色时的情况,要注意cur是根节点的情况
while (parent && parent->_color == RED)
{
//存在parent且parent是红色时,由于根节点是黑,所以一定存在它的双亲结点
Node* grandparent = parent->_parent;
//cur双亲结点parent在左,叔叔结点uncle在右
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
//情况一: 存在叔叔结点且为红
//这种情况平衡不会被破坏,不用关心结点的具体位置,只需变色
if (uncle && uncle->_color == RED)
{
//变色
grandparent->_color = RED;
parent->_color = uncle->_color = BLACK;
//往上排查
cur = grandparent;
parent = cur->_parent;
}
//情况二: 存在叔叔结点且为黑或不存在叔叔结点
else
{
//情景一: p是g的左孩子,u是g的右孩子,cur是p的左孩子
if (cur == parent->_left)
{
//旋转
RotateR(grandparent);
//变色
grandparent->_color = RED;
parent->_color = BLACK;
}
//情景二: p是g的左孩子,u是g的右孩子,cur是p的右孩子
else
{
//旋转
RotateLR(grandparent);
//变色
grandparent->_color = RED;
cur->_color = BLACK;
}
break;//旋转变色后直接退出
}
}
//cur双亲结点parent在右,叔叔结点uncle在左
else
{
Node* uncle = grandparent->_left;
//情况一: 存在叔叔结点且为红
//情况以上一样,这里只需变色无需旋转
//这里之所以不能单独列出来是因为叔叔结点不确定是否存在
if (uncle && uncle->_color == RED)
{
//变色
grandparent->_color = RED;
parent->_color = uncle->_color = BLACK;
//继续往上排查
cur = grandparent;
parent = cur->_parent;
}
//情况二: 存在叔叔结点且为黑或不存在叔叔结点
else
{
//情景三: p是g的右孩子,u是g的左孩子,cur是p的左孩子
if (cur == parent->_left)
{
//旋转
RotateRL(grandparent);
//变色
grandparent->_color = RED;
cur->_color = BLACK;
}
//情景四: p是g的右孩子,u是g的左孩子,cur是p的右孩子
else
{
//旋转
RotateL(grandparent);
//变色
grandparent->_color = RED;
parent->_color = BLACK;
}
break;//旋转变色后直接退出
}
}
}
//直接暴力解决cur为根节点情况
_root->_color = BLACK;
return true;
}//旋转算法
void RotateL(Node* parent) //左单旋
{
Node* cur = parent->_right;
Node* curL = cur->_left;
Node* pparent = parent->_parent;//旋转
parent->_right = curL;
if (curL)
curL->_parent = parent;//更新节点
if (parent == _root)
{
_root = cur;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = cur;
cur->_parent = pparent;
}
else
{
pparent->_right = cur;
cur->_parent = pparent;
}
}//旋转
cur->_left = parent;
parent->_parent = cur;
}void RotateR(Node* parent) //右单旋
{
Node* cur = parent->_left;
Node* curR = cur->_right;
Node* pparent = parent->_parent;//旋转
parent->_left = curR;
if (curR)
curR->_parent = parent;//更新节点
if (parent == _root)
{
_root = cur;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = cur;
cur->_parent = pparent;
}
else
{
pparent->_right = cur;
cur->_parent = pparent;
}
}//旋转
cur->_right = parent;
parent->_parent = cur;
}void RotateLR(Node* parent) //左右旋
{
//先左再右两次旋转
RotateL(parent->_left);
RotateR(parent);
}void RotateRL(Node* parent) //右左旋
{
//先右再左两次旋转
RotateR(parent->_right);
RotateL(parent);
}
2-3,红黑树的验证
红黑树的验证不能根据红黑树的特点判断,即不能根据最长路径不超过最短路径的二倍来判断。红黑树之所以路径会满足此特点是由红黑树的性质决定的,但反过来,满足路径关系却不一定满足红黑树的性质,所以这里要根据红黑树的性质进行验证。
红黑树的检测分为两步:1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 2. 检测其是否满足红黑树的性质。
这里重点说明第二步。红黑树的性质验证的核心检查有三点:1,根节点是黑色的。2,没有连续的红色结点。3,每条路径的黑色结点的数量相等。
第一点代码很好实现,不做过多说明。第二点直接使用前序遍历整个树,当遍历到此时结点为红色时查看它的双亲结点,若双亲结点也是红色的验证失败。第三点方法有很多,这里可先从树的根节点选任意一个路径,记录此路径黑色结点的数量作为标杆,然后不断前序遍历所有路径,若有任意一个路径的黑色结点数量与之不同,那么遍历失败。原因很简单,树的所有路径都可看成从根节点开始的路径的子路径,只要我们在每个结点到叶子结点路径上遇到黑色结点的数量加上上面从根节点开始到此路径的黑色结点数,就如同从根节点开始的一条路径黑色结点数,即任意一个结点(这里是根节点)到后代所有路径的黑色结点数比较。
//核心检查三步:1,根节点是黑色的。2,没有连续的红色结点。3,每条路径的黑色结点的数量相等。
bool IsBalance()
{
//核心检查1—根节点是黑色的
if (_root && _root->_color == RED)
return false;
//核心检查3—每条路径的黑色结点的数量相等
Node* cur = _root;
//检查3中,先检查红黑树的左子树黑色结点总共的个数,即标杆
size_t sign = 0;
while (cur)
{
if (cur->_color == BLACK)
sign++;
cur = cur->_left;
}
return Check(_root, 0, sign);
}
bool Check(const Node* root, size_t blacknum, size_t sign)
{
//一条路径结束,开始判断黑色结点数量是否相同
if (!root)
{
if (blacknum != sign)
return false;
return true;
}
//核心检查2—没有连续的红色结点
Node* parent = root->_parent;
if (root->_color == RED && parent->_color == RED) //root结点是红色时一定不是根节点
return false;
//检查3中,然后以标杆做依据,遍历每个路径的黑色结点也之是否相同
if (root->_color == BLACK)
blacknum++;
return Check(root->_left, blacknum, sign) && Check(root->_right, blacknum, sign);
}
相关文章:
【C++】红黑树讲解及实现
前言: AVL树与红黑树相似,都是一种平衡二叉搜索树,但是AVL树的平衡要求太严格,如果要对AVL树做一些结构修改的操作性能会非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更…...
security如何不拦截websocket
只要添加一个关键配置就行 //忽略websocket拦截Overridepublic void configure(WebSecurity webSecurity){webSecurity.ignoring().antMatchers("/**");} 全部代码我放着了 package com.oddfar.campus.framework.config;import com.oddfar.campus.framework.secur…...
Unity类银河恶魔城学习记录12-3 p125 Limit Inventory Slots源代码
Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Inventory.cs using Newtonsoft.Json.Linq; using System.Collections; us…...
【智能排班系统】雪花算法生成分布式ID
文章目录 雪花算法介绍起源与命名基本原理与结构优势与特点应用场景 代码实现代码结构自定义机器标识RandomWorkIdChooseLocalRedisWorkIdChooselua脚本 实体类SnowflakeIdInfoWorkCenterInfo 雪花算法类配置类雪花算法工具类 说明 雪花算法介绍 在复杂而庞大的分布式系统中&a…...
sass中的导入与部分导入
文章目录 sass中的导入与部分导入1. import:传统的导入方式2. use:现代化的模块化导入 sass中的导入与部分导入 在大型前端项目中,CSS代码量往往十分庞大,为了保持其可读性、可维护性以及便于团队协作,模块化开发成为…...
工业组态 物联网组态 组态编辑器 web组态 组态插件 编辑器
体验地址:by组态[web组态插件] BY组态是一款非常优秀的纯前端的【web组态插件工具】,可无缝嵌入到vue项目,react项目等,由于是原生js开发,对于前端的集成没有框架的限制。同时由于BY组态只是一个插件,不能独…...
git可视化工具
Gitkraken GitKraken 是一款专门用于管理和协作Git仓库的图形化界面工具。它拥有友好直观的界面,使得Git的操作变得更加简单易用,尤其适合那些不熟悉Git命令行的开发者。GitKraken提供了丰富的功能,如代码审查、分支管理、仓库克隆、提交、推…...
基于单片机电子密码锁系统设计
**单片机设计介绍,基于单片机电子密码锁系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机电子密码锁系统设计概要主要包括以下几个方面: 一、系统概述 基于单片机电子密码锁系统是一个…...
点云从入门到精通技术详解100篇-基于点云与图像纹理的 道路识别(续)
目录 3.1.2 图像滤波去噪 3.2 道路纹理特征提取 3.3 基于超像素分割的图像特征表达...
《机器学习在量化投资中的应用研究》目录
机器学习在量化投资中的应用研究 获取链接:机器学习在量化投资中的应用研究_汤凌冰著_北京:电子工业出版社 更多技术书籍:技术书籍分享,前端、后端、大数据、AI、人工智能... 内容简介 《机器学习在量化投资中的应用研究…...
Spring拓展点之SmartLifecycle如何感知容器启动和关闭
Spring为我们提供了拓展点感知容器的启动与关闭,从而使我们可以在容器启动或者关闭之时进行定制的操作。Spring提供了Lifecycle上层接口,这个接口只有两个方法start和stop两个方法,但是这个接口并不是直接提供给开发者做拓展点,而…...
深入理解Java匿名内部类(day21)
在Java编程中,匿名内部类是一种非常有用的特性,它允许我们定义和实例化一个类的子类或实现一个接口,而无需给出子类的名称。这种特性使得代码更加简洁、紧凑,尤其适用于一些只使用一次的临时对象。本文将深入探讨Java匿名内部类的…...
《状态模式(极简c++)》
本文章属于专栏- 概述 - 《设计模式(极简c版)》-CSDN博客 模式说明: 方案:状态模式是一种行为设计模式,用于在对象的内部状态发生改变时改变其行为。它包括三个关键角色:上下文(Context&#x…...
Day4-Hive直播行业基础笔试题
Hive笔试题实战 短视频 题目一:计算各个视频的平均完播率 有用户-视频互动表tb_user_video_log: id uid video_id start_time end_time if_follow if_like if_retweet comment_id 1 101 2001 2021-10-01 10:00:00 2021-10-01 10:00:30 …...
mybatis批量新增数据
数据量大的时候如果在循环中执行单条新增操作,是非常慢的。那么如何在mybatis中实现批量新增数据呢? 方法 insert 标签的 foreach 属性可以用于批量插入数据。您可以使用 foreach 属性遍历一个集合,并为集合中的每个元素生成一条插入语句。…...
webrtcP2P通话流程
文章目录 webrtcP2P通话流程webrtc多对多 mesh方案webrtc多对多 mcu方案webrtc多对多 sfu方案webrtc案例测试getUserMediagetUserMedia基础示例-打开摄像头getUserMedia canvas - 截图 打开共享屏幕 webrtcP2P通话流程 在这里,stun服务器包括stun服务和turn转发服…...
游戏引擎中的物理系统
一、物理对象与形状 1.1 对象 Actor 一般来说,游戏中的对象(Actor)分为以下四类: 静态对象 Static Actor动态对象 Dynamic Actor ---- 可能受到力/扭矩/冲量的影响检测器 TriggerKinematic Actor 运动学对象 ---- 忽略物理法则…...
【C++ STL有序关联容器】map 映射
文章目录 【 1. 基本原理 】【 2. map 的创建 】2.1 调用默认构造函数,创建一个空的 map2.2 map 被构造的同时初始化2.3 通过一个 queue 初始化另一个 queue2.4 取已建 map 中指定区域内的键值对,初始化新的 map2.5 指定排序规则 【 2. map 元素的操作 】…...
【ZZULIOJ】1041: 数列求和2(Java)
目录 题目描述 输入 输出 样例输入 Copy 样例输出 Copy code 题目描述 输入一个整数n,输出数列1-1/31/5-……前n项的和。 输入 输入只有一个整数n。 输出 结果保留2为小数,单独占一行。 样例输入 Copy 3 样例输出 Copy 0.87 code import java.util…...
C++【适配器模式】
简单介绍 适配器模式是一种结构型设计模式 | 它能使接口不兼容的对象能够相互合作。(是适配各种不同接口的一个中间件) 基础理解 举个例子:当你引用了一个第三方数据分析库,但这个库的接口只能兼容JSON 格式的数据。但你需要它…...
go | 上传文件分析 | http协议分析 | 使用openssl 实现 https 协议 server.key、server.pem
是这样的,现在分析抓包数据 test.go package mainimport ("fmt""log""github.com/gin-gonic/gin" )func main() {r : gin.Default()// Upload single filer.MaxMultipartMemory 8 << 20r.POST("/upload", func(c *g…...
Chatgpt掘金之旅—有爱AI商业实战篇|专业博客|(六)
演示站点: https://ai.uaai.cn 对话模块 官方论坛: www.jingyuai.com 京娱AI 一、AI技术创业博客领域有哪些机会? 人工智能(AI)技术作为当今科技创新的前沿领域,为创业者提供了广阔的机会和挑战。随着AI技…...
单例模式 JAVA
单例模式 什么是单例模式? 1、单例类只能有一个实例。2、单例类必须自己创建自己的唯一实例。3、单例类必须给所有其他对象提供这一实例。 应用:数据库的连接类,这样就可以确保只创建一次。节省资源。 单例模式代码:涉及懒加载…...
C++从入门到精通——初步认识面向对象及类的引入
初步认识面向对象及类的引入 前言一、面向过程和面向对象初步认识C语言C 二、类的引入C的类名代表什么示例 C与C语言的struct的比较成员函数访问权限继承默认构造函数默认成员初始化结构体大小 总结 前言 面向过程注重任务的流程和控制,适合简单任务和流程固定的场…...
GitHub入门与实践
ISBN: 978-7-115-39409-5 作者:【日】大塚弘记 译者:支鹏浩、刘斌 页数:255页 阅读时间:2023-08-05 推荐指数:★★★★★ 好久之前读完的了,一直没有写笔记。 这本入门Git的书籍还是非常推荐的,…...
centos 安装 stable-diffusion 详细流程
一、安装git 新版 先安装git 工具来更新git源码 , 载下源码后卸载git 版本(centos 默认1.8版本,说是安装会引起失败) 安装git 命令,可使用 git --version查看版本 sudo yum install git -y 卸载git命令 sudo yum remove git 正式源码安装…...
CSS编写登录框样式
/* 重置浏览器默认样式 */ * { margin: 0; padding: 0; box-sizing: border-box; } /* 设置登录框的基本样式 */ .login-box { width: 100%; max-width: 400px; margin: 50px auto; background-color: #f4f4f4; padding: 20px; box-shad…...
Python|OpenCV-获取鼠标点击位置的坐标,并绘制图像(13)
前言 本文是该专栏的第14篇,后面将持续分享OpenCV计算机视觉的干货知识,记得关注。 本文主要来详细说明,基于OpenCV来获取鼠标点击位置的坐标,并按坐标的位置进行自动绘制图像。具体怎么实现,笔者在正文中将结合实际代码案例进行详细说明。 具体细节部分以及完整代码的实…...
设计模式(14):命令模式
介绍 将一个请求封装为一个对象,从而使我们可用不同的请求对象客户进行参数化;对请求排队或者记录请求日志,以及支持可撤销的操作。也称之为:动作Action模式,事务transaction模式。 命令模式角色 抽象命令类(Comman…...
关于阿里云云数据库自动扩缩容和自动SQL优化的20道面试题
1. 请解释阿里云云数据库自动扩缩容的概念及其工作原理。 阿里云云数据库自动扩缩容是一种基于数据库实例的实时性能数据,能够发现流量异常并提供合理的数据库规格建议和磁盘容量建议的功能。其工作原理如下: 性能监控:系统会实时监控数据库…...
如何用c 做网站/百度下载免费安装最新版
引言 async/await是非常棒的语法糖,可以说他是解决异步问题的最终解决方案。从字面意思来理解。async 是异步的意思,而 await 是 等待 ,所以理解 async用于申明一个function是异步的,而 await 用于等待一个异步方法执行完成。 asy…...
高端模板网站建设/百度网页版怎么切换
把列表中的正数和负数分开排列. lst [1, -2, 10, -11, 123, -124] lst.sort(keylambda x: (x < 0, abs(x))) print(lst) [1, 10, 123, -2, -11, -124] 把多维列表转为一维列表 list_1 [[1, 2], [3, 4, 5], [6, 7], [8], [9]] # function 1 print([i for k in list_1 for i…...
兰州做公司网站/小程序开发工具
简介在处理数据的时候,经常会在MySQL里面格式化时间进行统计。DATE_FORMAT() 函数用于以不同的格式显示日期/时间数据。用法select DATE_FORMAT(date,format) from table;date 参数是合法的日期。format 规定日期/时间的输出格式,可以有下面的格式&#…...
集团公司网站开发/长沙市网站制作
人活着是为了什么,与动物等生物相比,有什么特别的意义。 选择一种什么样的生活方法,度过这一辈子,是我一直在思考的问题。未曾有过明确的答案,不过,一直在探索。 今天呢,想把我当前阶段的思考…...
潍坊潍微贷是哪家网站建设的/优化师
上个月最后一天的凌晨,Spring Cloud Alibaba 正式入驻了 Spring Cloud 官方孵化器,并在 maven 中央库发布了第一个版本。 目前 Spring Cloud Alibaba 还只能算是预览版吧,里边的坑肯定不少,不过我还是决定试试,看看 Al…...
新浪微博可以做网站吗/北京朝阳区优化
一. 下载: 终端输入指令: pip3 install pymysql如果失败就检查 pip 指令的环境变量是否配置; 若不会,则自行百度;等待下载完成后, 在终端直接进入 python 环境, 导入该模块, 若无报错,则证明下载成功.(如下图所示) 二. 开始使用: 1, 在py文件中导入该模块: import pymysql 2, 连…...