文章目录
1.红黑树介绍
二叉搜索树在最好情况下的时间复杂度是 O （ l o g n ） O（log n） O（logn），但是当插入元素是有序的时候，二叉搜索树就变成了一个链表，在这种情况下，时间复杂度为 O ( n ) O(n) O(n)。
红黑树就是针对这一情形进行改进。红黑树本质上是一种二叉搜索树，但它在二叉搜索树的基础上额外添加了一个标记（颜色），同时具有一定的规则，这些规则使得红黑树保证一种平衡，插入、删除、查找的最坏时间复杂度都为 O （ l o g n ） O（logn） O（logn）。红黑树的统计性能要好于平衡二叉树。
红黑树的在原有的二叉搜索树上增加了如下几个要求：
1）每个结点要么是红色，要么是黑色
2）根节点永远是黑色的
3）所有叶子结点都是黑色的（红黑树中的叶子结点都是空结点(NIL)。）
4）每个红色结点的两个子结点一定都是黑色的（说明从根到结点的路径上不会有两个连续的红色结点，但黑色结点可以是连续的）
5）从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点。（是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定）红黑树并不是标准的平衡二叉树，它是以上述要求作为一种平衡方法，使一棵n个结点的红黑树始终保持了 l o g n logn logn的高度，使得自己的性能得到提升。
2.红黑树的旋转
当对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。
1）左旋操作：当在某个结点pivot上，做左旋操作时，我们假设它的右孩子不是NIL（叶子结点），pivot可以为任何不是NIL的左子节点。左旋操作是以pivot到其右孩子之间的链为“支轴”进行，使得其右孩子成为该子树的新根，而右孩子的左孩子成为pivot的右孩子。
左旋伪代码如下：
def leftRoate(T, x):
y = x.right
x.right = y.left # y的左孩子成为x的右孩子
if y.left != NIL
y.left.parent = x # x的父结点成为y的父结点
y.parent = x.parent
if x.parent = NIL:
T.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.left = y
y.left = x
x.parent = y
2）右旋操作：与左旋操作类似，当在某个结点pivot上做右旋操作时，以pivot和其左孩子之间的链为轴，使得其左孩子成为该子树的新根，而左孩子的右孩子作为pivot的左孩子。
右旋伪代码如下：
def rightRoate(T, x):
y = x.left
x.left = y.right # y的左孩子成为x的右孩子
if y.right != NIL
y.right.parent = x # x的父结点成为y的父结点
y.parent = x.parent
if x.parent = NIL:
T.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.left = y
y.right = x
x.parent = y
3.红黑树的插入和创建
首先来了解一下二叉搜索树的插入：
伪代码：
def Tree-Insert(T, z): # T是一棵树，z是要插入的结点
y = NIL
x = T.root
while x != NIL:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z.parent = y
if y == NIL:
T.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z
红黑树的插入所示在二叉搜索树的基础上，为了重新回复平衡，继续做了插入修复操作。
红黑树插入的伪代码如下：假设插入的结点为z
def RB-INSERT(T, z):
y = NIL
x = T.root
while x != NIL:
y = x
if z.key < x.key:
x = x.left
x = x.right
z.parent = y
if y == NIL:
T.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z
z.left = NIL
z.right = NIL
z.color = red # 新插入的结点先设置为红色
RB-INSERT-FIXUP(T, z) # 调整红黑树
红黑树的插入，重要的是插入之后对红黑树进行调整，下面是各种情况的介绍：
- 1.插入结点设置为红色
- 2.如果插入结点为根节点，则将其置为黑色，return
- 3.如果插入结点的父节点为黑色，什么都不用做，return
- 4.如果插入结点的父节点为红色：
1）父节点是祖父节点的左孩子：
A. 叔叔结点为红色：
策略：将当前结点的父节点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结
点，从新的当前结点（即祖父结点）重新开始算法
B. 叔叔结点为黑色，且插入结点为父节点的右孩子：
策略：以插入结点的父节点做为新的当前结点，以新的当前结点为支点进行左旋操作
C. 叔叔结点为黑色， 插入结点为父节点的左孩子：
策略：当前结点的父节点变为黑色，祖父结点变为红色，以祖父结点为支点进行右旋操
作
2）父节点是祖父结点的右孩子：
A. 叔叔结点为红色：
策略：将当前结点的父节点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结
点，从新的当前结点（即祖父结点）重新开始算法
B. 叔叔结点为黑色， 插入结点为父节点的右孩子：
策略：将当前结点的父节点变为黑色，祖父结点变为红色，以祖父结点为支点进行左旋
操作
C. 叔叔结点为黑色， 插入结点为父节点的左孩子：
策略：当前结点的父节点最为新的当前结点，以新的当前结点为支点进行右旋操作
调整红黑树伪代码如下：
def RB-INSERT-FIXUP(T, z)：
while z.parent.color == RED:
if z.parent = z.parent.parent.left: # 其父节点是祖父结点的左孩子
y = z.parent.parent.right # y 是其叔叔结点
if y.color == RED: # 父节点为红色，叔叔结点也为红色
# 父节点是红色，且叔叔结点也是红色
# 当父节点是左孩子时：将当前结点的父节点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前结点重新开始算法
z.parent.color = BLACK
y.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
elif z == z.parent.right: # 叔叔结点为黑色， 且当前结点是其父节点的右孩子
# 当前结点的父节点最为新的当前结点，以新的当前结点为支点进行左旋操作
z = z.parent
LEFT-ROTATE(T, z)
elif z == z.parent.left: # 叔叔结点为黑色，且当前结点是其父节点的左孩子
# 将当前结点的父节点变为黑色，祖父结点变为红色，以祖父结点为支点进行右旋操作
z.parent.color = BLACK
a.parent.parent.color = RED
RIGHT-ROTATE(T, z.p.p)
else: # # 其父节点是祖父结点的右孩子
y = z.parent.parent.right # y 是其叔叔结点
if y.color == RED: #父节点为红色，叔叔结点也为红色
# 父节点是红色，且叔叔结点也是红色
# 当父节点是右孩子时：将当前结点的父节点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前结点重新开始算法
z.parent.color = BLACK
y.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
elif z == z.parent.right: # 叔叔结点为黑色， 且当前结点是其父节点的右孩子
# 将当前结点的父节点变为黑色，祖父结点变为红色，以祖父结点为支点进行左旋操作
z.parent.color = BLACK
z.parent.parent.color = RED
LEFT-ROTATE(T, z.parent.parent)
elif z == z.parent.left: # 叔叔结点为黑色，且当前结点是其父节点的左孩子
# 当前结点的父节点最为新的当前结点，以新的当前结点为支点进行右旋操作
z = z.parent
RIGHT-ROTATE(T, z)
T.root.color = BLACK # 将根节点涂为黑色
下面讲解红黑树的创建：
在很多关于红黑树的博文中，没有提到红黑树是怎么创建的，它们给出的图大多是下图中的红黑树。下面我们就开始从无到有的创建这一棵树。红黑树的创建是就是通过一步一步插入结点得到的。
初始的数组为：[13.8.17.1.11.15.25.6.22.27]
另外，同一个序列，排列顺序不同时，产生的红黑树也不同。下面举例说明：
当初始的数组为： [15, 1, 6, 13, 27, 17, 8, 11, 22, 25]，产生的红黑树步骤如下：（没有详细的解释了，仅仅展示每次插入调整之后的结果）
step1.插入15
step2.插入1
step3.插入6
step4.插入13
step5.插入27
step6.插入17
step7.插入8
step8.插入11
step9.插入22
step10.插入25
介绍一个红黑树在线图示：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
4.红黑树的删除
同样的，我们先了解一下二叉搜索树结点删除的几种情况
1.删除结点为叶节点：直接将父节点对应的儿子指针设为NULL，删除儿子结点即可
2.删除的结点b有一个儿子c，那么将删除结点的父节点a的相应儿子指针指向c，删除b即可
3.删除的结点有两个儿子：将其左子树的最大元素值或右子树的最小值代替该值，然后删除左子树最大元素或右子树最小元素的结点即可
下面来讨论红黑树删除的情况：
- case 1.被删除结点node没有非空子节点，且node结点是红色：
策略：直接将该结点删除即可，不会破幻红黑树的性质 - case2.被删除结点无子节点，且被删除结点为黑色
删除黑色结点会破幻红黑树的性质5），所以为了不破坏性质5），在替换节点上增加一个一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的节点加上除红与黑的另一种颜色，这里只是一种假设，有了这重额外的黑色，原红黑树性质5就能保持不变。
case 2.1被删除结点node的brother结点为黑色，且brother结点有一个与其自身方向一致的红色子节点son (son称为node的远侄子结点)
策略： 当node为左孩子：将父节点father和兄弟节点brother的颜色对调，然后以父节点father为支点，进行左旋操作，再将之前的红色son结点变为黑色即可。
当node为右孩子：将父节点father和兄弟节点brother的颜色对调，然后以父节点father为支点，进行右旋操作，再将之前的红色son结点变为黑色即可。
图解： 下图中白色的结点表示什么颜色都可以。
当node为左孩子：
当node为左孩子：
case 2.2被删除结点node的brother结点为黑色，且brother结点有一个与其自身方向不一致的红色子节点son(son称为node的近侄子结点)
策略：当node为左孩子：以近侄子节点为支点，进行右旋，并将近侄子节点的颜色与兄弟结点节点的颜色进行互换, 此时情况变为case2.1
当node为右孩子：将近侄子节点的颜色和兄弟结点的颜色互换，并以近侄子节点为支点，进行左旋操作, 此时情况变为case2.1
图解：
当node为左孩子：
当node为右孩子：
case 2.3被删除结点node的brother结点为黑色，且brother结点没有红色子结点
此时又可以分为两种情况：father结点为红色、father结点为黑色
1）当father结点为红色时，因为被删除结点node没有子节点，根据红黑树的性质可知，
brother结点也一定没有子节点
策略： 将father的颜色和brother的颜色互换，然后删除node即可。
2）当father结点为黑色时，因为被删除结点node没有子节点，根据红黑树的性质可知，
brother结点也一定没有子节点
策略： 将brother的颜色改为红色，这样删除node之后，father左右两支的黑色节点数就
相等了，但是经过father结点的路径上的黑色节点数会减少1，这个时候，我们再以
father为起始点，继续根据情况进行平衡操作（将father结点当做node结点，只是不再
进行删除操作），观察是什么情况，再进行相应的调整，这样一直向上，直到新的起
始点为根节点。
图解：
当被删除结点node的brother结点为黑色，且brother结点没有红色子结点，father结点为红色时， brother结点也一定没有子节点：
当被删除结点node的brother结点为黑色，且brother结点没有红色子结点，father结点为黑色时，brother结点也一定没有子节点：
case 2.4被删除结点node的brother结点为红色， 则其父节点一定为黑色
策略： 当被删除结点为左结点时，将父节点和兄弟结点的颜色互换，然后以父节点为支
点，进行左旋操作
当被删除结点为右结点时，将父节点和兄弟结点的颜色互换，然后以父节点为支
点，进行右旋操作
图解：
当被删除结点为左结点时：
当被删除结点为右结点时：
- case3.被删除结点只有一个子节点，且被删除结点为红色 — 该情况不存在
当被删除结点只有一个子节点时，其子节点必定为黑色，如图所示，违反了性质5）。
- case4.被删除结点只有一个子节点，且被删除结点为黑色
策略： 在这种情况下，则其子节点一定是红色，才能够满足性质5），删除node之后，将其子节点代替该结点，并涂黑即可
图解：
- case5&6：被删除结点有两个子节点，且被删除结点为黑色或红色
策略： 当被删除结点node有两个子节点时，先要找到被删除结点的后继结点
successor(此处successor为右子树中的最小值)，successor的情况有两种，
如下图所示。
策略： 当successor在左边图的情况中时，使用successor代替node之后，相当于删
除的结点变为了successor，如果successor为红色，且没有右子树的话，则
变成了case1；（如果successor为红色，但是有右子树的话，则变成了
case3），若successor为黑色，且没有右子树的话，则变成了组合2；如果
successor为黑色，但是有右子树的话，则变成了case4。
策略： 当successor在右边图的情况中时，使用successor代替node之后，相当于
successor被删除，如果successor为红色，则变成了case3，不可能存在，
所以successor只能为黑色，则变成了组合2或4。
5.参考
1.csdn，v_JULY_v， https://blog.csdn.net/v_july_v/article/details/6105630
2.博客园，青儿哥哥， https://www.cnblogs.com/qingergege/p/7351659.html
3.nbb3210 https://segmentfault.com/a/1190000012115424