阅读笔记。原文传送门
1. 概念
1.1 二叉查找树
红黑树本质上就是一棵二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree），排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意结点的左、右子树也分别为二叉查找树。
- 没有键值相等的结点（no duplicate nodes）。
一棵由n个结点，随机构造的二叉查找树的高度为logn，一般操作的执行时间为O（logn）。
二叉树若退化成了一棵具有n个结点的线性链后，操作最坏情况运行时间为O（n）。
1.2 红黑树
红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
红黑树的5条性质（正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度 ）：
1. 每个结点要么是红的，要么是黑的。
2. 根结点是黑的。
3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4. 如果一个结点是红的，那么它的俩个儿子都是黑的。
5. 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
wiki里有一棵红黑树的示例（由Cburnett - 自己的作品，CC BY-SA 3.0，https://commons.wikimedia.org/w/index.php?curid=1508398）：
2. 树的操作
2.1 旋转
对红黑树进行修改可能会违背红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即修改树中某些结点的颜色及指针结构，来继续保持它的性质或平衡。
2.1.1 左旋
如上图所示：
当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为任何不是NIL[T]的左孩子结点。
左旋以pivot到y之间的链为“支轴”进行，它使y成为该孩子树新的根，而y的左孩子b则成为pivot的右孩子。
左旋操作的参考代码如下所示（以x代替上述的pivot）：
LEFT-ROTATE(T, x)
1 y ← right[x] ▹ Set y.
2 right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree.
3 p[left[y]] ← x
4 p[y] ← p[x] ▹ Link x's parent to y.
5 if p[x] = nil[T]
6 then root[T] ← y
7 else if x = left[p[x]]
8 then left[p[x]] ← y
9 else right[p[x]] ← y
10 left[y] ← x ▹ Put x on y's left.
11 p[x] ← y
2.1.2 右旋
RIGHT-ROTATE(T, x)
1 y ← left[x] ▹ Set y.
2 left[x] ← right[y] ▹ Turn y's right subtree into x's left subtree.
3 p[right[y]] ← x
4 p[y] ← p[x] ▹ Link x's parent to y.
5 if p[x] = nil[T]
6 then root[T] ← y
7 else if x = left[p[x]]
8 then left[p[x]] ← y
9 else right[p[x]] ← y
10 right[y] ← x ▹ Put x on y's right.
11 p[x] ← y
** 对于树的旋转，能保持不变的只有原树的搜索性质；而原树的红黑性质则可利用旋转和颜色重涂来恢复。**
2.2 插入
2.2.1 二叉查找树的插入
TREE-INSERT(T, z)
1 y ← NIL
2 x ← root[T]
3 while x ≠ NIL
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = NIL
10 then root[T] ← z ⊹ Tree T was empty
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
2.2.2 红黑树的插入
红黑树的插入相当于在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
可以看出，RB-INSERT(T, z)前面的第1-13行代码基本就是二叉查找树的插入代码，然后第14-16行代码把z的左孩子、右孩子都赋为叶结点nil，再把z结点着为红色，最后为保证红黑性质在插入操作后依然保持，调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色，并旋转。
FIXUP可能面对以下几种情形：
- Case 1： 如果插入的是根结点，因为原树是空树，此情况只会违反性质2，所以直接把此结点涂为黑色。
- Case 2： 如果插入的结点的父结点是黑色，由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时也是什么也不做。
- Case 3： 如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
- Case 4： 如果当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子
- Case 5： 如果当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子
RB-INSERT-FIXUP（T,z）
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED ▹ Case 3
5 then color[p[z]] ← BLACK
6 color[y] ← BLACK
7 color[p[p[z]]] ← RED
8 z ← p[p[z]]
9 continue
10 else if z = right[p[z]] ▹ Case 4
11 then z ← p[z]
12 LEFT-ROTATE(T, z)
13 color[p[z]] ← BLACK ▹ Case 5
14 color[p[p[z]]] ← RED
15 RIGHT-ROTATE(T, p[p[z]])
16 else (same as then clause with "right" and "left" exchanged)
17 color[root[T]] ← BLACK ▹ Case 1
Case 3： 如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
对策：将当前结点的父结点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前结点重新开始算法。
Case 4： 如果当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子
对策：当前结点的父结点做为新的当前结点，以新当前结点为支点左旋。即如下代码所示：
Case 5： 如果当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子
对策：父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋
2.3 删除
2.3.1 二叉查找树的删除
待删除的结点按照儿子的个数可以分为三种：
- 没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。
- 只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。
- 有两个儿子。选择左儿子中的最大元素（一般选择）或者右儿子中的最小元素放到待删除结点的位置，然后调整子树（删除所选元素的原节点）。
TREE-DELETE(T, z)
1 if left[z] = NIL or right[z] = NIL
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ NIL
5 then x ← left[y]
6 else x ← right[y]
7 if x ≠ NIL
8 then p[x] ← p[y]
9 if p[y] = NIL
10 then root[T] ← x
11 else if y = left[p[y]]
12 then left[p[y]] ← x
13 else right[p[y]] ← x
14 if y ≠ z
15 then key[z] ← key[y]
16 copy y's satellite data into z
17 return y
2.3.2 红黑树的删除
RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y ≠ z
14 then key[z] ← key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y
如果删除的是红色结点，那么原红黑树的性质依旧保持，此时不用做修正操作，如果删除的结点是黑色结点，原红黑树的性质会被改变，我们要对其做修正操作。
FIXUP可能面对以下几种情形：
- Case 1： 如果顶替节点为红，直接把此结点涂为黑色，满足全部性质。
- Case 2： 如果顶替节点为黑，且为根节点，什么都不需要做。
- Case 3： 如果顶替节点为黑，兄弟节点为红色（此时父结点和兄弟结点的子结点一定都为黑）
- Case 4： 如果顶替节点为黑，兄弟节点及其双子为黑色（子节点不存在可视为黑），父节点为任意色
- Case 5： 如果顶替节点为黑，兄弟结点是黑色，兄弟的左子是红色、右子是黑色，父节点为任意色
- Case 6： 如果顶替节点为黑，兄弟结点是黑色，兄弟的左子是任意色、右子是红色，父节点为任意色
RB-DELETE-FIXUP(T, x)
1 while x ≠ root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w ← right[p[x]]
4 if color[w] = RED ▹ Case 3
5 then color[w] ← BLACK
6 color[p[x]] ← RED
7 LEFT-ROTATE(T, p[x])
8 w ← right[p[x]]
9 if color[left[w]] = BLACK and color[right[w]] = BLACK ▹ Case 4
10 then color[w] ← RED
11 if color[p[x]] = RED
12 then color[p[x]] ← BLACK
13 break
14 else x ← p[x]
15 continue
16 else if color[right[w]] = BLACK ▹ Case 5
17 then color[left[w]] ← BLACK
18 color[w] ← RED
19 RIGHT-ROTATE(T, w)
20 w ← right[p[x]]
21 color[w] ← color[p[x]] ▹ Case 6
22 color[p[x]] ← BLACK
23 color[right[w]] ← BLACK
24 LEFT-ROTATE(T, p[x])
25 x ← root[T]
26 else (same as then clause with "right" and "left" exchanged)
27 color[x] ← BLACK ▹ Case 1
Case 3： 如果顶替节点为黑，兄弟节点为红色（此时父结点和兄弟结点的子结点一定都为黑）
策略：把父结点染成红色，把兄弟结点染成黑色，以父节点为支点左旋，之后重新进入算法
/*
* upper letters stand black, while lower letters stand red,
* and letters in parentheses stand black or red.
*/
P S
/ \ / \
N s --> p Sr
/ \ / \
Sl Sr N Sl
Case 4： 如果顶替节点为黑，兄弟节点及其双子为黑色（子节点不存在可视为黑），父节点为任意色
策略：把父结点染成黑色，把兄弟结点染成红色，之后重新进入算法
(p) (p)
/ \ / \
N S --> N s
/ \ / \
Sl Sr Sl Sr
Case 5： 如果顶替节点为黑，兄弟结点是黑色，兄弟的左子是红色、右子是黑色，父节点为任意色
策略：把兄弟结点染红，兄弟左子结点染黑，之后再在兄弟结点为支点解右旋，之后重新进入算法
(p) (p)
/ \ / \
N S --> N Sl
/ \ \
sl Sr s
\
Sr
Case 6： 如果顶替节点为黑，兄弟结点是黑色，兄弟的左子是任意色、右子是红色，父节点为任意色
策略： 把兄弟结点染成当前结点父结点的颜色，把当前结点父结点染成黑色，兄弟结点右子染成黑色，之后以当前结点的父结点为支点进行左旋，此时算法结束
(p) (s)
/ \ / \
N S --> P Sr
/ \ / \
(sl) sr N (sl)