当前位置: 首页 > news >正文

探索数据结构:红黑树的分析与实现

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯,先赞后看哦~🎈🎈

所属专栏:数据结构与算法
贝蒂的主页:Betty’s blog

1. 红黑树的介绍

1.1. 红黑树的引入

我们前面学习了AVL树,知道其本质是通过旋转操作来确保每个节点的左右子树高度差不超过 1,以此解决数据有序或接近有序时二叉搜索树退化为单边树而导致查找效率低下的问题。然而,当插入数据量过大时,频繁的旋转操作同样会使效率降低。为应对这一问题,就有人提出了一种更为特殊的树——红黑树

红黑树是一种自平衡的二叉查找树,查找效率高。它由Rudolf Bayer于 1978 年发明,当时被称为平衡二叉B树。后来,在 1978 年,Leo J. GuibasRobert Sedgewick对其进行了修改,形成了如今的红黑树。

1.2. 红黑树的特点

首先,红黑树属于二叉搜索树,其特点是在每个节点额外增加了一个存储位用于记录节点的颜色,该颜色可以是 RED,也可以是 BLACK。 并且红黑树通过对任意一条从根到叶子的简单路径上颜色的约束,能够保证最长路径不会超过最短路径的二倍,从而实现近似平衡,减少旋转的效果。其具体特点如下:

  1. 节点颜色只有黑色与红色两种颜色。
  2. 根节点一定是黑色。
  3. 空节点null一定为黑色,并且在红黑树中认为null节点才是叶子节点。
  4. 红色节点的子节点和父节点一定为黑色。
  5. 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点。

img

为什么上述规则能保证红黑树最长路径不超过最短路径的两倍?

具体来说,根据上述规则可以得出最短路径即为全是黑节点的路径,最长路径则是一个红节点接着一个黑节点。当从根节点到叶子节点的路径上黑色节点数量相同时,最长路径恰好是最短路径的两倍。

2. 红黑树的功能

以下是红黑树常见的功能:

  1. 红黑树的插入。
  2. 红黑树的查找。
  3. 红黑树的删除。

3. 红黑树的结构

3.1. 红黑树的节点

红黑树的节点本质与二叉搜索树的节点差不多,所以肯定有三个成员变量:左子树_left,右子树_right,键值_kv,并且键值我们采用KV模型的形式。并且还有一个表示节点颜色的变量_col,以及一个父节点_parent。并且为了增加代码的可读性,我们可以定义一个枚举来表示颜色。当然为了适配不同的类型,我们同样需要定义一个模版.。

template<class K,class V>
struct RBTreeNode
{RBTreeNode(const pair<K,V>& kv = pair<K,V>(), Color col = RED):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(col)//默认为红节点{}RBTreeNode<K, V>* _left;//左子树RBTreeNode<K, V>* _right;//右子树RBTreeNode<K, V>* _parent;//父节点pair<K, V> _kv;//键值Color _col;//颜色
};

为什么插入新节点的颜色默认是红色而不是黑色呢?

  • 若插入的是黑色节点,会导致插入路径的黑色节点数量增加,破坏原每条路径黑色节点数量相同的平衡特性,需要对所有路径进行调整,非常麻烦。
  • 若插入节点为红色,则需分情况讨论。当插入节点的父节点为黑色时,不会违反红黑树规则,无需处理。而当插入节点的父节点为红色时,由于红黑树不能有连续的红色节点,此时就需要进行调整。但是因为只需调整该路径,所以明显更简单。

综上所述,红黑树插入节点默认设为红色能在一定程度上减少违反规则的情况,同时降低调整树结构的复杂性。

3.2. 红黑树

然后我们就可以通过节点来定义红黑树,并将根节点初始化为空。

template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://...具体功能
private:Node* _root = nullptr;//根节点
};

4. 红黑树的初始化与销毁

4.1. 构造函数/拷贝构造/赋值重载

首先我们直接定义一个无参的构造函数,因为我们在定义拷贝构造之后编译器就不会在生成默认的构造函数了。

RBTree()
{}

之后我们可以利用递归来实现一个拷贝构造函数。

RBTree(const RBTree<K, V>&t)
{_root = copy(t._root);
}
Node* copy(Node* root)
{// 如果原始节点为空,直接返回空指针if (root == nullptr){return nullptr;}// 为新节点分配内存并拷贝原始节点的值Node* newnode = new Node(root->_kv);// 递归拷贝左子树newnode->_left = copy(root->_left);// 递归拷贝右子树newnode->_right = copy(root->_right);// 将新节点的父节点指针置为空newnode->_parent = nullptr;// 拷贝原始节点的颜色信息newnode->_col = root->_col;// 如果新节点的左子节点存在,设置其父节点为新节点if (newnode->_left){newnode->_left->_parent = newnode;}// 如果新节点的右子节点存在,设置其父节点为新节点if (newnode->_right){newnode->_right->_parent = newnode;}
}

最后我们通过一个简单的方式实现赋值重载——通过形参调用拷贝构造出一个临时变量,然后交换this所指向的变量,这样原本this所指向的对象出了作用域就会销毁,间接实现了实现赋值重载。

RBTree<K, V> operator =(const RBTree<K, V> t)
{this->swap(_root, t._root);return *this;
}

4.2. 析构函数

析构函数需要借助递归释放所有节点,而为了方便我们传参我们可以定义子函数来帮助我们解决。

~RBTree()
{Destroy(_root);
}
void Destroy(Node*& root)
{if (root == nullptr){return;}//递归销毁左子树Destroy(root->_left);//递归销毁右子树Destroy(root->_right);//销毁根节点delete root;root = nullptr;
}

5. 红黑树的功能实现

不论是红黑树的插入还是删除操作都需要用到旋转操作,如果你还不知道旋转操作的具体内容可以先看看这篇文章——AVL树。当然具体的旋转操作也看到也有细微的区别,因为红黑树并不存在平衡因子,但是主体思路肯定不会改变。

5.1. 红黑树的插入

向红黑树进行插入,首先是先找到需要插入的位置,这个逻辑与二叉搜索树类似,这里就不在赘述。找到之后插入默认的红节点,此时就可以分为五种情况来讨论:

为了方便叙述,我们首先假设插入节点为cur,其父节点为parent,其父节点的兄弟节点为uncle,其父节点的父节点为grandfather

其中下面图示抽象的情况可能是红黑树整体,也可能是红黑树的某个子树。

5.1.1. 情况一

第一种情况就是第一次插入,也就是插入根节点,此时根据性质1我们只需要将对应颜色从RED改为BLACK即可。

5.1.2. 情况二

第二种情况就是插入节点的父节点是黑节点,符合红黑树的定义,所以此时也不需要做任何调整,直接插入即可。

5.1.3. 情况三

第三种情况就是插入节点的父节点parent是红节点,其父节点的兄弟节点uncle也为红节点,并且祖父节点grandfather是黑节点。如下图:

并且为了方便我们之后的null节点不画出,默认存在。其中a,b,c,d,e五颗子树中黑色节点数量都相同。

img

这种情况的调整方法也很简单,直接将parentuncle变为黑色,grandfather变为红色即可。

img

当然镜像对称后调整方式也是同理,所以这里就不在赘述。

注意:祖父节点grandfather可能不是根节点,当祖父节点parent变为红色节点时可能会引起上面节点的冲突(祖父节点的父节点也为红色),这时就需要循环调整。并且如果祖父节点grandfather是根节点,该调整方法会将根节点变为红节点,所以这时需要将根节点改回黑节点。

img

5.1.4. 情况四

第四种情况严格来说又可以分为两种情况:一种是cur为红色,parent也为红色,grandfather也为黑色,但是uncle不存在。如下图:

其中a,b,c三颗子树中除了null外没有黑色节点。

img

还有一种是cur为红色,parent也为红色,grandfather也为黑色,uncle存在且为黑色·。如下图:

其中a,b,c三颗子树中黑色节点的数量比d,e两棵子树黑色节点的数量多1。

img

当然这种情况肯定不是新插入红色节点造成的,因为一旦cur是新插入节点,那么a,b两棵子树高度为0,没有任何节点,肯定无法满足黑色节点数量比c,d,e多1这个条件。所以这种情况肯定是子树从情况三变换得来的。

针对以上两种情况我们都先右单旋,再将parent变为黑色,grandfather变为红色。当然镜像对称后调整方式也是同理,将旋转改为左单旋转即可,所以这里就不在赘述。

img

img

并且调整完毕后该子树的根节点是黑节点,所以也并不需要往上调整。

5.1.5. 情况五

最后一种情况与第四种情况条件相同:就是cur为红色,parent也为红色,grandfather也为黑色,uncle不存在/存在且为黑色。只不过插入节点位置有所区别。

其中a,b,c三颗子树中除了null外没有黑色节点。

img

其中a,b,c三颗子树中黑色节点的数量比d,e两棵子树黑色节点的数量多1。同样与情况四相同,这种情况不可能是插入造成的,一定是由情况三变化而来。

img

针对以上两种情况我们都先左右双旋,最后将cur变为黑色,grandfather变为红色。当然镜像对称后调整方式也是同理,将旋转改为右左双旋即可,所以这里就不在赘述。

img

img

并且调整完毕后该子树的根节点是黑节点,所以也并不需要往上调整。

默认插入节点为红色,最后我们对插入操作总结如下:

  1. 情况一:新插入的节点为根节点,将其颜色设置为黑色。
  2. 情况二:新插入节点的父节点为黑色,无需调整。
  3. 情况三:父节点和叔父节点均为红色,将父节点和叔父节点改为黑色,祖父节点改为红色,然后以祖父节点为当前节点继续进行调整,如果祖父节点是根节点则停止调整并将其改为黑色。
  4. 情况四:父节点为红色,叔父节点不存在/存在为黑色,当前节点是父节点的左子节点且父节点又是祖父节点的左子节点/当前节点是父节点的右子节点且父节点又是祖父节点的右子节点。先进行左单旋/右单旋,然后将父节点改为黑色,祖父节点改为红色。
  5. 情况五:父节点为红色,叔父节点不存在/存在为黑色,当前节点是父节点的左子节点且父节点又是祖父节点的右子节点/当前节点是父节点的右子节点且父节点又是祖父节点的左子节点。先进行左右双旋/右左双旋,然后将当前节点改为黑色,祖父改为红色。
bool Insert(const pair<K, V>& kv)
{//情况一:如果是根节点if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;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 && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况三:如果叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//情况四:叔叔不存在/存在且为黑,且cur在parent的左侧if (cur == parent->_left){//     g  //   p   u// c RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况五:叔叔不存在 / 存在且为黑,cur在parent的右侧{//     g//   p   u//     cRotateLR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//这时该子树的根节点变为黑色,不需要继续调整break;}}else{Node* uncle = grandfather->_left;//情况三:如果叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续调整cur = grandfather;parent = cur->_parent;}else{//情况四:叔叔不存在/存在且为黑,且cur在parent的左侧if (cur == parent->_right){//    g//  u   p//        cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // 情况五:叔叔不存在 / 存在且为黑,cur在parent的右侧{//    g//  u   p//    cRotateRL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//这时该子树的根节点变为黑色,不需要继续调整break;}}}//防止情况三改到根节点变为红色_root->_col = BLACK;return true;
}
void RotateR(Node* parent)
{Node* cur = parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}
}
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}
}
void RotateLR(Node* parent)
{RotateL(parent->_left);RotateR(parent);
}
void RotateRL(Node* parent)
{RotateR(parent->_right);RotateL(parent);
}

5.2. 红黑树的查找

红黑树的查找的逻辑本质与二叉搜索树的查找逻辑相同,所以这里就不在赘述。

Node* Find(const K& val)
{Node* cur = _root;while (cur){if (cur->_kv.first > val){//左子树中查找cur = cur->_left;}else if (cur->_kv.first < val){//右子树中查找cur = cur->_right;}else{//找到了return cur;}}return nullptr;
}

5.3. 红黑树的删除

删除红黑树的逻辑明显比插入逻辑更加复杂,但是总体逻辑又与AVL树与二叉搜索树类似,首先第一步找到待删除节点,如果待删除节点的左右子树都不为空,可以采用伪删除法,即寻找到左子树的最右节点(左子树的最大值),或者是右子树的最左节点(右子树的最小值),然后赋值,转换为在其左子树或者右子树删除节点,保证待删除节点的左右子树至少有一个为空。第二步进行调整,删除该节点可能会破坏红黑树的性质所以这时需要调整。第三步删除节点并重新链接

第一步与第三步都非常简单,我们接下来重点讨论第三步。

为了方便描述我们将待删除节点称为delete,其父节点称为parent,其兄弟节点称为brother,其兄弟节点的左右节点分别称为broLeftbroRight

看图需知

  1. 如果parent为蓝色,表示parent可能为黑色也可能为红色。
  2. 如果broLeftbroRight为蓝色,表示broLeftbroRight可能为黑色也可能为红色,也可能为null节点。
  3. 如果broLeftbroRight为黑色,表示broLeftbroRight可能为黑色也可能为null节点。
  4. 绿色长方形表示高度未知的子树,也可以为null节点。

下面图示我们将按照delete节点在parent节点左侧的形式讨论,根据镜像对称delete节点在parent节点右侧只需对称操作即可,所以这里就不在赘述。

首先如果delete节点为红色,因为至少有一个空节点,那么另一个子节点既不能为红色也不可能为黑色,此时直接删除即可。

其次如果delete节点为黑色,且有一个孩子节点,那么这个孩子节点一定为红色,(parentbrother不都为红色)否则会破坏性质5。这种情况也只需重新链接不需要调整,然后将该孩子节点改为黑色。

imgimg

接下来我们将讨论delete节点为黑色且没有孩子节点的情况。

  1. 情况一:兄弟节点为红色。

因为兄弟节点为红色,其父节点一定为黑色,所以对于这种情况我们只需要对parent节点进行一次左旋转,再将brother变为黑色,parent变为红色。再重新更新brother节点,继续分析原删除节点delete,将情况一转换为情况二,三,四。

img

img

  1. 情况二:兄弟节点为黑色,且其左右孩子为空或者都为黑色。

对于这种情况我们需要将brother变为红色,然后根据parent节点颜色继续分析,如果parent节点为红色,只需要将其变为黑色即可,调整结束;如果parent节点为黑色,那么delete节点被删除后,原来该子树有两个黑色节点变为一个,性质5被破坏,将parent节点当做删除节点往上更新或者遇见根节点直接停止,将情况二转换为情况一,二,三,四。

img

img

  1. 情况三:兄弟节点为黑色,且其左孩子是红色结点,右孩子是黑色结点或为空。

这种情况一定不是第一次调整,因为如果是第一次调整此时根本不平衡。对应这种情况我们需要对brother节点进行一次右单旋,然后再将brother结点变为红色,broLeft变为黑色,最后更新brother节点,再对delete节点进行调整,情况三就转换成了情况四。

img

img

  1. 情况四:兄弟节点为黑色,且其右孩子是红色结点。

对于这种情况我们先将parent节点进行一次左单旋,然后将parent的颜色赋值给brother,再将parent的颜色变为黑色,最后将broRight变为黑色,此时红黑树的调整一定结束。

img

img

最后删除节点如果是根节点直接删除再将左子树或者右子树的根节点变黑,当做新的根节点。如果没有左右子树都为空,那就将根节点_root置为空。

最后我们来总结

  1. 如果删除节点为红色,直接删除。
  2. 如果删除节点为黑色且有一个子节点,直接删除再链接,并将该子节点改为黑色。
  3. 如果删除节点为黑色且没有子节点,可以分为以下四种情况:
  • 情况一:兄弟节点为红色。先对parent左单旋,再将brother变为黑色,将parent变为红色,再对待删除结点delete进行情况分析,情况一就转换成了情况二、三或四。
  • 情况二:兄弟节点为黑色,且其左右孩子为空或者都为黑色。我们直接将brother变成红色,若parent是红色,将parent变为黑色后调整结束;若parent是黑色,则需将parent结点当作下一次调整时的结点进行分析直至根节点,情况二就转换成了情况一,二、三或四。
  • 情况三:兄弟节点为黑色,且其左孩子是红色结点,右孩子是黑色结点或为空。先将brother右单旋,再将brother变为红色,broLeft变为黑色,再对待删除结点delete进行情况分析,将情况三转换成情况四。
  • 情况四:兄弟节点为黑色,且其右孩子是红色结点。先将parent左单旋,然后将parent的颜色赋值给brother,再将parent变为黑色,最后将brotRight变为黑色,此时红黑树的调整一定结束。

思考题:为什么删除节点为黑色且没有子节点的四种情况的调整方法一定能使红黑树调整成功?

我们知道这四种调整方法一共有三个"出口",分别为:(1)情况二调整后parent为红色,(2)情况二parent为黑色调整到根节点,(3)调整完情况四。所以问题就成功转换为经过任意三个"出口"结束之后,为什么红黑树一定调整成功。

  1. 如果从1号"出口"结束:一个子节点被删除后,因为使parent变为黑色,另一个子节点变为红色,所以此时这颗子树的路径上的黑色节点数没减少,调整成功。
  2. 如果从2号"出口"结束:一定是只经过情况二,因为如果是从情况一转换过来的情况二,那parent一定是红色就会从1号"出口"结束。如果只经过情况二那么每次操作都会使上层的一颗子树(非父节点所在子树)黑色节点数减一,最后更新到根节点整颗红黑树根节点到叶子节点的黑色节点数比原来少1,调整成功。
  3. 如果从3号"出口"结束:经过第四种调整方式,被删除一侧的黑色节点数增一,无论是从第一,二,三删除节点后都会使被删除一侧减一,所以经过情况四调整成功。

思考题:为什么删除节点为黑色且没有子节点的四种情况的调整方法不会造成死循环?

因为情况三一定会被转换为情况四,情况四一定会调整成功,所以情况三与情况四一定不会死循环。而情况一与情况二也可能转换为情况三与情况四这时也不会死循环。但会不会出现情况一与情况二一直互相循环的情况呢?其实不会的,因为一旦从情况一转换为情况二,此时父节点parent为红色,一定会结束。

//删除函数
bool Erase(const K& key)
{//(一)找到删除节点Node* cur = Find(key);//未找到返回falseif (cur == nullptr){return false;}//记录父节点Node* parent = cur->_parent;//用于标记实际的待删除结点及其父结点Node* delParent = nullptr;Node* delCur = nullptr;if (cur->_left == nullptr) //待删除结点的左子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_right; //让根结点的右子树作为新的根结点if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent = parent; //标记实际删除结点的父结点delCur = cur; //标记实际删除的结点}}else if (cur->_right == nullptr) //待删除结点的右子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_left; //让根结点的左子树作为新的根结点if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent = parent; //标记实际删除结点的父结点delCur = cur; //标记实际删除的结点}}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_kv = minRight->_kv; //将待删除结点的键值改为minRight的键值delParent = minParent; //标记实际删除的父节点delCur = minRight; //标记实际删除的结点}//记录待删除结点及其父结点,便于后面删除Node* del = delCur;Node* delP = delParent;//(二)调整红黑树AdjustRBTree(delCur, delParent);//(三)进行实际删除DeleteNode(del, delP);return true;
}
void DeleteNode(Node* del, Node* delP)
{if (del->_left == nullptr) //实际删除结点的左子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_right;//指向父节点if (del->_right)del->_right->_parent = delP;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_right;if (del->_right)del->_right->_parent = delP;}}else //实际删除结点的右子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_left;if (del->_left)del->_left->_parent = delP;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_left;if (del->_left)del->_left->_parent = delP;}}delete del; //实际删除结点
}
void AdjustRBTree(Node* delCur, Node* delParent)
{if (delCur->_col == BLACK) //删除的是黑色结点{if (delCur->_left) //待删除结点有一个红色的左孩子(不可能是黑色){delCur->_left->_col = BLACK; //将这个红色的左孩子变黑即可}else if (delCur->_right) //待删除结点有一个红色的右孩子(不可能是黑色){delCur->_right->_col = BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delCur != _root) //可能一直调整到根结点{if (delCur == delParent->_left) //待删除结点是其父结点的左孩子{Node* brother = delParent->_right; //兄弟结点是其父结点的右孩子//情况一:brother为红色if (brother->_col == RED){delParent->_col = RED;brother->_col = BLACK;RotateL(delParent);//需要继续处理brother = delParent->_right; //更新brother}//情况二:brother为黑色,且其左右孩子都是黑色结点或为空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParent->_col == RED){delParent->_col = BLACK;break;}//需要继续处理delCur = delParent;delParent = delCur->_parent;}else{//情况三:brother为黑色,且其左孩子是红色结点,右孩子是黑色结点或为空if ((brother->_right == nullptr) || (brother->_right->_col == BLACK)){brother->_left->_col = BLACK;brother->_col = RED;RotateR(brother);//需要继续处理brother = delParent->_right; //更新brother}//情况四:brother为黑色,且其右孩子是红色结点brother->_col = delParent->_col;delParent->_col = BLACK;brother->_right->_col = BLACK;RotateL(delParent);break; //情况四执行完毕后调整一定结束}}else //delCur == delParent->_right //待删除结点是其父结点的右孩子{Node* brother = delParent->_left; //兄弟结点是其父结点的左孩子//情况一:brother为红色if (brother->_col == RED) //brother为红色{delParent->_col = RED;brother->_col = BLACK;RotateR(delParent);//需要继续处理brother = delParent->_left; //更新brother}//情况二:brother为黑色,且其左右孩子都是黑色结点或为空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParent->_col == RED){delParent->_col = BLACK;break;}//需要继续处理delCur = delParent;delParent = delCur->_parent;}else{//情况三:brother为黑色,且其右孩子是红色结点,左孩子是黑色结点或为空if ((brother->_left == nullptr) || (brother->_left->_col == BLACK)){brother->_right->_col = BLACK;brother->_col = RED;RotateL(brother);//需要继续处理brother = delParent->_left; //更新brother}//情况四:brother为黑色,且其左孩子是红色结点brother->_col = delParent->_col;delParent->_col = BLACK;brother->_left->_col = BLACK;RotateR(delParent);break; //情况四执行完毕后调整一定结束}}}}}
}

6. 判断是否为红黑树

判断是否为红黑树首先得判断是否为二叉搜索树,然后判断是否满足红黑树的性质。

判断是否满足红黑树的性质,首先判断根节点是否为黑色。然后统计一条路径的节点个数,最后通过递归判断是否有连续的红色节点,以及每条路径的黑色节点是否相同。

bool IsRBTree()
{if (_root->_col == RED){cout << "根节点为红节点" << endl;return false;}//从根节点到叶节点的黑色节点数int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum) && isValidBST();
}
//判断是否为二叉搜索树
bool isValidBST()
{return _isValidBST(_root, LONG_MIN, LONG_MAX);
}
bool _isValidBST(Node* root, long long lower, long long upper)
{if (root == nullptr){return true;}if (root->_kv.first <= lower || root->_kv.first >= upper){return false;}bool left = _isValidBST(root->_left, lower, root->_kv.first);bool right = _isValidBST(root->_right, root->_kv.first, upper);return left && right;
}
bool Check(Node* root, int blackNum, int refNum)
{if (root == nullptr){//判断黑色节点数是否相同if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}//判断是否存在连续的红色节点if (root->_parent && root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);
}

7. 复杂度分析

对于红黑树的插入、查找和删除操作,其时间复杂度和空间复杂度分析如下:
时间复杂度:

  • Insert操作:平均和最坏情况下的时间复杂度均为 O ( log ⁡ n ) O(\log n) O(logn)。插入过程中需要调整红黑树的性质,可能涉及到旋转操作,但这些操作的时间是常数级,而查找插入位置的过程类似于二叉搜索树,时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)
  • Find操作:平均和最坏情况下的时间复杂度均为 O ( log ⁡ n ) O(\log n) O(logn)。与二叉搜索树的查找过程类似,通过比较键值逐渐缩小搜索范围,每次比较都能将范围缩小一半。
  • Erase操作:平均和最坏情况下的时间复杂度均为 O ( log ⁡ n ) O(\log n) O(logn)。删除节点时需要查找节点位置,然后根据红黑树的性质进行调整和可能的旋转操作,这些操作的时间复杂度与插入操作相似。

空间复杂度:

  • Insert操作:空间复杂度为 O ( 1 ) O(1) O(1)。在插入过程中,主要的额外空间消耗在于创建新节点以及存储一些临时变量,如指针等,这些空间消耗是常数级的。
  • Find操作:空间复杂度为 O ( 1 ) O(1) O(1)。寻找过程中仅使用了少量的固定数量的指针和临时变量,没有额外的大规模空间分配。
  • Erase操作:空间复杂度为 O ( 1 ) O(1) O(1)。删除操作中的主要空间消耗在于存储临时变量和指针,不会动态分配大规模的额外空间。

8.源码

#pragma once
#include<utility>
enum _col
{RED,//红色BLACK//黑色
};
template<class K,class V>
struct RBNode
{RBNode(const pair<K,V>& kv = pair<K,V>(), _col col = RED):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(col)//默认为红节点{}RBNode<K, V>* _left;//左子树RBNode<K, V>* _right;//右子树RBNode<K, V>* _parent;//父节点pair<K, V> _kv;//键值_col _col;//颜色
};
template<class K, class V>
class RBTree
{typedef RBNode<K, V> Node;
public:RBTree(){}RBTree(const RBTree<K, V>&t){_root = copy(t._root);}RBTree<K, V> operator =(const RBTree<K, V> t){this->swap(_root, t._root);return *this;}bool Insert(const pair<K, V>& kv){//情况一:如果是根节点if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;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 && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况三:如果叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//情况四:叔叔不存在/存在且为黑,且cur在parent的左侧if (cur == parent->_left){//     g  //   p   u// c RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况五:叔叔不存在 / 存在且为黑,cur在parent的右侧{//     g//   p   u//     cRotateLR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//这时该子树的根节点变为黑色,不需要继续调整break;}}else{Node* uncle = grandfather->_left;//情况三:如果叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续调整cur = grandfather;parent = cur->_parent;}else{//情况四:叔叔不存在/存在且为黑,且cur在parent的左侧if (cur == parent->_right){//    g//  u   p//        cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // 情况五:叔叔不存在 / 存在且为黑,cur在parent的右侧{//    g//  u   p//    cRotateRL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//这时该子树的根节点变为黑色,不需要继续调整break;}}}//防止情况三改到根节点变为红色_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* cur = parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}}void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}Node* Find(const K& val){Node* cur = _root;while (cur){if (cur->_kv.first > val){//左子树中查找cur = cur->_left;}else if (cur->_kv.first < val){//右子树中查找cur = cur->_right;}else{//找到了return cur;}}return nullptr;}//删除函数bool Erase(const K& key){//(一)找到删除节点Node* cur = Find(key);//未找到返回falseif (cur == nullptr){return false;}//记录父节点Node* parent = cur->_parent;//用于标记实际的待删除结点及其父结点Node* delParent = nullptr;Node* delCur = nullptr;if (cur->_left == nullptr) //待删除结点的左子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_right; //让根结点的右子树作为新的根结点if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent = parent; //标记实际删除结点的父结点delCur = cur; //标记实际删除的结点}}else if (cur->_right == nullptr) //待删除结点的右子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_left; //让根结点的左子树作为新的根结点if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent = parent; //标记实际删除结点的父结点delCur = cur; //标记实际删除的结点}}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_kv = minRight->_kv; //将待删除结点的键值改为minRight的键值delParent = minParent; //标记实际删除的父节点delCur = minRight; //标记实际删除的结点}//记录待删除结点及其父结点,便于后面删除Node* del = delCur;Node* delP = delParent;//(二)调整红黑树AdjustRBTree(delCur, delParent);//(三)进行实际删除DeleteNode(del, delP);return true;}void DeleteNode(Node* del, Node* delP){if (del->_left == nullptr) //实际删除结点的左子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_right;//指向父节点if (del->_right)del->_right->_parent = delP;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_right;if (del->_right)del->_right->_parent = delP;}}else //实际删除结点的右子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_left;if (del->_left)del->_left->_parent = delP;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_left;if (del->_left)del->_left->_parent = delP;}}delete del; //实际删除结点}void AdjustRBTree(Node* delCur, Node* delParent){if (delCur->_col == BLACK) //删除的是黑色结点{if (delCur->_left) //待删除结点有一个红色的左孩子(不可能是黑色){delCur->_left->_col = BLACK; //将这个红色的左孩子变黑即可}else if (delCur->_right) //待删除结点有一个红色的右孩子(不可能是黑色){delCur->_right->_col = BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delCur != _root) //可能一直调整到根结点{if (delCur == delParent->_left) //待删除结点是其父结点的左孩子{Node* brother = delParent->_right; //兄弟结点是其父结点的右孩子//情况一:brother为红色if (brother->_col == RED){delParent->_col = RED;brother->_col = BLACK;RotateL(delParent);//需要继续处理brother = delParent->_right; //更新brother}//情况二:brother为黑色,且其左右孩子都是黑色结点或为空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParent->_col == RED){delParent->_col = BLACK;break;}//需要继续处理delCur = delParent;delParent = delCur->_parent;}else{//情况三:brother为黑色,且其左孩子是红色结点,右孩子是黑色结点或为空if ((brother->_right == nullptr) || (brother->_right->_col == BLACK)){brother->_left->_col = BLACK;brother->_col = RED;RotateR(brother);//需要继续处理brother = delParent->_right; //更新brother}//情况四:brother为黑色,且其右孩子是红色结点brother->_col = delParent->_col;delParent->_col = BLACK;brother->_right->_col = BLACK;RotateL(delParent);break; //情况四执行完毕后调整一定结束}}else //delCur == delParent->_right //待删除结点是其父结点的右孩子{Node* brother = delParent->_left; //兄弟结点是其父结点的左孩子//情况一:brother为红色if (brother->_col == RED) //brother为红色{delParent->_col = RED;brother->_col = BLACK;RotateR(delParent);//需要继续处理brother = delParent->_left; //更新brother}//情况二:brother为黑色,且其左右孩子都是黑色结点或为空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParent->_col == RED){delParent->_col = BLACK;break;}//需要继续处理delCur = delParent;delParent = delCur->_parent;}else{//情况三:brother为黑色,且其右孩子是红色结点,左孩子是黑色结点或为空if ((brother->_left == nullptr) || (brother->_left->_col == BLACK)){brother->_right->_col = BLACK;brother->_col = RED;RotateL(brother);//需要继续处理brother = delParent->_left; //更新brother}//情况四:brother为黑色,且其左孩子是红色结点brother->_col = delParent->_col;delParent->_col = BLACK;brother->_left->_col = BLACK;RotateR(delParent);break; //情况四执行完毕后调整一定结束}}}}}}~RBTree(){Destroy(_root);}bool IsRBTree(){if (_root->_col == RED){cout << "根节点为红节点" << endl;return false;}//从根节点到叶节点的黑色节点数int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum)&& isValidBST();}//判断是否为二叉搜索树bool isValidBST(){return _isValidBST(_root, LONG_MIN, LONG_MAX);}private:bool _isValidBST(Node* root, long long lower, long long upper){if (root == nullptr){return true;}if (root->_kv.first <= lower || root->_kv.first >= upper){return false;}bool left = _isValidBST(root->_left, lower, root->_kv.first);bool right = _isValidBST(root->_right, root->_kv.first, upper);return left && right;}bool Check(Node* root, int blackNum, int refNum){if (root == nullptr){if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_parent && root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}void Destroy(Node*& root){if (root == nullptr){return;}//递归销毁左子树Destroy(root->_left);//递归销毁右子树Destroy(root->_right);//销毁根节点delete root;root = nullptr;}Node* copy(Node* root){// 如果原始节点为空,直接返回空指针if (root == nullptr){return nullptr;}// 为新节点分配内存并拷贝原始节点的值Node* newnode = new Node(root->_kv);// 递归拷贝左子树newnode->_left = copy(root->_left);// 递归拷贝右子树newnode->_right = copy(root->_right);// 将新节点的父节点指针置为空newnode->_parent = nullptr;// 拷贝原始节点的颜色信息newnode->_col = root->_col;// 如果新节点的左子节点存在,设置其父节点为新节点if (newnode->_left){newnode->_left->_parent = newnode;}// 如果新节点的右子节点存在,设置其父节点为新节点if (newnode->_right){newnode->_right->_parent = newnode;}}Node* _root = nullptr;
};

相关文章:

探索数据结构:红黑树的分析与实现

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;数据结构与算法 贝蒂的主页&#xff1a;Betty’s blog 1. 红黑树的介绍 1.1. 红黑树的引入 我们前面学习了AVL树&#xff0c;…...

【设计模式】装饰器模式和适配模式

装饰器模式 装饰器模式能够很好的对已有功能进行拓展&#xff0c;这样不会更改原有的代码&#xff0c;对其他的业务产生影响&#xff0c;这方便我们在较少的改动下对软件功能进行拓展。 类似于 router 的前置守卫和后置守卫。 Function.prototype.before function (beforeFn)…...

Visual Studio VS 插件之 ReSharper

集成在VS2022上的ReSharper暂无找到汉化方式&#xff0c;如果有大神可以汉化&#xff0c;请指导下。 首先ReSharper 是IDE 下的插件 主要是基于C# 语句优化的这么一个插件。 使用ReSharper可以使开发效率大大提高&#xff0c;但是也是比较吃电脑的配置。所以说如果配置低的小…...

【二分查找】--- 进阶题目赏析

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; 算法Journey 本篇博客我们继续来了解一些有关二分查找算法的进阶题目。 &#x1f3e0; 寻找峰值 &#x1f4cc; 题目内容 162. 寻找峰值 - 力扣&#…...

CSS 对齐

CSS 对齐 在网页设计中&#xff0c;CSS&#xff08;层叠样式表&#xff09;对齐是一种基本而重要的技术&#xff0c;它决定了网页元素的位置和布局。CSS 提供了多种对齐方法&#xff0c;可以精确控制元素的水平、垂直对齐&#xff0c;以及相对于其父元素或整个页面的位置。本文…...

暑假算法刷题日记 Day 10

目录 重点整理 054、 拼数 题目描述 输入格式 输出格式 输入输出样例 核心思路 代码 055、 求第k小的数 题目描述 输入格式 输出格式 输入输出样例 核心思路 代码 总结 这几天我们主要刷了洛谷上排序算法对应的一些题目&#xff0c;相对来说比较简单 一共是13道…...

【Midjourney】AI作画提示词工程:精细化技巧与高效实践指南

文章目录 &#x1f4af;AI作画提示词基础结构1 图片链接1.1 上传流程 2 文字描述3 后置参数 &#x1f4af;AI作画提示词的文字描述结构1 主体主体细节描述2 环境背景2.1 环境2.2 光线2.3 色彩2.4 氛围 3 视角4 景别构图5 艺术风格6 图片制作方法7 作品质量万能词 &#x1f4af;…...

C语言——文件

文件操作 概念 文件是指存储在外存储器上&#xff08;一般代指磁盘&#xff0c;也可以是U盘&#xff0c;移动硬盘等&#xff09;的数据的集合。 文件操作体现在哪几个方面 1.文件内容的读取 2.文件内容的写入 数据的读取和写入可被视为针对文件进行输入和输出的操作&#xf…...

视频孪生技术在智慧水利(水务)场景中的典型应用展示

一、智慧水利建设规划 根据水利部编制《“十四五”智慧水利建设规划》&#xff0c;建设数字孪生流域、“2N”水利智能业务应用体系、安全可控水利网络安全防护体系、优化健全水利网信保障体系&#xff0c;建成七大江河数字孪生流域&#xff0c;推进水利工程智能化改造&#xf…...

使用kubekey快速搭建k8s集群

项目仓库地址 https://github.com/kubesphere/kubekey/ 支持的Kubernetes Versions https://github.com/kubesphere/kubekey/blob/master/docs/kubernetes-versions.md 安装 选择自己想要下载的版本 https://github.com/kubesphere/kubekey/releases 复制下载链接并下载 示…...

C++——入门基础(上)

目录 一、C参考文档 二、C在工作领域的应用 三、C学习书籍 四、C的第一个程序 五、命名空间 &#xff08;1&#xff09;namespace的定义 (2)命名空间的使用 六、C的输入和输出 七、缺省函数 八、函数重载 九、写在最后 一、C参考文档 &#xff08;1&#xff09;虽…...

Spring事务失效

类内部访问导致事务不生效原因&#xff1a; 注解Transaction的底层实现是Spring AOP技术&#xff0c;而Spring AOP技术使用的是动态代理。spring事务失效的原因就是动态代理失效的原因: 对于static方法和非public方法&#xff0c;注解Transactional是失效的&#xff0c;因为不…...

Qt QLabel标签制作弹框效果,3s后缓慢自动消失

效果图 初始化说明 void InitStatusTips() {if (NULL statusTips_) {return;}statusTips_->setFixedSize(300, 80);//固定大小statusTips_->move((width() - statusTips_->width()) / 2, height() - 30 - statusTips_->height());//移动位置statusTips_->setA…...

JZ55 二叉树的深度

二叉树的深度_牛客题霸_牛客网 递归代码太简单-一行就可以,可以用二叉树的层序遍历&#xff0c;顺便温习下二叉树层序遍历的写法。 对应leetcode 104题&#xff0c;层序遍历对应leetcode-102自顶向下&#xff0c;leetcode-107自底向上 /* struct TreeNode {int val;struct Tre…...

视频号分销系统搭建教程,源代码+部署上线指南

目录 一、视频号分销是什么&#xff1f; 二、视频号分销系统怎么搭建&#xff1f; 1.系统架构设计 2.部署与上线 3.持续迭代与升级 三、部分代码展示 一、视频号分销是什么&#xff1f; 视频号分销系统是合集了视频号商家的产品&#xff0c;推广达人推广商家的产品可赚取…...

【python】cryptography库学习

【python】cryptography库学习 cryptography学习1-安装2-cryptography学习2.1-fernet的使用2.2-padding填充2.3-Hash2.4-ciphers&#xff08;对称算法AES为例&#xff09;2.5-asymmetric(非对称算法RSA为例)函数&#xff1a;generate_private_key类&#xff1a;RSAPrivateKey&a…...

解密!抖音百万粉丝博主三维地图视频都用到了什么GIS数据和技术

引言 在抖音上有许多诸如三维地图科普局、三维地图看世界和三维地图鉴赏等百万粉丝博主靠着三维地图科普城市、景区、人文和地理视频获赞百万&#xff0c;在我们浏览视频时犹如身临其境一般&#xff0c;那么制作这些视频需要什么GIS技术呢&#xff1f;如何利用MapMost技术自己…...

Python知识点:如何使用Kubernetes与Python进行容器编排

Kubernetes 是一个开源的容器编排平台&#xff0c;用于自动化容器化应用的部署、管理和扩展。结合 Python&#xff0c;你可以通过 Kubernetes API 和工具&#xff0c;如 kubectl 和 kubernetes-client 库&#xff0c;来编写和管理容器化应用。以下是如何使用 Kubernetes 和 Pyt…...

Markdown与Word中插入图片的方法及比较

在撰写文档时&#xff0c;无论是技术文档、博客还是学术论文&#xff0c;插入图片都是非常常见的需求。本文将对比两种流行的文本编辑工具——Markdown和Microsoft Word——在插入图片方面的异同点。 Markdown插入图片 如何插入图片 在Markdown中插入图片非常简单&#xff0…...

Vue3+Vite安装配置tailwindCss

考虑到官网不是很好访问&#xff0c;这里记录一下简单步骤方便小友查阅 1. 安装依赖 npm install -D tailwindcss postcss autoprefixer2. 初始化配置文件 npx tailwindcss init -p3.配置模板路径 /** type {import(tailwindcss).Config} */ export default {content: [&quo…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...