树：红黑树 - 版本历史

Eijux：/* 定义和性质 */

2021-04-22T08:23:53Z

定义和性质

←上一版本		2021年4月22日 (四) 16:23的版本
第19行：		第19行：
	# 根节点是黑色。		# 根节点是黑色。
	# 每个叶子节点（NIL）是黑色。		# 每个叶子节点（NIL）是黑色。
			#* 【图中未必画出，但叶子节点都是“NULL”指针。】
	# '''每个红色结点的两个子结点一定都是黑色'''。【？】		# '''每个红色结点的两个子结点一定都是黑色'''。【？】
	#* 从每个叶子到根的所有路径上不能有两个连续的红色节点。		#* 从每个叶子到根的所有路径上不能有两个连续的红色节点。

Eijux：/* 情景2.2：替换结点是其父结点的右子结点【类似“情景2.1”】 */

2021-04-21T17:35:37Z

情景2.2：替换结点是其父结点的右子结点【类似“情景2.1”】

←上一版本		2021年4月22日 (四) 01:35的版本
第170行：		第170行：
	##: [[File:红黑树：删除情景2.1.2.3.png\|600px]]		##: [[File:红黑树：删除情景2.1.2.3.png\|600px]]

	===== 情景2.~~2：替换结点是其父结点的右子结点【类似“情景2~~.1”】 =====		===== 情景2.2：替换结点是黑结点，替换结点是其父结点的右子结点【类似“情景2.1”】 =====
	【同上“情景2.1”，只是方向不同，对应的旋转操作不同】		【同上“情景2.1”，只是方向不同，对应的旋转操作不同】
	# '''情景2.2.1'''：“'''替换结点的兄弟结点是红结点'''”，处理：		# '''情景2.2.1'''：“'''替换结点的兄弟结点是红结点'''”，处理：

Eijux：/* 情景2.1：替换结点是其父结点的左子结点 */

2021-04-21T17:35:23Z

情景2.1：替换结点是其父结点的左子结点

←上一版本		2021年4月22日 (四) 01:35的版本
第139行：		第139行：
	当替换结点是黑色时，就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡。		当替换结点是黑色时，就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡。

	===== 情景2.~~1：替换结点是其父结点的左子结点~~ =====		===== 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 =====
	分为两种情况：		分为两种情况：
	# '''情景2.1.1'''：“'''替换结点的兄弟结点是红结点'''”，处理：		# '''情景2.1.1'''：“'''替换结点的兄弟结点是红结点'''”，处理：

Eijux：/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

2021-04-21T17:34:42Z

情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点

←上一版本		2021年4月22日 (四) 01:34的版本
第91行：		第91行：
	#: [[File:红黑树：插入情景4.2.2.png\|600px]]		#: [[File:红黑树：插入情景4.2.2.png\|600px]]

	==== 情景4.~~3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点~~ ====		==== 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点【类似“情景4.2”】 ====
	【同上“情景4.2”，只是方向不同，对应的旋转操作不同】		【同上“情景4.2”，只是方向不同，对应的旋转操作不同】
	分为两种情况：		分为两种情况：

Eijux：/* 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 */

2021-04-21T17:32:39Z

情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点

@@ 第139行： / 第139行： @@
 当替换结点是黑色时，就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡。
-===== 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 =====
+===== 情景2.1：替换结点是其父结点的左子结点 =====
 分为两种情况：
-# '''情景2.1.1'''：“替换结点的兄弟结点是红结点”，处理：
+# '''情景2.1.1'''：“'''替换结点的兄弟结点是红结点'''”，处理：
 #* 若兄弟结点是红结点，那么根据“性质4”，兄弟结点的父结点和子结点肯定为黑色。
 ## 将 S 设为黑色；
@@ 第147行： / 第147行： @@
 ## 对P进行左旋，得到“情景2.1.2.3”并处理。
 #: [[File:红黑树： 删除情景2.1.1.png|600px]]
-# '''情景2.1.2'''：“替换结点的兄弟结点是黑结点”，处理：
+# '''情景2.1.2'''：“'''替换结点的兄弟结点是黑结点'''”，处理：
 #* 当兄弟结点为红结点，其父结点和子结点的具体颜色无法确定。此时又得考虑多种情景：
-## “'''情景2.1.2.1'''”：“替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色”，处理：
+## “'''情景2.1.2.1'''”：“'''替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色'''”，处理：
-##* 即将删除的左子树的一个黑色结点，显然左子树的黑色结点少1了，然而右子树又又红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。
+##* 即将删除的左子树的一个黑色结点【R 结点】，显然左子树的黑色结点少 1 了，然而右子树又又红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。
 ### 将 S 的颜色设为 P 的颜色；
 ### 将 P 设为黑色；
@@ 第156行： / 第156行： @@
 ### 对 P 进行左旋。
 ##: [[File:红黑树：删除情景2.1.2.1.png|600px]]

Eijux：/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

2021-04-21T17:05:16Z

情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点

←上一版本		2021年4月22日 (四) 01:05的版本
第95行：		第95行：
	分为两种情况：		分为两种情况：
	# '''情景 4.3.1'''：“插入结点是其父结点的左子结点”，处理：		# '''情景 4.3.1'''：“插入结点是其父结点的左子结点”，处理：
	## 将 P ~~设为黑色。~~		## 将 P 设为黑色；
	## 将 PP ~~设为红色。~~		## 将 PP 设为红色；
	## 对 PP 进行左旋。		## 对 PP 进行左旋。
	#: [[File:红黑树：插入情景4.3.1.png\|400px]]		#: [[File:红黑树：插入情景4.3.1.png\|400px]]
	#: 如上，已平衡无需再处理。		#: 如上，已平衡无需再处理。
	# '''情景 4.3.2'''：“插入结点是其父结点的右子结点”，处理：		# '''情景 4.3.2'''：“插入结点是其父结点的右子结点”，处理：
	## 对 P ~~进行左旋。~~		## 对 P 进行左旋；
	## 把 P 设置为插入结点，得到“情景 4.3.1”，并进行如上“情景4.3.1”处理。		## 把 P 设置为插入结点，得到“情景 4.3.1”，并进行如上“情景4.3.1”处理。
	#: [[File:红黑树：插入情景4.3.2.png\|600px]]		#: [[File:红黑树：插入情景4.3.2.png\|600px]]

Eijux：/* 情景4.2：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的左子结点 */

2021-04-21T17:04:59Z

情景4.2：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的左子结点

←上一版本		2021年4月22日 (四) 01:04的版本
第81行：		第81行：
	分为两种情况：		分为两种情况：
	# '''情景 4.2.1'''：“插入结点是其父结点的左子结点”，处理：		# '''情景 4.2.1'''：“插入结点是其父结点的左子结点”，处理：
	## 将 P ~~设为黑色。【此时，叔叔节点不存在，或为叶子节点（黑色）】~~		## 将 P 设为黑色；【此时，叔叔节点不存在，或为叶子节点（黑色）】
	## 将 PP ~~设为红色。~~		## 将 PP 设为红色；
	## 对 PP 进行右旋。		## 对 PP 进行右旋。
	#: [[File:红黑树：插入情景4.2.1.png\|400px]]		#: [[File:红黑树：插入情景4.2.1.png\|400px]]
	#: 如上，已平衡无需再处理。		#: 如上，已平衡无需再处理。
	# '''情景 4.2.2'''：“插入结点是其父结点的右子结点”，处理：		# '''情景 4.2.2'''：“插入结点是其父结点的右子结点”，处理：
	## 对 P ~~进行左旋。~~		## 对 P 进行左旋；
	## 把 P 设置为插入结点，得到“情景 4.2.1”，并进行如上“情景4.2.1”处理。		## 把 P 设置为插入结点，得到“情景 4.2.1”，并进行如上“情景4.2.1”处理。
	#: [[File:红黑树：插入情景4.2.2.png\|600px]]		#: [[File:红黑树：插入情景4.2.2.png\|600px]]

Eijux：/* 情景4.1：父结点为红结点，叔叔结点存在并且为红结点 */

2021-04-21T17:04:25Z

情景4.1：父结点为红结点，叔叔结点存在并且为红结点

←上一版本		2021年4月22日 (四) 01:04的版本
第64行：		第64行：

	那么此时该插入子树的红黑层数的情况是：'''黑红红'''，显然最简单的处理方式是把其改为：'''红黑红'''：		那么此时该插入子树的红黑层数的情况是：'''黑红红'''，显然最简单的处理方式是把其改为：'''红黑红'''：
	# 将 P 和 S ~~设置为黑色。~~		# 将 P 和 S 设置为黑色；
	# 将 PP ~~设置为红色。~~		# 将 PP 设置为红色；
	#:如图：		#:如图：
	#: [[File:红黑树：插入情景4.1_1.png\|400px]] [[File:红黑树：插入情景4.1_2.png\|400px]]		#: [[File:红黑树：插入情景4.1_1.png\|400px]] [[File:红黑树：插入情景4.1_2.png\|400px]]
	# 把 PP 设置为当前插入结点：【此时 PP 结点为红色】		# 把 PP 设置为当前插入结点：【此时 PP 结点为红色】
	## 如果 PP 的父结点是黑色，则已平衡无需再处理；		## 如果 PP 的父结点是黑色，则已平衡无需再处理；
	## 如果 PP 的父结点是红色（“性质4”），则把 PP ~~当作新的插入结点，应用不同插入情景继续插入操作自平衡处理。~~		## 如果 PP 的父结点是红色（“性质4”），则把 PP 当作新的插入结点，应用不同插入情景继续插入操作自平衡处理；
	## 如果 PP 刚好为根结点时（“性质2”），必须把 PP 重新设为黑色，那么树的红黑结构变为：'''黑黑红'''。		## 如果 PP 刚好为根结点时（“性质2”），必须把 PP 重新设为黑色，那么树的红黑结构变为：'''黑黑红'''。
	##: 即，从根结点到叶子结点的路径中，黑色结点增加了。【这是唯一一种会增加红黑树黑色结点层数的插入情景】		##: 即，从根结点到叶子结点的路径中，黑色结点增加了。【这是唯一一种会增加红黑树黑色结点层数的插入情景】

Eijux：/* 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 */

2021-04-21T17:03:41Z

情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点

←上一版本		2021年4月22日 (四) 01:03的版本
第143行：		第143行：
	# '''情景2.1.1'''：“替换结点的兄弟结点是红结点”，处理：		# '''情景2.1.1'''：“替换结点的兄弟结点是红结点”，处理：
	#* 若兄弟结点是红结点，那么根据“性质4”，兄弟结点的父结点和子结点肯定为黑色。		#* 若兄弟结点是红结点，那么根据“性质4”，兄弟结点的父结点和子结点肯定为黑色。
	## 将 S ~~设为黑色~~		## 将 S 设为黑色；
	## ~~将P设为红色~~		## 将 P 设为红色；
	## 对P进行左旋，得到“情景2.1.2.3”并处理。		## 对P进行左旋，得到“情景2.1.2.3”并处理。
	#: [[File:红黑树：删除情景2.1.1.png\|600px]]		#: [[File:红黑树：删除情景2.1.1.png\|600px]]
			# '''情景2.1.2'''：“替换结点的兄弟结点是黑结点”，处理：
			#* 当兄弟结点为红结点，其父结点和子结点的具体颜色无法确定。此时又得考虑多种情景：
			## “'''情景2.1.2.1'''”：“替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色”，处理：
			##* 即将删除的左子树的一个黑色结点，显然左子树的黑色结点少1了，然而右子树又又红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。
			### 将 S 的颜色设为 P 的颜色；
			### 将 P 设为黑色；
			### 将 SR 设为黑色；
			### 对 P 进行左旋。
			##: [[File:红黑树：删除情景2.1.2.1.png\|600px]]

Eijux：/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

2021-04-21T16:54:03Z

情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点

←上一版本		2021年4月22日 (四) 00:54的版本
第93行：		第93行：
	==== 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 ====		==== 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 ====
	【同上“情景4.2”，只是方向不同，对应的旋转操作不同】		【同上“情景4.2”，只是方向不同，对应的旋转操作不同】


	分为两种情况：		分为两种情况：
	# '''情景 4.3.1'''：“插入结点是其父结点的左子结点”，处理：		# '''情景 4.3.1'''：“插入结点是其父结点的左子结点”，处理：

树：红黑树 - 版本历史

Eijux：​/* 定义和性质 */

Eijux：​/* 情景2.2：替换结点是其父结点的右子结点【类似“情景2.1”】 */

Eijux：​/* 情景2.1：替换结点是其父结点的左子结点 */

Eijux：​/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

Eijux：​/* 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 */

Eijux：​/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

Eijux：​/* 情景4.2：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的左子结点 */

Eijux：​/* 情景4.1：父结点为红结点，叔叔结点存在并且为红结点 */

Eijux：​/* 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 */

Eijux：​/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

Eijux：/* 定义和性质 */

Eijux：/* 情景2.2：替换结点是其父结点的右子结点【类似“情景2.1”】 */

Eijux：/* 情景2.1：替换结点是其父结点的左子结点 */

Eijux：/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

Eijux：/* 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 */

Eijux：/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */

Eijux：/* 情景4.2：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的左子结点 */

Eijux：/* 情景4.1：父结点为红结点，叔叔结点存在并且为红结点 */

Eijux：/* 情景2.1：替换结点是黑结点，替换结点是其父结点的左子结点 */

Eijux：/* 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 */