可视化红黑树详解（gif图演示，洛谷P3369 普通平衡树）

文章目录

  • 写在前面
  • 红黑树是什么
  • 红黑树的平衡性
  • 红黑树整体框架
  • 旋转操作
  • 插入操作
  • 双红修正
      • Case 1, 2
      • Case 3
      • Case 4
      • Case 5
      • Case 6
  • 删除操作
      • 二叉查找树
      • 红黑树
      • Case 0
      • Case 1
      • Case 2
      • Case 3
  • 双黑修正
      • Case 1
      • Case 2
      • Case 3
      • Case 4
      • Case 5
  • 其他查询操作
      • 查询排名
      • 查询第k大
      • 寻找前驱
      • 寻找后继
  • 最终代码

写在前面

推荐一个很实用的工具：红黑树可视化

本文参考OI wiki中的红黑树代码，读者也可以参考该篇解析（写得还是很不错的），不过OI Wiki里删除后平衡维护的Case 4和Case 5在代码细节上稍微有些问题（把 c c c, d d d 均为红色算进Case 4了，这样不会出bug，只是相当于绕了个弯）。

大部分红黑树代码都采用 rotateLeft 和 rotateRight 两个函数来进行旋转，而且在找close/distant nephew的时候也是分类讨论，这样比较麻烦。
我们其实可以使用 node *ch[2] 来表示左右孩子，ch[0] 表示左孩子，ch[1] 表示右孩子。在后续使用中，我们#define left ch[0], #define right ch[1]，从而兼容用 left, right 找左右孩子的方法。这种存储方式的好处是，我们可以通过异或1来轻松切换左右分支，而不是采用三目运算符来找兄弟节点。
再考虑 rotate，其实 rotate 相当于把某个子节点往上转到其父节点的位置，因此我们可以用同一个 rotate 函数来表示左旋或右旋，使用时旋转左孩子即为 rotateLeft，旋转右孩子即为 rotateRight。

红黑树是什么

如果能把一个又一个节点积累起来，也许就能变成一棵红黑树。 ——高松灯

红黑树是一棵满足特殊性质的二叉搜索树。它的特殊性质有：

  1. 节点均为红色/黑色（顾名思义）
  2. NIL 节点（空叶子节点，有时也叫外部节点）为黑色
  3. 红色节点的子节点均为黑色
  4. 从根节点（不含根节点本身）到 NIL 节点的每条路径上的黑色节点数量相同

（注：有的教材/解析要求根节点一定是黑色，不过这个没有太大影响，根节点是红色也不会影响树的平衡性）

我们把第 4 条性质中，从某节点出发（不含节点本身），到任意 NIL 节点路径上的黑节点数，称为节点的“黑高”（black height）。
这里黑高的定义是比较反直觉的（究竟是谁定义的？），因为既要去掉节点本身，又要加上一个额外的 NIL 节点。
可以用以下递推式来加深对黑高的理解：
b h [ N I L ] = 0 bh[NIL] = 0 bh[NIL]=0
∀ s ∈ s o n ( x ) , \forall s \in son(x), ∀s∈son(x), b h [ x ] = b h [ s ] + [ c o l o r ( s ) = = B L A C K ] bh[x] = bh[s] + [color(s) == BLACK] bh[x]=bh[s]+[color(s)==BLACK]，中括号表示该表达式的bool值，若表达式成立则为1，表达式不成立则为0.

我们把粉色头发的ano酱作为红节点，黑色头发的Rikki作为黑节点，那么下面这棵树是一棵红黑树：
在这里插入图片描述

其中蓝色数字标注的是节点的黑高。
假如给上面这棵树的节点填入权值，就是一棵标准的红黑树：
在这里插入图片描述

红黑树的平衡性

考虑这样一个问题：一棵“黑高”为 h h h的红黑树，至少会有多少节点？（“黑高”是指根到任意NIL节点路径上的黑节点数）
其实可以用归纳法证明结果是 2 h − 1 2^h-1 2h−1，这里提供另一种思路：

对于黑高确定的红黑树，我们要想节点数最少，直接全部放黑节点就可以了。因为往里面放红节点不会对黑高产生任何影响，而且由于红节点的子节点必须是黑节点，放红节点还会让总节点数变得更多。
而全为黑节点的红黑树必然是一棵满二叉树，因为根节点到任意NIL节点路径上的黑节点数相同，如果某个部分缺了一块，那这部分的黑高就会减少。
那么，黑高为 h h h的红黑树，节点最少的情况是一棵高为 h h h，全是黑节点的满二叉树（注意高是 h h h而不是 h + 1 h+1 h+1，因为计算黑高时多统计了一次NIL节点，又少统计一次自身，二者抵消了）。这样的树有 2 h − 1 2^h-1 2h−1个节点。
因此，一棵“黑高”为 h h h的红黑树，至少有 2 h − 1 2^h-1 2h−1个节点。（ N = s i z e o f ( x ) ≥ 2 b h ( x ) − 1 N = \rm sizeof(x)\ge 2^{bh(x)}-1 N=sizeof(x)≥2bh(x)−1）

我们还知道，红节点的两个孩子一定为黑节点，所以说，根节点到NIL节点的路径上，一个红节点就必定有一个黑节点与之对应，所以红节点数一定不超过黑节点数。
因此， b h ( T r e e ) ≥ h ( T r e e ) / 2 \rm bh(Tree)\ge h(Tree)/2 bh(Tree)≥h(Tree)/2。

根据上面两个不等式，可以推出：

一棵有 N N N个节点的红黑树，树高不超过 2 log ⁡ ( N + 1 ) 2\log (N+1) 2log(N+1)。

也就是说，红黑树天生就是平衡的，树高在 O ( log ⁡ N ) O(\log N) O(logN)级别。
假如我们能在插入和删除时维护好红黑树的几条性质，我们就能得到一棵高恒为 O ( log ⁡ N ) O(\log N) O(logN)的二叉搜索树。

红黑树整体框架

红黑树类定义为：

template<typename T>
class RedBlackTree {
	private:
		struct node;
		node* root;		//根节点
		//...
	public:
		int size();
		void insert(T);
		bool remove(T);
		//...
};

节点定义为：

#define RED 1
#define BLACK 0
#define left ch[0]
#define right ch[1] 
template<typename T>
struct RedBlackTree<T>::node {
	T val;			//权值
	bool color;		//1 is red, 0 is black 
	node *father, *ch[2];
	int siz;		//子树大小
	int direction() {
		if(father == NULL)	return 0;
		return father->right == this;
	}
	node* sibling() {
		if(father == NULL)	return NULL;
		return father->ch[direction() ^ 1];
	}
	node* uncle() {
		if(father == NULL)	return NULL;
		return father->sibling();
	}
	void pushup() {
		siz = (left?left->siz:0) + (right?right->siz:0) + 1;
	}
	//......
}

其中val代表节点权值，siz代表子树大小，ch[0] 和 ch[1] 分别代表左右孩子。
direction() 表示当前节点所在分支（0为左孩子，1为右孩子），sibling(), uncle() 是在插入/删除中需要经常用到的亲戚节点。为了方便，我们统一提前写好。

旋转操作

可以参考splay树的旋转操作。这里我们不需要区分左旋和右旋，rotate(x) 表示把节点 x x x 旋转到它父亲的位置。

template<typename T>
void RedBlackTree<T>::connect(node *x, node *fa, int k) {
	if(x != NULL)	x->father = fa;
	if(fa != NULL) {
		fa->ch[k] = x;
	} else {
		root = x;
	}
}

template<typename T>
void RedBlackTree<T>::rotate(node *x) {
	//rotate x to its parent's position
	node* y = x->father;
	node* z = y->father;
	int yson = x->direction();	//the branch of x, 0 is left, 1 is right
	if(z == NULL) {
		root = x;
		x->father = NULL;
	} else {
		int zson = y->direction();
		connect(x, z, zson);
	}
	connect(x->ch[yson^1], y, yson);
	connect(y, x, yson^1);
	y->pushup();
	x->pushup();
}

插入操作

从今天开始，我们就是一起演奏音乐的命运共同体！ ——丰川祥子

红黑树的插入与普通的 BST 的插入操作类似。
我们将新节点作为红节点插入到树中对应位置，再根据相关节点状态进行调整，使整棵树满足红黑树的性质。
具体地说，红黑树要求红节点的子节点均为黑节点，而插入一个红节点可能会使父节点和子节点均为红色，所以在插入后，我们需要进行双红修正。
插入操作的代码实现如下：

template<typename T>
void RedBlackTree<T>::insert(T v) {
	node *x = root, *fa = NULL;
	while(x != NULL) {
		x->siz++;
		fa = x;
		if(v < x->val) {
			x = x->left;
		} else {
			x = x->right;
		}
	}
	x = new node(v, RED, fa);	//create a new node
	if(fa == NULL) {
		root = x;
	} else if(v < fa->val) {
		fa->left = x;
	} else {
		fa->right = x;
	}
	SolveDoubleRed(x);
}

双红修正

不过，为了下次不失败而努力不就好了？就算失败一次，也要有重来的信心。 ——千早爱音

上面的插入过程中，可能会出现父节点和子节点都是红色的连续双红情况，这违反了红黑树的性质。
在 SolveDoubleRed(x) 函数中， x x x 为红节点，我们检查 x x x 的父节点是否为红节点，如果是，则进行修正。（也就是说，这里 x x x 表示连续双红节点的子节点）
修正时，我们要保证红黑树的性质成立，即不出现连续的双红节点，以及保证黑高相同。

在下面的所有注释中，我们用<X>来表示红节点，[X]表示黑节点，{X}表示任意颜色的节点。

Case 1, 2

x x x 为根（父节点为空），或 x x x 的父节点为黑，此时无需修正。下面都是需要修正的情况。

Case 3

x x x 的父节点 p p p 为根节点，此时把 p p p 染黑即可。

if(p == root) {
	// Case 3: Parent is root and is RED
	//   Paint parent to BLACK.
	//    <P>         [P]
	//     |   ====>   |
	//    <X>         <X>
	p->color = BLACK;
	return;
}

Case 4

x x x （图中的 N）的父节点 p p p，叔节点 u u u 均为红色。由于该树原本是一棵合法的红黑树，所以 x x x 的祖父节点 g g g 一定是黑色。
在这里插入图片描述

此时我们将 p p p 和 u u u 染黑，将 g g g 染红，这样在 g g g 以下就不会有连续的红节点。
由于插入前 g g g 到 NIL 节点经历的黑节点数都相同，所以把 p p p, u u u 都染黑后黑节点数仍然相同。且因为又把 g g g 染为了红色，所以不会对 g g g 往上的节点的黑高产生影响。
不过这时节点 g g g 与 g g g 的父亲又有可能是连续的红节点，因此我们递归对 g g g 进行双红修正。
请添加图片描述

if(x->hasUncle() && x->uncle()->color == RED) {
	// Case 4: Both parent and uncle are RED
	//   Paint parent and uncle to BLACK;
	//   Paint grandparent to RED;
	//   Maintain grandparent recursively.
	//        [G]             <G>
	//        / \             / \
	//      <P> <U>  ====>  [P] [U]
	//      /               /
	//    <X>             <X>
	p->color = BLACK;			//parent -> black
	x->uncle()->color = BLACK;	//uncle  -> black
	p->father->color = RED;		//grandparent -> red
	SolveDoubleRed(p->father);
	return;
}

Case 5

叔节点为黑色，且当前节点 x x x 与父节点 p p p 的方向相反（即一个为左子节点，一个为右子节点）。
这种情况无法直接维护，我们把节点 x x x 旋转上来，然后就转化为了Case 6。
在这里插入图片描述
把 x x x 转上来后， x x x 与 p p p 的方向就一致了，这时 p p p 成为了 x x x 的父节点，于是我们需要处理的节点变成了 p p p。
请添加图片描述

// Case 5 & 6: parent is RED, uncle is BLACK(or NULL)
if(x->direction() != p->direction()) {
	// Case 5: Current node is the opposite direction as parent
	//   Step 1. Rotate x to parent's position.
	//   Step 2. Goto Case 6.
	//      [G]                 [G]
	//      / \    rotate(X)    / \
	//    <P> [U]  ========>  <X> [U]
	//      \                 /
	//      <X>             <P>
	rotate(x);
	x = p;			//Now P is the child of double red.
	p = x->father;	//reset p to x's father
}

Case 6

叔节点为黑色，且当前节点 x x x 与父节点 p p p 的方向相同（即同为左子节点或右子节点）。
由于父节点 p p p 是红色，所以祖父节点 g g g 一定是黑色。这种情况下，我们先向上转一次 p p p，再把 p p p 染黑， g g g 染红。
在这里插入图片描述
这里可以证明，这样操作后，树的黑高是不变的。我们假设最左边的图中 u u u 的黑高是1（即两个子节点均为 NIL），那么 g g g 的黑高是2，则由于黑高相同的性质， p p p 和 x x x（图中的N）黑高也为2.
在旋转+重新染色后， x x x 和 u u u 的子树结构和颜色没有变化，因此 x x x 的黑高仍为2， u u u 的黑高仍为1. 那么 g g g 的黑高为2， p p p 的黑高为2，与开始时 g g g 的黑高一致。
在这里插入图片描述
请添加图片描述

	// Case 6: Current node is the same direction as parent
	//   Step 1. Rotate parent to grandparent's position
	//   Step 2. Paint parent (before rotate) to BLACK;
	//           Paint grandparent (before rotate) to RED.
	//        [G]                 <P>               [P]
	//        / \    rotate(P)    / \    repaint    / \
	//      <P> [U]  ========>  <X> [G]  ======>  <X> <G>
	//      /                         \                 \
	//    <X>                         [U]               [U]
	rotate(p);				//rotate x's parent
	p->color = BLACK;
	x->sibling()->color = RED;	//repaint

删除操作

这个，不需要了！ ——长崎素世

二叉查找树

我们先考虑单纯的二叉搜索树怎么删除一个节点。
根据要删除的节点的子节点数，可以分为三种情况：0个子节点（即叶节点），1个子节点（一条链的正中间），以及2个子节点（内部节点）。

删除叶节点是最简单的，直接把这个节点去掉就行了。
如果是1个子节点的情况，就与链表的删除比较类似，我们用这个子节点来代替原来被删除的节点。
2个子节点的情况，我们找到删除节点的后继节点，也就是右子树中权值最小的节点。找后继节点的方法是从右子节点开始一直往左走，直到没有左子节点为止。
（后继节点一定没有左子节点，也就是说，它只有0或1个子节点）
由于后继节点是原来右子树中最小的节点，所以把它原来的权值放到被删除节点的位置，仍然满足左子树 < 根 < 右子树的性质。
因此，我们交换删除节点和后继节点的权值，然后把后继节点删除，这就转化成了对有0或1个子节点的节点进行删除的情况。

红黑树

考虑删除有0或1个子节点的节点的情况。（有2个子节点的情况是可以转化成这两种情况的，所以不用讨论）
删除有1个子节点的节点时，是用它唯一的子节点代替本身。删除叶节点（0个子节点）时，可以看作用一个 NIL 节点代替它本身。
我们再考虑红黑树关键的两条性质：不能出现连续双红节点，以及黑高相同。
假如我们删除的是红节点，那么它的替代节点一定是黑节点，所以删除它既不会使树中出现双红节点，也不会影响黑高相同的性质。
但是如果删除的是黑节点，那么会使经过这个节点的路径的黑高-1，而且如果父节点、子节点都是红色，就会出现连续的双红了。
这里双红是很容易处理的，我们的重点在于处理黑高（“双黑”）。如果我们可以简单通过重新染色解决黑高不同的问题，那就简单处理就好了。但是有的时候这样行不通，我们就需要进行双黑修正。
具体地说，我们需要调整树的结构和颜色，把目标黑色节点放在一个比兄弟节点黑高多1的位置，再把目标节点删掉，这样黑高就相同了。

template<typename T>
bool RedBlackTree<T>::remove(T v, node* x) {
	if(x == NULL)	return false;
	if(v != x->val) {
		int branch = (v > x->val);	//v > x->val : branch = 1, goto right child
		if(x->ch[branch] != NULL) {
			//the structure of the subtree may change
			//node x may have new children after remove
			//so first update the size of subtree
			//if fail to remove then rollback size changes
			x->siz--;
			bool result = remove(v, x->ch[branch]);
			if(result == false) {
				x->siz++;
			}
			return result;
		}
		return false;
	}
	//Remove x from the tree
	//......
}

Case 0

删除节点为根，且整棵树只有这一个节点，直接删就完了。

Case 1

删除节点 x x x 有2个子节点，则交换当前节点与后继节点的权值，然后问题转化为删除后继节点。

if(x->left != NULL && x->right != NULL) {
	// Case 1: If the node is strictly internal
	//   Step 1. Find the successor S with the smallest key
	//           and its parent P on the right subtree.
	//   Step 2. Swap the data (key and value) of S and X,
	//           S is the node that will be deleted in place of X.
	//   Step 3. X = S, goto Case 2, 3
	//     |                    |
	//     X                    S
	//    / \                  / \
	//   L  ..   swap(X, S)   L  ..
	//       |   =========>       |
	//       P                    P
	//      / \                  / \
	//     S  ..                X  ..
	x->siz--;
	//Step 1
	node* rt = x->right;
	rt->siz--;
	while(rt->left) {
		rt = rt->left;
		rt->siz--;
	}
	//Step 2, 3
	node* succ = rt;
	swap(x->val, succ->val);
	x = succ;
}

Case 2

删除叶子节点。如果是红叶子就直接删掉，如果是黑叶子，就要重新维护黑高。
在维护操作中，由于我们只是把目标节点放到了比兄弟节点黑高多1的地方，而没有改变目标节点的子树结构和数据，所以我们可以先对其维护，让它的黑高比兄弟多1，再把它删除。

if(x->left == NULL && x->right == NULL) {
	// Case 2: Current node is a leaf
	//   Step 1. Put X to a position where its black height
	//           is greater than its sibling by 1.(if X is black)
	//   Step 2. remove X

	// The maintain operation won't change the node itself,
	//  so we can perform maintain operation before unlink the node.
	x->siz = 0;
	if(x->color == BLACK) {
		SolveDoubleBlack(x);	//Step 1
	}
	x->father->ch[x->direction()] = NULL;
	x->father->pushup();
	return true;
}

Case 3

目标节点刚好有一个子节点，我们用它唯一的子节点来代替它本身。
这时唯一的孩子只可能是红色，否则一边为黑，一边为NIL，两边的黑高是不同的。
因此，我们直接把替代节点染成黑色，就可以解决黑高-1的问题。

	// Case 3: Current node has a single left or right child
	//   Step 1. Paint its child to black(the child must be red).
	//   Step 2. Remove X
	node* replacement = (x->left != NULL ? x->left : x->right);
	if(x->color == BLACK) {
		replacement->color = BLACK;
	}
	if(x == root) {
		root = replacement;
		replacement->father = NULL;
	} else {
		node* parent = x->father;
		parent->ch[x->direction()] = replacement;
		replacement->father = parent;
		parent->pushup();
	}

OI Wiki上这一段代码和最后给出的完整版里不一样，最后的完整版还写了唯一孩子是黑色时维护孩子的 if 分支，这个可能是出于工程上代码完整性的考虑（？

双黑修正

致命的黑影啊，翩翩起舞吧！ ——Ave Mujica《黑色生日》

双黑维护，其实就是目标节点的黑高因为某些情况（如删除了一个黑节点）减少了1（或者即将要减少1），导致它比兄弟节点的黑高少1.
我们需要把它放在一个比兄弟黑高多1的位置，从而抵消黑高-1的影响。

Case 1

兄弟节点 s s s 为红色，则父节点 p p p 和两个侄节点 c c c 和 d d d 必为黑色。这种情况与双红修正的Case 5类似，无法直接使其满足所有性质，我们将其转化为其他Case进行处理。
Step 1. 往上转一次兄弟节点 s s s
Step 2. 把 s s s 染黑， p p p 染红，并转到其他Case
在这里插入图片描述
假设原来黑高为上面最左边蓝色数字标注的值，则这样操作后目标节点与新的兄弟节点 c c c 黑高相同。由于我们需要目标节点比兄弟黑高多1，所以我们转到其它Case，继续对该节点进行处理。
请添加图片描述

if(sibling->color == RED) {
	// Case 1: Sibling is RED, parent and nephews must be BLACK
	//   Step 1. Rotate X's sibling to P's position
	//   Step 2. Paint S to BLACK, P to RED
	//   Step 3. Goto Case 2, 3, 4, 5
	//      [P]                   <S>               [S]
	//      / \     rotate(S)     / \    repaint    / \
	//    [X] <S>  ==========>  [P] [D]  ======>  <P> [D]
	//        / \               / \               / \
	//      [C] [D]           [X] [C]           [X] [C]
	node* parent = x->father;
	//Step 1
	rotate(sibling);
	//Step 2
	sibling->color = BLACK;
	parent->color = RED;
	sibling = x->sibling();		//update sibling after rotation
}

Case 2

兄弟节点 s s s 和侄节点 c c c, d d d 均为黑色，且父节点 p p p 为红色。
此时将父节点 p p p 染红，将 s s s 染黑即可。
在这里插入图片描述

假设原来的黑高如左图所示，那么重新染色之后，再删除目标节点，则其替代节点的黑高由2变为1。删除后， p p p 的黑高为2。
假如 p p p 有一个父节点，则原来 p p p 的父节点黑高为3（因为原来 p p p 是红色），调整后父节点黑高也为3（ p p p 为黑，父节点黑高为 p p p 的黑高+1）.
请添加图片描述

bool closeBlack = (closeNephew == NULL) || (closeNephew->color == BLACK);
bool distantBlack = (distantNephew == NULL) || (distantNephew->color == BLACK);
if(closeBlack && distantBlack) {
	if(x->father->color == RED) {
		// Case 2: Sibling and nephews are BLACK, parent is RED
		//   Swap the color of P and S
		//      <P>             [P]
		//      / \             / \
		//    [X] [S]  ====>  [X] <S>
		//        / \             / \
		//      [C] [D]         [C] [D]
		sibling->color = RED;
		x->father->color = BLACK;
	}
	//Other cases
}

Case 3

兄弟节点 s s s 和侄节点 c c c, d d d 均为黑色，且父节点 p p p 也为黑色。
我们先把兄弟节点 s s s 染红，这样删除目标节点后，父节点 p p p 的所有黑高就相同了。但是这样 p p p 节点的黑高会比兄弟节点少1，所以我们递归维护 p p p。
在这里插入图片描述
重新染色后黑高的变化如上图所示。
请添加图片描述

//Assume that both nephews are black
if(x->father->color == BLACK) {
	// Case 3: Sibling, parent and nephews are all black
	//   Step 1. Paint S to RED
	//   Step 2. Recursively maintain P
	//      [P]             [P]
	//      / \             / \
	//    [X] [S]  ====>  [X] <S>
	//        / \             / \
	//      [C] [D]         [C] [D]
	sibling->color = RED;
	SolveDoubleBlack(x->father);
	return;
}

Case 4

我们把与目标节点同向（即同为左孩子/同为右孩子）的侄节点称为close nephew，用 c c c 表示。反向的侄节点称为distant nephew，用 d d d 表示。在图中可以看出，close nephew就是离目标节点（图中的N）比较近的侄节点，distant nephew就是离得比较远的侄节点。

Case 4为，兄弟节点 s s s 为黑色， c c c 为红， d d d 为黑。父节点 p p p 红黑均可。
这种情况同样无法直接维护，因此将其转变为 Case 5 的状态，利用后续 Case 5 的维护过程进行修正。
Step 1. 向上旋转 c c c
Step 2. 将 c c c 染黑， s s s 染红。
Step 3. 转到 Case 5.
在这里插入图片描述
黑高变化如上图所示。
请添加图片描述
注：上面这个gif处理的是0003节点的双黑问题。

bool closeRed = (closeNephew != NULL) && (closeNephew->color == RED);
if(closeRed && distantBlack) {
	// Case 4: Sibling is BLACK, close nephew is RED,
	//         distant nephew is BLACK
	//   Step 1. Rotate close nephew to sibling's position
	//   Step 2. Swap the color of close nephew and sibling
	//   Step 3. Goto case 5
	//                            {P}                {P}
	//      {P}                   / \                / \
	//      / \     rotate(C)   [X] <C>   repaint  [X] [C]
	//    [X] [S]  ==========>        \   ======>        \
	//        / \                     [S]                <S>
	//      <C> [D]                     \                  \
	//                                  [D]                [D]
	//Step 1
	rotate(closeNephew);
	//Step 2
	closeNephew->color = BLACK;
	sibling->color = RED;
	// Update sibling and nephews after rotation
	sibling = x->sibling();
	xdir = x->direction();
	closeNephew = sibling->ch[xdir];
	distantNephew = sibling->ch[xdir ^ 1];
}

Case 5

兄弟节点 s s s 为黑色，distant nephew节点 d d d 为红色，close nephew节点 c c c 为任意颜色，父节点 p p p 为任意颜色。

Step 1. 向上旋转兄弟节点 s s s
Step 2. 把 s s s 染成 p p p 的颜色，把 p p p 染黑（即交换两者颜色）。
Step 3. 将 d d d 染黑。

在这里插入图片描述
黑高变化如上图所示。这样操作后删除目标节点，目标节点黑高由2变为1，整棵树满足红黑树性质。
请添加图片描述

	// Case 5: Sibling is BLACK, close nephew is unknown,
	//         distant nephew is RED
	//      {P}                   [S]                 {S}
	//      / \     rotate(S)     / \    repaint     /  \
	//    [X] [S]  ==========>  {P} <D>  =======>  [P]  [D]
	//        / \               / \                / \
	//      {C} <D>           [X] {C}            [X] {C}
	//   Step 1. Rotate sibling to P's position
	//   Step 2. Swap the color of parent and sibling.
	//			 Paint distant nephew to BLACK if it is not null.
	//Step 1
	rotate(sibling);
	//Step 2
	sibling->color = x->father->color;
	x->father->color = BLACK;
	if(distantNephew != NULL) {
		distantNephew->color = BLACK;
	}

其他查询操作

其他查询操作就和二叉查找树完全一致了。下面几个查询操作对应洛谷P3369中的操作3-6.

查询排名

template<typename T>
int RedBlackTree<T>::get_rank(T v, node* x) {
	if(x == NULL)	return 0;
	if(v <= x->val)	return get_rank(v, x->left);
	int lsiz = (x->left != NULL ? x->left->siz : 0);
	return lsiz + 1 + get_rank(v, x->right);
}
template<typename T>
int RedBlackTree<T>::get_rank(T v) {
	return get_rank(v, root);
}

查询第k大

template<typename T>
T RedBlackTree<T>::kth(int k, node* x) {
	if(!(x->left)) {
		if(k == 1)	return x->val;
		return kth(k - 1, x->right);
	}
	if(k <= x->left->siz)	return kth(k, x->left);
	if(k == x->left->siz + 1)	return x->val;
	return kth(k - x->left->siz - 1, x->right);
}
template<typename T>
T RedBlackTree<T>::kth(int k) {
	return kth(k, root);
}

寻找前驱

template<typename T>
T RedBlackTree<T>::get_prev(T v) {
	node *x = root;
	T ans;
	while(x != NULL) {
		if(x->val < v) {
			ans = x->val;
			x = x->right;
		} else {
			x = x->left;
		}
	}
	return ans;
}

寻找后继

template<typename T>
T RedBlackTree<T>::get_succ(T v) {
	node *x = root;
	T ans;
	while(x != NULL) {
		if(x->val > v) {
			ans = x->val;
			x = x->left;
		} else {
			x = x->right;
		}
	}
	return ans;
}

最终代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

template<typename T>
class RedBlackTree {
	private:
		struct node;
		node* root;
		void SolveDoubleRed(node*);
		void SolveDoubleBlack(node*);
		node* Find(T);
		void connect(node*, node*, int);
		void rotate(node*);
		void checkNodeSize(node*);
		
		bool remove(T, node*);
		int get_rank(T, node*);
		T kth(int, node*);
	public:
		RedBlackTree() : root(NULL) {}
		int size();
		void insert(T);
		bool remove(T);
		int get_rank(T);
		T kth(int);
		T get_prev(T);
		T get_succ(T);

		void previs(node*);
		void invis(node*);
		void postvis(node*);
		void print();
		void checkNodeSize();
};

#define RED 1
#define BLACK 0
#define left ch[0]
#define right ch[1]
template<typename T>
struct RedBlackTree<T>::node {
	/*
	 * <X>	X is red.
	 * [X]	X is black.
	 * {X}	X is unknown(red/black).
	 */
	T val;
	bool color;		//1 is red, 0 is black 
	node *father, *ch[2];
	int siz;
	node(T v = T(), bool col = true, node* f = NULL,
	     node* l = NULL, node* r = NULL , int s = 1)
		: val(v), color(col), father(f), siz(s) {
		left = l;
		right = r;
	}
	int direction() {
		if(father == NULL)	return 0;
		return father->right == this;
	}
	node* sibling() {
		if(father == NULL)	return NULL;
		return father->ch[direction() ^ 1];
	}
	bool hasSibling() {
		return sibling() != NULL;
	}
	node* uncle() {
		if(father == NULL)	return NULL;
		return father->sibling();
	}
	bool hasUncle() {
		return uncle() != NULL;
	}
	void pushup() {
		siz = (left?left->siz:0) + (right?right->siz:0) + 1;
	}
	void print() {
		cout << "key = " << val << ", color = " << (color ? "Red" : "Black") << endl;
	}
};

template<typename T>
int RedBlackTree<T>::size() {
	return root->siz;
}

template<typename T>
void RedBlackTree<T>::connect(node *x, node *fa, int k) {
	if(x != NULL)	x->father = fa;
	if(fa != NULL) {
		fa->ch[k] = x;
	} else {
		root = x;
	}
}

template<typename T>
void RedBlackTree<T>::rotate(node *x) {
	//rotate x to its parent's position
	node* y = x->father;
	node* z = y->father;
	int yson = x->direction();
	if(z == NULL) {
		root = x;
		x->father = NULL;
	} else {
		int zson = y->direction();
		connect(x, z, zson);
	}
	connect(x->ch[yson^1], y, yson);
	connect(y, x, yson^1);
	y->pushup();
	x->pushup();
}

template<typename T>
void RedBlackTree<T>::insert(T v) {
	node *x = root, *fa = NULL;
	while(x != NULL) {
		x->siz++;
		fa = x;
		if(v < x->val) {
			x = x->left;
		} else {
			x = x->right;
		}
	}
	x = new node(v, RED, fa);	//create a new node
	if(fa == NULL) {
		root = x;
	} else if(v < fa->val) {
		fa->left = x;
	} else {
		fa->right = x;
	}
	SolveDoubleRed(x);
}
template<typename T>
void RedBlackTree<T>::SolveDoubleRed(node* x) {
	if(x == root || x->father->color == BLACK) {
		return;
	}
	node* p = x->father;
	if(p == root) {
		// Case 3: Parent is root and is RED
		//   Paint parent to BLACK.
		//    <P>         [P]
		//     |   ====>   |
		//    <X>         <X>
		p->color = BLACK;
		return;
	}
	if(x->hasUncle() && x->uncle()->color == RED) {
		// Case 4: Both parent and uncle are RED
		//   Paint parent and uncle to BLACK;
		//   Paint grandparent to RED;
		//   Maintain grandparent recursively.
		//        [G]             <G>
		//        / \             / \
		//      <P> <U>  ====>  [P] [U]
		//      /               /
		//    <X>             <X>
		p->color = BLACK;			//parent -> black
		x->uncle()->color = BLACK;	//uncle  -> black
		p->father->color = RED;		//grandparent -> red
		SolveDoubleRed(p->father);
		return;
	}
	// Case 5 & 6: parent is RED, uncle is BLACK(or NULL)
	if(x->direction() != p->direction()) {
		// Case 5: Current node is the opposite direction as parent
		//   Step 1. Rotate x to parent's position.
		//   Step 2. Goto Case 6.
		//      [G]                 [G]
		//      / \    rotate(X)    / \
		//    <P> [U]  ========>  <X> [U]
		//      \                 /
		//      <X>             <P>
		rotate(x);
		x = p;			//Now P is the child of double red.
		p = x->father;	//reset p to x's father
	}
	// Case 6: Current node is the same direction as parent
	//   Step 1. Rotate parent to grandparent's position
	//   Step 2. Paint parent (before rotate) to BLACK;
	//           Paint grandparent (before rotate) to RED.
	//        [G]                 <P>               [P]
	//        / \    rotate(P)    / \    repaint    / \
	//      <P> [U]  ========>  <X> [G]  ======>  <X> <G>
	//      /                         \                 \
	//    <X>                         [U]               [U]
	rotate(p);				//rotate x's parent
	p->color = BLACK;
	x->sibling()->color = RED;	//repaint
}

#define col(a) (a == RED ? "Red" : "Black")

template<typename T>
void RedBlackTree<T>::previs(node* x) {
	if(x == NULL)	return;
	printf("%d %s %d\n", x->val, col(x->color), x->siz);
	previs(x->left);
	previs(x->right);
}
template<typename T>
void RedBlackTree<T>::invis(node* x) {
	if(x == NULL)	return;
	invis(x->left);
	printf("%d %s %d\n", x->val, col(x->color), x->siz);
	invis(x->right);
}
template<typename T>
void RedBlackTree<T>::postvis(node* x) {
	if(x == NULL)	return;
	postvis(x->left);
	postvis(x->right);
	printf("%d %s %d\n", x->val, col(x->color), x->siz);
}
template<typename T>
void RedBlackTree<T>::print() {
	printf("------pre-vis------\n");
	previs(root);
	printf("------in-vis------\n");
	invis(root);
	printf("------post-vis------\n");
	postvis(root);
}

template<typename T>
void RedBlackTree<T>::checkNodeSize(node* x) {
	int before = x->siz;
	if(x->left)	checkNodeSize(x->left);
	if(x->right)	checkNodeSize(x->right);
	x->pushup();
	if(x->siz != before) {
		printf("node of key %d : size changed from %d to %d\n", x->val, before, x->siz);
	}
}

template<typename T>
void RedBlackTree<T>::checkNodeSize() {
	checkNodeSize(root);
}

template<typename T>
bool RedBlackTree<T>::remove(T v) {
	return remove(v, root);
}

template<typename T>
bool RedBlackTree<T>::remove(T v, node* x) {
	if(x == NULL)	return false;
	if(v != x->val) {
		int branch = (v > x->val);	//v > x->val : branch = 1, goto right child
		if(x->ch[branch] != NULL) {
			//the structure of the subtree may change
			//node x may have new children after remove
			//so first update the size of subtree
			//if fail to remove then rollback size changes
			x->siz--;
			bool result = remove(v, x->ch[branch]);
			if(result == false) {
				x->siz++;
			}
			return result;
		}
		return false;
	}
	if(x == root && x->siz == 1) {
		root = NULL;
		return true;
	}
	if(x->left != NULL && x->right != NULL) {
		// Case 1: If the node is strictly internal
		//   Step 1. Find the successor S with the smallest key
		//           and its parent P on the right subtree.
		//   Step 2. Swap the data (key and value) of S and X,
		//           S is the node that will be deleted in place of X.
		//   Step 3. X = S, goto Case 2, 3
		//     |                    |
		//     X                    S
		//    / \                  / \
		//   L  ..   swap(X, S)   L  ..
		//       |   =========>       |
		//       P                    P
		//      / \                  / \
		//     S  ..                X  ..
		x->siz--;
		//Step 1
		node* rt = x->right;
		rt->siz--;
		while(rt->left) {
			rt = rt->left;
			rt->siz--;
		}
		//Step 2, 3
		node* succ = rt;
		swap(x->val, succ->val);
		x = succ;
	}
	if(x->left == NULL && x->right == NULL) {
		// Case 2: Current node is a leaf
		//   Step 1. Put X to a position where its black height
		//           is greater than its sibling by 1.(if X is black)
		//   Step 2. remove X

		// The maintain operation won't change the node itself,
		//  so we can perform maintain operation before unlink the node.
		x->siz = 0;
		if(x->color == BLACK) {
			SolveDoubleBlack(x);	//Step 1
		}
		x->father->ch[x->direction()] = NULL;
		x->father->pushup();
		return true;
	}
	// Case 3: Current node has a single left or right child
	//   Step 1. Paint its child to black(the child must be red).
	//   Step 2. Remove X
	node* replacement = (x->left != NULL ? x->left : x->right);
	if(x->color == BLACK) {
		replacement->color = BLACK;
	}
	if(x == root) {
		root = replacement;
		replacement->father = NULL;
	} else {
		node* parent = x->father;
		parent->ch[x->direction()] = replacement;
		replacement->father = parent;
		parent->pushup();
	}
	return true;
}

template<typename T>
void RedBlackTree<T>::SolveDoubleBlack(node* x) {
	if(x == root)	return;
	node* sibling = x->sibling();
	if(sibling->color == RED) {
		// Case 1: Sibling is RED, parent and nephews must be BLACK
		//   Step 1. Rotate X's sibling to P's position
		//   Step 2. Paint S to BLACK, P to RED
		//   Step 3. Goto Case 2, 3, 4, 5
		//      [P]                   <S>               [S]
		//      / \     rotate(S)     / \    repaint    / \
		//    [X] <S>  ==========>  [P] [D]  ======>  <P> [D]
		//        / \               / \               / \
		//      [C] [D]           [X] [C]           [X] [C]
		node* parent = x->father;
		//Step 1
		rotate(sibling);
		//Step 2
		sibling->color = BLACK;
		parent->color = RED;
		sibling = x->sibling();		//update sibling after rotation
	}
	//close nephew: sibling's child with the same direction as x
	int xdir = x->direction();		//the direction of x
	node* closeNephew = sibling->ch[xdir];
	node* distantNephew = sibling->ch[xdir ^ 1];
	//NIL nodes are always black
	bool closeBlack = (closeNephew == NULL) || (closeNephew->color == BLACK);
	bool distantBlack = (distantNephew == NULL) || (distantNephew->color == BLACK);
	if(closeBlack && distantBlack) {
		if(x->father->color == RED) {
			// Case 2: Sibling and nephews are BLACK, parent is RED
			//   Swap the color of P and S
			//      <P>             [P]
			//      / \             / \
			//    [X] [S]  ====>  [X] <S>
			//        / \             / \
			//      [C] [D]         [C] [D]
			sibling->color = RED;
			x->father->color = BLACK;
		} else {
			// Case 3: Sibling, parent and nephews are all black
			//   Step 1. Paint S to RED
			//   Step 2. Recursively maintain P
			//      [P]             [P]
			//      / \             / \
			//    [X] [S]  ====>  [X] <S>
			//        / \             / \
			//      [C] [D]         [C] [D]
			sibling->color = RED;
			SolveDoubleBlack(x->father);
		}
	} else {
		bool closeRed = (closeNephew != NULL) && (closeNephew->color == RED);
		if(closeRed && distantBlack) {
			// Case 4: Sibling is BLACK, close nephew is RED,
			//         distant nephew is BLACK
			//   Step 1. Rotate close nephew to sibling's position
			//   Step 2. Swap the color of close nephew and sibling
			//   Step 3. Goto case 5
			//                            {P}                {P}
			//      {P}                   / \                / \
			//      / \     rotate(C)   [X] <C>   repaint  [X] [C]
			//    [X] [S]  ==========>        \   ======>        \
			//        / \                     [S]                <S>
			//      <C> [D]                     \                  \
			//                                  [D]                [D]
			//Step 1
			rotate(closeNephew);
			//Step 2
			closeNephew->color = BLACK;
			sibling->color = RED;
			// Update sibling and nephews after rotation
			sibling = x->sibling();
			xdir = x->direction();
			closeNephew = sibling->ch[xdir];
			distantNephew = sibling->ch[xdir ^ 1];
		}
		// Case 5: Sibling is BLACK, close nephew is unknown,
		//         distant nephew is RED
		//      {P}                   [S]                 {S}
		//      / \     rotate(S)     / \    repaint     /  \
		//    [X] [S]  ==========>  {P} <D>  =======>  [P]  [D]
		//        / \               / \                / \
		//      {C} <D>           [X] {C}            [X] {C}
		//   Step 1. Rotate sibling to P's position
		//   Step 2. Swap the color of parent and sibling.
		//			 Paint distant nephew to BLACK if it is not null.
		//Step 1
		rotate(sibling);
		//Step 2
		sibling->color = x->father->color;
		x->father->color = BLACK;
		if(distantNephew != NULL) {
			distantNephew->color = BLACK;
		}
	}
}

template<typename T>
T RedBlackTree<T>::kth(int k, node* x) {
	if(!(x->left)) {
		if(k == 1)	return x->val;
		return kth(k - 1, x->right);
	}
	if(k <= x->left->siz)	return kth(k, x->left);
	if(k == x->left->siz + 1)	return x->val;
	return kth(k - x->left->siz - 1, x->right);
}
template<typename T>
T RedBlackTree<T>::kth(int k) {
	return kth(k, root);
}

template<typename T>
T RedBlackTree<T>::get_prev(T v) {
	node *x = root;
	T ans;
	while(x != NULL) {
		if(x->val < v) {
			ans = x->val;
			x = x->right;
		} else {
			x = x->left;
		}
	}
	return ans;
}
template<typename T>
T RedBlackTree<T>::get_succ(T v) {
	node *x = root;
	T ans;
	while(x != NULL) {
		if(x->val > v) {
			ans = x->val;
			x = x->left;
		} else {
			x = x->right;
		}
	}
	return ans;
}

template<typename T>
int RedBlackTree<T>::get_rank(T v, node* x) {
	if(x == NULL)	return 0;
	if(v <= x->val)	return get_rank(v, x->left);
	int lsiz = (x->left != NULL ? x->left->siz : 0);
	return lsiz + 1 + get_rank(v, x->right);
}
template<typename T>
int RedBlackTree<T>::get_rank(T v) {
	return get_rank(v, root);
}
RedBlackTree<int> Tree;
int main() {
	int n;
	cin >> n;
	while(n--) {
		int op, x;
		cin >> op >> x;
		if(op == 1) {
			Tree.insert(x);
		} else if(op == 2) {
			Tree.remove(x);
		} else if(op == 3) {
			cout << Tree.get_rank(x) + 1 << endl;
		} else if(op == 4) {
			cout << Tree.kth(x) << endl;
		} else if(op == 5) {
			cout << Tree.get_prev(x) << endl;
		} else {
			cout << Tree.get_succ(x) << endl;
		}
//		Tree.checkNodeSize();
	}
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

golang和Java的简单介绍和对比

golang和Java的简单介绍和对比

一、golang 1、Golang简介 Golang&#xff0c;也称为Go&#xff0c;是由Google公司在2009年推出的开源编程语言&#xff0c;由罗伯特格瑞史莫(Rob Pike)、肯汤普逊(Ken Thompson)、罗勃派克(Robert Griesemer)等人设计。Go语言的目标是在保持简单高效的编程模型的同时&#xf…
阅读更多...
Springboot中的三层架构

Springboot中的三层架构

我们在进行前后端交互的时候&#xff0c;会分为数据访问&#xff0c;业务逻辑&#xff0c;接受请求并响应数据三个操作&#xff0c;这三部分其实是可以拆分的&#xff0c;让他们解耦&#xff0c;否则代码复用性差并且不易维护&#xff0c;所以诞生了三层架构——1.Dao(数据访问…
阅读更多...
主干网络篇 | YOLOv8改进之用RCS-OSA替换C2f（来源于RCS-YOLO）

主干网络篇 | YOLOv8改进之用RCS-OSA替换C2f（来源于RCS-YOLO）

前言：Hello大家好，我是小哥谈。RCS-YOLO是一种目标检测算法，它是基于YOLOv3算法的改进版本。通过查看RCS-YOLO的整体架构可知，其中包括RCS-OSA模块。RCS-OSA模块在模型中用于堆叠RCS模块，以确保特征的复用并加强不同层之间的信息流动。本文就给大家详细介绍如何将RCS-YOLO…
阅读更多...
关系（二）利用python绘制热图

关系（二）利用python绘制热图

关系&#xff08;二&#xff09;利用python绘制热图 热图 &#xff08;Heatmap&#xff09;简介 热图适用于显示多个变量之间的差异&#xff0c;通过颜色判断彼此之间是否存在相关性。 快速绘制 基于seaborn import seaborn as sns import pandas as pd import numpy as np i…
阅读更多...
干货教程【AI篇】| AI大模型文字生成视频环境部署小白级教程

干货教程【AI篇】| AI大模型文字生成视频环境部署小白级教程

只需要一个主题、一个词语&#xff0c;或者一段描述&#xff0c;就可以生成一个完整的短视频的工具来啦&#xff01; 在文章下方公众号中回复关键词【aivd】即可获取完整代码和配套软件 工具获取 ps&#xff1a;本文不涉及任何代码开发工作&#xff0c;仅仅作为软件推荐。 如…
阅读更多...
OpenHarmony实战开发-分布式关系型数据库

OpenHarmony实战开发-分布式关系型数据库

介绍 本示例使用ohos.data.relationalStore 接口和ohos.distributedDeviceManager 接口展示了在eTS中分布式关系型数据库的使用&#xff0c;在增、删、改、查的基本操作外&#xff0c;还包括分布式数据库的数据同步同能。 效果预览 使用说明: 1.启动应用后点击“”按钮可以添…
阅读更多...
网络以太网之(2)VLAN协议

网络以太网之(2)VLAN协议

网络以太网之(1)VLAN协议 Author: Once Day Date: 2024年4月1日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day…
阅读更多...
主流公链 - Fantom

主流公链 - Fantom

Fantom&#xff1a;高性能的区块链协议 Fantom是一种开创性的区块链协议&#xff0c;旨在革新去中心化应用和数字金融领域 技术特点 共识机制 Lachesis协议&#xff1a;Fantom使用了Lachesis协议作为其共识算法。Lachesis是一种 异步拜占庭容错&#xff08;ABFT&#xff09;共…
阅读更多...
2023数模国赛C 题 蔬菜类商品的自动定价与补货决策-完整版创新多思路详解（含代码）

2023数模国赛C 题 蔬菜类商品的自动定价与补货决策-完整版创新多思路详解（含代码）

题目简评&#xff1a;看下来C题是三道题目里简单一些的&#xff0c;考察的点比较综合&#xff0c;偏数据分析。涉及预测模型和运筹优化(线性规划)&#xff0c;还设了一问开放型问题&#xff0c;适合新手入门&#xff0c;发挥空间大。 题目分析与思路&#xff1a; 背景&#x…
阅读更多...
文心一言 vs GPT-4 ----全面横向比较

文心一言 vs GPT-4 ----全面横向比较

文心一言 (Wenxin Yiyan) 和 GPT-4 是两个强大的人工智能语言模型&#xff0c;它们在处理自然语言方面表现出了出色的能力。但它们有一些关键的区别和优势。以下是它们的横向比较&#xff1a; 公司和平台&#xff1a; * 文心一言是由百度开发的中文语言模型&#xff0c;专门为…
阅读更多...
【JavaScript】函数 ③ ( 形参 与 实参 匹配问题 | 实参个数 = 形参个数 | 实参个数 ＞ 形参个数 | 实参个数 ＜ 形参个数 )

【JavaScript】函数 ③ ( 形参 与 实参 匹配问题 | 实参个数 = 形参个数 | 实参个数 ＞ 形参个数 | 实参个数 ＜ 形参个数 )

文章目录 一、JavaScript 函数 形参 与 实参 匹配问题1、函数形参与实参不匹配问题2、形参与实参个数匹配3、实参个数 > 形参个数4、实参个数 < 形参个数5、完整代码示例 一、JavaScript 函数 形参 与 实参 匹配问题 1、函数形参与实参不匹配问题 在 其它语言 中 , 如 Ja…
阅读更多...
Java 设计模式系列：备忘录模式

Java 设计模式系列：备忘录模式

简介 备忘录模式是一种软件设计模式&#xff0c;用于在不破坏封闭的前提下捕获一个对象的内部状态&#xff0c;并在该对象之外保存这个状态。这样以后就可将该对象恢复到原先保存的状态。 备忘录模式提供了一种状态恢复的实现机制&#xff0c;使得用户可以方便地回到一个特定…
阅读更多...
【VTKExamples::Meshes】第三期 ClipClosedSurface

【VTKExamples::Meshes】第三期 ClipClosedSurface

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ：870202403 公众号：VTK忠粉 前言 本文分享VTK样例ClipClosedSurface，并解析接口vtkClipClosedSurface，希望对各位小伙伴有所帮助！ 感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！ 你的点赞就是我的动力(…
阅读更多...
HTML标签之表格标签和表格案例

HTML标签之表格标签和表格案例

表格标签的使用案例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevic…
阅读更多...
yolov7代码 | model.named_models

yolov7代码 | model.named_models

文章目录 前言1. print(model)2. print(model.named_models)2.1 print(name)2.2 print(module)2.3 print(f"{name}:: {module}") 3. hasattr(module, weight) 前言 了解model.named_models&#xff0c;为剪枝做准备。 剪枝有一些层如果你不想剪掉&#xff0c;那就用…
阅读更多...
IP代理池赋能Python网络爬虫

IP代理池赋能Python网络爬虫

文章目录 什么是IP代理池代理服务器IP代理池的作用IP代理池的构建IP代理池的管理 相关案例IP代理在爬虫中的运用IP代理在数据收集中的运用IP代理在反爬虫中的运用 结语 什么是IP代理池 IP代理池是一个存储了多个可用代理IP地址的资源池&#xff0c;用于在网络爬虫、数据采集、…
阅读更多...
PS从入门到精通视频各类教程整理全集，包含素材、作业等（6）复发

PS从入门到精通视频各类教程整理全集，包含素材、作业等（6）复发

PS从入门到精通视频各类教程整理全集&#xff0c;包含素材、作业等 最新PS以及插件合集&#xff0c;可在我以往文章中找到 由于阿里云盘有分享次受限制和文件大小限制&#xff0c;今天先分享到这里&#xff0c;后续持续更新 橘子老师章节9-17图像的调色 等文件 https://www.a…
阅读更多...
网站备案进度

网站备案进度

1.网站开通后&#xff0c;请在网站首页底部中间位置放置您的ICP备案号并链接至"https://beian.miit.gov.cn"。 并在开通之日起30日内登录全国互联网安全管理平台提交公安联网备案申请。获取《公安备案信息填写指南》&#xff0c;或者通过“公安备案助手”协助您完成申…
阅读更多...
文件操作的详序

文件操作的详序

1.为什么使用文件&#xff1f; 如果没有文件&#xff0c;我们写的程序的数据是存储在电脑的内存中&#xff0c;如果程序退出&#xff0c;内存回收&#xff0c;数据就丢失了&#xff0c;等再次运行程序&#xff0c;是看不到程序的数据的&#xff0c;如果将数据进行持久化的保存…
阅读更多...
【六 （2）机器学习-机器学习建模步骤/kaggle房价回归实战】

【六 （2）机器学习-机器学习建模步骤/kaggle房价回归实战】

一、确定问题和目标&#xff1a; 1、业务需求分析&#xff1a; 与业务团队或相关利益方进行深入沟通&#xff0c;了解他们的需求和期望。 分析业务流程&#xff0c;找出可能的瓶颈、机会或挑战。 思考机器学习如何帮助解决这些问题或实现业务目标。 2、问题定义&#xff1a;…
阅读更多...
最新文章

Copyright @ 2022~2023