ps：本文中结点和节点是同义词

红黑树的性质

红黑树是一棵二叉搜索树，它在每一个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK 。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树可以确保没有一条路径会比其它路径长出两倍，因而是近似于平衡的。

struct node{
	char color;
	int key;
	*node left;
	*node right;
	*node p;
	
}

如果一个结点没有子结点或父结点，则该结点相应指针属性的值为 NIL。我们将这些 NIL 视为二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

一棵红黑树是满足一下红黑性质的二叉搜索树：

每个结点或是红色的，或是黑色的
根节点是黑色的
每个叶结点（NIL）是黑色的
如果一个结点是红色的，则它的两个子结点都是黑色的
对每个结点，从该结点到其所有后代结点的简单路径上，均包含相同数目的黑色结点。 ^923721

黑高：从某个结点 x 出发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高，记为bh(x)。

引理13.1 ：一棵有n个内部结点的红黑树的高度至多为 2lg(n+1)

旋转

为了维护红黑性质，必须要修改树中某些结点的颜色以及指针结构。

指针结构的修改是通过旋转来完成的，旋转是一种能保持二叉搜索树性质的搜索树局部操作。

左旋

当在某个结点 x 上做左旋时，假设它的右孩子为 y 而不是 T.nil（空结点）；x 可以为其右孩子不是T.nil 结点的树内任意结点。

右旋

与左旋对称

插入

将一个结点插入红黑树中，先将该结点设为红色，然后再对结点重新着色并旋转。

RB-INSERT(T,z) //z表示将要插入的结点，T表示红黑树
 y = T.nil
 x = T.root
 while x != T.nil
	 y = x
	 if z.key < x.key
		 x = x.left
	else
		x = x.right
 z.p = y
 if y == T.nil  //空树
	 T.root = z
 elif z.key < y.key
	 y.left = z
 else
	 y.right = z
 z.left = T.nil
 z.right = T.nil
 z.color = RED //新插入的结点默认为RED

 RB-INSERT-FIXUP(T,z)

RB-INSERT-FIXUP(T,z)

while z.p.color == RED
 if z.p == z.p.p.left  // 如果当前插入结点的父结点是其父结点的左孩子结点
	 y = z.p.p.right   // 令 y 等于其父结点的右孩子结点 AKA父结点的兄弟结点
	 if y.color == RED  // 如果父结点的兄弟结点为 红色
		 z.p.color = BLACK // 令父结点的颜色为黑色
		 y.color = BLACK // 令兄弟结点的颜色为黑色
		 z.p.p.color = RED // 令父结点的父结点的颜色为红色
		 z = z.p.p  // 令 z 为父结点的父结点
	elif z == z.p.right // 插入结点是右孩子
		 z = z.p
		 LEFT-ROTATE(T,z)
	z.p.color = BLACK
	z.p.p.color = RED
	RIGHT-ROTATE(T,z.p.p)
 else    //当前插入结点的父结点是其父结点的右孩子结点
	 ...
T.root.color = BLACK

为了理解 RB-INSERT-FIXUP 的工作过程，要将代码分成三个主要的步骤

要确定当结点 z 被插入并着为红色后，红黑性质中有哪些不能继续保持（插入过程）
要分析 while 循环的总目标
要分析 while 循环中的三种情况，理解它们的功能

插入一个新结点，那么这个树的结点仍然不是黑色就是红色，且所有NIL仍然是黑色的。因为插入的结点默认为红色（保持性质1），新插入的结点的左右孩子结点为 T.nil (保持性质2)。

对于性质5，即从一个指定结点开始的每条简单路径上的黑结点的个数都是相等的，也仍然成立，因为新插入的结点 z代替了一个 T.nil(黑色结点)，z为红色，而z的左右孩子仍然为黑色，因此性质5仍然保持。

while循环的循环不变式

结点z的颜色是RED
如果z.p是根节点，则z.p是黑结点
如果有任何红黑性质被破坏，则至多只有一条被破坏。如果性质2被破坏，则z为根节点且为红结点。如果性质4被破坏，则是因为z和z.p都是红结点

初始化

在循环的第一次迭代之前，从一棵正常的红黑树开始，并新增一个红结点z。

如果违反了性质2，则红色根节点一定是新增结点z，此时它是树中的唯一的内部结点。因为z的父结点以及左右孩子均为 T.nil，所以没有违反性质4.
如果违反了性质4，则由于 z 的子结点为黑色，且该树在新插入结点之前没有其他性质的违反，所以只是因为 z 和 z,p是黑色的。

终止

循环终止是因为 z.p是黑色的。如果 z 是根结点，则可能因为 z 是红色的违反性质 4，在RB-INSERT-FIXUP中的最后一行代码可恢复此性质。故此时所有红黑性质均成立。

保持

由于插入结点 z 的父结点是右孩子的情况和是左孩子的情况对称，故只用考虑是右孩子的情况即可。

情况1：z的叔结点 y 是红色的

用z表示当前迭代中的结点 z ，z’ = z.p.p表示在一次迭代第一行测试的结点 z

因为这次迭代把 z.p.p着为红色，结点z’在下一次迭代的开始是红色
这次迭代中结点 z’.p 是 z.p.p.p，且这个结点的颜色不会改变。如果它是根节点，那么此次迭代之前它是黑色的，且它在下次迭代开始仍然是黑色的。
情况1保证性质1，性质3，性质5

如果结点 z’ 在下一次迭代开始时是根节点，则情况1使其为黑色，使其新插入的结点 z 为红色。恢复了性质4。由于z’为红色，故做情况1违背了性质2，但最后一行默认设置根节点为黑色，故可恢复性质2。

如果结点 z’ 在下一次迭代开始时不是根节点，则情况1不会导致性质2被破坏，情况1可以修正z与z.p之间违背性质4。但使 z’ 为红色，若 z’.p是黑色，则 z’.p 和 z’之前没有违背情况，若z’.p是红色，则又违背了性质4。

情况2：z的叔结点 y 是黑色的且 z 是一个右孩子

情况3： z的叔节点 y 是黑色的且 z 是一个左孩子

在情况2和情况3 中，z的叔结点 y 是黑色的。通过 z 是 z.p 的右孩子还是左孩子来区别这两种情况。
在情况2中，结点 z 是它的父结点的右孩子，可以使用一个左旋来将此情况转变此情况为性质3，此时结点z为左孩子。

因为z 和 z.p 都是红色的，所以该旋转对于结点的黑高和性质5都无影响。

无论是直接进入情况3，还是通过情况2进入情况3，z 的叔结点 y 总是黑色的，否则就是情况 1.

此外 z.p.p存在，因为要进入循环，则 z.p 为 RED，又由循环不变式可知，红黑树的根节点必为黑色，故 z.p 必不是根节点， z.p有父结点。

![[红黑树图13-6.png]]

令 z = z.p ，即将 z 上移一层，然后执行 LEFT-ROTATE ，又将 z 下移了一层，z.p.p的身份保持不变。在情况3中，改变某些结点的颜色并做一次右旋，保持性质5。自此，所有性质得到保证，循环终止。

下面证明情况2和情况3保持了循环不变式。

情况2 让 z 指向红色的 z.p。在情况 2 和情况 3 中 z 及 z 的颜色都不再改变
情况 3 将 z.p 着成黑色，使得如果 z.p 在下一次迭代开始时是根节点，则它是黑色的。
性质1，3，5仍然得到保持。

删除

从一棵红黑树中删除结点的过程是基于TREE-DELETE过程而来的。

RB-TRANSPLANT(T,u,v)

if u.p == T.nil
	T.root = v
elif u = u.p.left
	u.p.left = v
else
	u.p.right = v
v.p = u.p

RB-DELETE(T,z)

y = z
y-original-color = y.color
if z.left = T.nil
	x = z.right
	RB-TRANSPLANT(T,z,z.right)
elif z.right = T.nil
	x = z.left
	RB-TRANSPLANT(T,z,z.left)
else                    // z有两个孩子结点
	y = TREE-MINIMUM(z.right)  // 找到z的右子树中的最小值
	y-original-color = y.color  
	x = y.right  // 设 x 等于 y的右子树
	if y.p == z  // 如果y的父结点就是 z ，那么以y为结点的二叉搜索树必然只有右孩子结点
		x.p =y  // 设x的父结点为 y
	else          // y的父结点不是z
		RB-TRANSPLANT(T,y,y.right) 用 y 的右子树代替y的位置
		y.right = z.right   // 用z的右子树代替 y的右子树
		y.right.p = y   // 将y的右子树（原先z的右子树）的父结点设为 y
	RB-TRANSPLANT(T,z,y)  
	y.left = z.left
	y.left.p = y
	y.color = z.color

if y-original-color == BLACK
	RB-DELETE-FIXUP(T,x)

对于将要删除的只有左孩子/右孩子的结点，这样的结点必然是黑结点，孩子结点为红色，因为如果这个结点是红色，那么它一个子树的黑高为 0 ，而另一个不为 0。对于这样的直接用孩子代替结点 z ，再将其变为黑色。

y的性质

始终维持结点 y 为从树中删除的结点或者移至树内的结点。
由于结点y的颜色可能改变，变量 y-original-color 存储了发生改变前y的颜色。

RB-DELETE-FIXUP(T,x)

while x != T.root and x.color == BLACK
	if x == x.p.left
		w = x.p.right
		if w.color == RED
			w.color = BLACK
			x.p.color = RED
			LEFT-ROTATE(T,x.p)
			w = x.p.right
		if w.left.color == BLACK and w.right.color == BLACK
			w.color = RED
			x = x.p
		else if
			  w.right.color == BLACK
			  w.color = RED
			  RIGHT-ROTATE(T,w)
			  w = x.p.right
		w.color = x.p.color
		x.p.color = BLACK
		w.right.color = BLACK
		LEFT-ROTATE(T,x.p)
		x = T.root
	
	else (same as then clause with "right" and "left" exchanged)

x.color = BLACK

删除的是只有左孩子/只有右孩子：代替后变黑

红色结点：首先，它肯定只有右孩子结点，删除后，第一，它不会影响它在的路径的黑高；第二它不会使两个红色结点相邻，因为它的右孩子结点颜色为黑色。
黑色结点：它也只有右孩子，删除后，它会使它在的路径的黑高减去1，根据二叉搜索树的删除，只有右孩子可以直接替代，因此用右孩子（红色）替代，然后把这个红色结点变成红色，这样这个路径上的黑高就不会变化。

如果（实际）删除的是没有孩子的结点（设r为兄弟的右孩子，s为要删除的结点的兄弟结点，p为删除结点的父结点）

因为删除后的替代结点要么是一个左孩子（右子树中的最小结点），或者是待删除的右孩子结点。
如果是左孩子，那么它最多就一个右孩子了，不可能有左孩子（不然就不是待删除结点的右子树中的最小结点了）。如果它是右孩子结点，那么它最多只有右孩子结点（如果有左孩子结点，那么它也不是右子树中最小的）。

双黑节点
删除（移动）黑色结点（设为y）会导致包含该节点的任意简单路径上黑色节点个数减少一。因此 y 的任何祖先都不满足性质5。改正这一问题的方法是将现在占有 y 原来位置的节点 x 视为还有一重额外的黑色。

红节点：删除后无需任何调整
黑结点
1. 兄弟是黑色
  1. 兄弟至少有一个红孩子：（LL，RR，LR，RL）变色+旋转
    1. LL型：变色（r变s，s变p，p变黑）右旋，双黑变单黑
    2. RR型：变色（r变s，s变p，p变黑）左旋，双黑变单黑
    3. LR型：变色（r变p，p变黑）左旋p的左孩子，然后右旋p，双黑变单黑
    4. RL型：变色（r变p，p变黑）右旋p的右孩子，然后左旋p，双黑变单黑
  2. 兄弟的孩子全是黑色
    1. 兄弟变红，双黑上移，遇到红色结点或根结点直接变成黑色
2. 兄弟是红色
  1. 兄父变色，朝双黑旋转（保持双黑继续调整）

没有孩子的红色结点删除后，显然不破坏任何在删除中可能被破坏的性质

根节点为黑色：删除的是红色结点，根节点不是红色，对根节点没有影响
黑高没有变化：删除的是红色结点，黑高指的是其到叶结点经过的黑色结点数。
不存在相邻的红色结点：显然的，因为它没有孩子，同时父结点为黑色。

没有孩子的其实对应算法导论里 x（替换被删除的结点 y）就是T.nil。所以x是双黑结点。

待删除结点（为黑色，且兄弟是红色）
这一步是为了转换成兄弟为黑色且兄弟至少有一个红孩子或兄弟为黑色且全是黑色孩子的情况）。
兄父变色，那么s为黑色，p为红色。朝双黑旋转，如果双黑是p的左孩子，那么就是左旋，p变成了 s 的左孩子。s的左孩子（黑色）变成了p的右孩子。此时为兄弟为黑色且兄弟的孩子…。