树
本文总结几种树
二叉树
树：
class Node{
Object element;// 存储数据
Node left;// 左孩子
Node right;// 右孩子
}
二叉查找树：
对于每个节点，其左子节点的值都比它小，而右子节点的值都比它大。
B树：特殊的二叉查找树，数据库常用来存储数据。
二叉树的遍历：
它的前序遍历顺序为：ABDGHCEIF（规则是先是根结点，再前序遍历左子树，再前序遍历右子树）
它的中序遍历顺序为：GDHBAEICF（规则是先中序遍历左子树，再是根结点，再是中序遍历右子树）
它的后序遍历顺序为：GHDBIEFCA（规则是先后序遍历左子树，再是后序遍历右子树，再是根结点）
二叉查找树的搜索、插入、删除：
搜索：node为树中节点
while node is not NULL:
if node->key ==target_key, return node
elseif node->key >target_key, node = node->left
else node = node->righ
插入：插入的元素是叶子节点（关键点：用一个变量存储当前指向节点，一个变量存储当前指向节点的parent）
parent = NULL
pcur = root
while(pcur) {
if (pcur->value ==target_key) {
return false
} elseif(pcur->value >target_key) {
parent = pcur
pcur = pcur->left
} else {
parent = pcur
pcur = pcur->right
}
}
if parent->value >target_key
parent->left = new Node(target_key);
else
parent-> right = new Node(target_key);
删除：
1.无左右孩子，直接删除；
2.只有左孩子，则让待删除的节点的父节点指向该左孩子；
3.只有右孩子，则让待删除的节点的父节点指向该右孩子；
4.左右孩子都有：
- 找到该节点右子树中的最左孩子（右子树中序遍历的第一个节点
- 把它的值和要删除的节点交换
- 删除这个最左孩子
删除代码：（摘抄https://www.linuxidc.com/Linux/2016-08/134742.htm）
parent = NULL
pcur = node
del = pcur
while(pcur->value != target_key && pcur != NULL) {
if (pcur->value > target_key) {
parent = pcur
pcur = pcur->left
} elseif (pcur->value < target_key) {
parent = pcur
pcur = pcur->right
}
}
if (pcur == NULL)
return false
if (pcur->left == NULL) {//当前节点只有右子节点
if (pcur == root) {
root = pcur->right
} elseif (pcur == parent->left) {//当前节点是父节点的左子节点
parent->left = pcur->right
} else {//当前节点是父节点的右子节点
parent->right = pcur->right
}
del = pcur
} elseif (pcur->right == NULL) {//当前节点只有左子节点
if (pcur == root) {
root = pcur->left
} elseif (pcur == parent->left) {//当前节点是父节点的左子节点
parent->left = pcur->left
} else {//当前节点是父节点的右子节点
parent->right = pcur->left
}
del = pcur
} else {//当前节点左右子节点都有
//找到右子树的最左节点
parent = pcur
target_left = pcur->right//右子树
while(target_left->left){//找到最左节点
parent = target_left
target_left = target_left->left
}
del = target_left
pcur->value = target_left->value//交换要删除节点和最左节点的值
//删除该最左节点
if(parent->left == target_left) {
parent->left = target_left -> right
} else {//这种情况是在右子树当前就是其自己这棵树的最左节点的情况下，则其右子树替上来作为parent的右树
parent->right = target_left -> right
}
delete del;
return true;
}
左旋：
LEFT-ROTATE(T, x)
y ← right[x] // 前提：这里假设x的右孩子为y。下面开始正式操作
right[x] ← left[y] // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子
p[left[y]] ← x // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x
p[y] ← p[x] // 将 “x的父亲” 设为 “y的父亲”
if p[x] = nil[T]
then root[T] ← y // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
else if x = left[p[x]]
then left[p[x]] ← y // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else right[p[x]] ← y // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
left[y] ← x // 将 “x” 设为 “y的左孩子”
p[x] ← y // 将 “x的父节点” 设为 “y”
右旋：
RIGHT-ROTATE(T, y)
x ← left[y] // 前提：这里假设y的左孩子为x。下面开始正式操作
left[y] ← right[x] // 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子
p[right[x]] ← y // 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y
p[x] ← p[y] // 将 “y的父亲” 设为 “x的父亲”
if p[y] = nil[T]
then root[T] ← x // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点
else if y = right[p[y]]
then right[p[y]] ← x // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
else left[p[y]] ← x // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
right[x] ← y // 将 “y” 设为 “x的右孩子”
p[y] ← x // 将 “y的父节点” 设为 “x”
左旋/右旋不改变二叉树的性质，即如果该树在旋转前是二叉树，则旋转后依然是二叉树。所以当插入/删除的时候我们用旋转来保持AVL树、红黑树等的性质。
AVL树：二叉平衡树
定义：AVL树是带有平衡条件的二叉查找树。这个平衡条件必须容易保持，而且它保证树的深度必须是O(log N)。一颗AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（空树的高度定义为-1）。这样就能充分利用二叉树的特性，避免一个分支走到底。
AVL树插入：
AVL树的插入，有可能影响AVL树的平衡，下面分两种情况讨论：
1.外部失衡
1.1 （LL）某个节点左孩子的左子树插入一个节点使得树失衡：把左孩子做右旋
1.2 （RR）某个节点右孩子的右子树插入一个节点使得树失衡：把右孩子做左旋
2.外部失衡
2.1 （RL）某个节点k1右孩子的左子树插入一个节点使得树失衡：把左孩子右旋再左旋
2.2 （LR）某个节点k3左孩子的右子树插入一个节点使得树失衡：把右孩子左旋再右旋
代码思路：
1.拿到一个节点newNode后按照二叉查找树的插入方式插入树中。
2.从底向上检查currNode是否失衡。如果失衡，标记当前失衡节点为currNode。
3.找到失衡点后：
3.1 如果Depth(currNode.left) – Depth(currNode.right) = 2：左侧比右侧深，有可能是LL/LR，且newNode < currNode。
如果 newNode < currNode.left，则为LL：对currNode进行右旋。
如果 newNode > currNode.left，则为LR：对currNode.left进行左旋，再对currNode进行右旋。
3.2 如果Depth(currNode.right) – Depth(currNode.left) = 2：左侧比右侧深，有可能是RL/RR，且newNode > currNode。
如果newNode > currNode.right，则为RR：对currNode进行左旋。
如果newNode < currNode.right，则为RL：对currNode.right进行右旋，再对currNode进行左旋。
PS:这里需要注意LL/RR和LR/RL情况下，currNode在的不同位置。
AVL树的删除：按照二叉查找树来删除之后，按照以上思路来使之平衡。
1.从根节点开始找到要删除的节点currNode；
2.从左子树找到最大值targetNode（或者右子树找到最小值），如果左子树为空则直接把右子树上位，如果右子树也为空则直接删除currNode即可。
3.把currNode放到targetNode上，然后删除。
4.这个时候失衡只有LL/RR两种情况，按照上面调整失衡。
代码：（摘抄https://www.cnblogs.com/Lynn-Zhang/p/5643797.html）
//// AVL树的节点类
template<class K,class V>
class AVLTreeNode
{
K _key;
V _value;
int _bf;//balance factor平衡因子 -1,0,1(每个节点的平衡因子等于右子树的高度减去左子树的高度)
AVLTreeNode<K, V>* _parent; //指向父节点的指针
AVLTreeNode<K, V>* _left; //指向左孩子的指针
AVLTreeNode<K, V>* _right; //指向右孩子的指针
AVLTreeNode(const K& key = K(), const V& value = V())
:_key(key)
, _value(value)
, _bf(0)
, _parent(NULL)
, _left(NULL)
, _right(NULL)
{}
};
插入数据
// AVLTree插入算法
template<class K, class V>
bool AVLTree<K,V>::Insert(const K& key, const V& value)
{
//1.空树
if (_root == NULL)
{
_root = new AVLTreeNode<K, V>(key, value);
return true;
}
//2.AVL树不为NULL
AVLTreeNode<K, V>* parent = NULL;
AVLTreeNode<K, V>* cur = _root;
//找到数据插入位置
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//插入数据
cur = new AVLTreeNode<K, V>(key, value);
cur->_parent = parent;
if (parent->_key > key)
parent->_left = cur;
else
parent->_right = cur;
while (parent)
{
//更新平衡因子
if (cur == parent->_left)
parent->_bf--;
else if (cur == parent->_right)
parent->_bf++;
//检验平衡因子是否合法
if (parent->_bf == 0)
break;
else if (parent->_bf == -1 || parent->_bf == 1)
{ // 回溯上升 更新祖父节点的平衡因子并检验合法性
cur = parent;
parent = cur->_parent;
}
else // 2 -2 平衡因子不合法 需要进行旋转 降低高度
{
if (parent->_bf == 2)
{
if (cur->_bf == 1)
_RotateL(parent);
else
_RotateRL(parent);
}
else if (parent->_bf == -2)
{
if (cur->_bf == -1)
_RotateR(parent);
else
_RotateLR(parent);
}
break;
}
}
}
左旋：
//左旋
template<class K, class V>
void AVLTree<K, V>::_RotateL(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* subR = parent->_right;
AVLTreeNode<K, V>* subRL = subR->_left;
AVLTreeNode<K, V>* ppNode = parent->_parent; //标记祖先节点
//1.构建parent子树 链接parent和subRL
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
//2.构建subR子树 链接parent和subR
subR->_left = parent;
parent->_parent = subR;
//3.链接祖先节点和subR节点
subR->_parent = ppNode;
if (ppNode== NULL)
{//如果祖先节点为NULL，说明目前的根节点为subR
_root = subR;
}
else
{ //将祖先节点和subR节点链接起来
if (parent == ppNode->_left)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
//4.重置平衡因子
parent->_bf = 0;
subR->_bf = 0;
//5.更新subR为当前父节点
parent = subR;
}
右旋：
///右旋
template<class K, class V>
void AVLTree<K, V>::_RotateR(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* subL = parent->_left;
AVLTreeNode<K, V>* subLR = subL->_right;
AVLTreeNode<K, V>* ppNode = parent->_parent; //标记祖先节点
//1.构建parent子树 将parent和subLR链接起来
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
//2.构建subL子树 将subL与parent链接起来
subL->_right = parent;
parent->_parent = subL;
//3.将祖先节点与sunL链接起来
if (ppNode == NULL)
{ //如果祖先为NULL，说明当前subL节点为根节点
subL->_parent = NULL;
_root = subL;
}
else
{
subL->_parent = ppNode;
if (ppNode->_left == parent)
ppNode->_left = subL;
else if (ppNode->_right == parent)
ppNode->_right = subL;
}
//4.重置平衡因子
parent->_bf = 0;
subL->_bf = 0;
//5.更新subL为当前父节点
parent = subL;
}
左右：
//左右双旋
template<class K, class V>
void AVLTree<K, V>::_RotateLR(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* pNode = parent;
AVLTreeNode<K, V>* subL = parent->_left;
AVLTreeNode<K, V>* subLR = subL->_right;
int bf = subLR->_bf;
_RotateL(parent->_left);
_RotateR(parent);
if (bf == 1)
{
pNode->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
pNode->_bf = 1;
subL->_bf = 0;
}
else
{
pNode->_bf = 0;
subL->_bf = 0;
}
}
右左：
//右左双旋
template<class K, class V>
void AVLTree<K, V>::_RotateRL(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* pNode = parent;
AVLTreeNode<K, V>* subR= parent->_right;
AVLTreeNode<K, V>* subRL = subR->_left;
int bf = subRL->_bf;
_RotateR(parent->_right);
_RotateL(parent);
if (bf == 1)
{
pNode->_bf = 0;
subR->_bf = -1;
}
else if (bf == -1)
{
pNode->_bf = 1;
subR->_bf = 0;
}
else
{
pNode->_bf = 0;
subR->_bf = 0;
}
}
AVL 的操作代价分析：（http://blog.csdn.net/sun_tttt/article/details/65445754）
(1) 查找代价： AVL是严格平衡的BST（平衡因子不超过1）。那么查找过程与BST一样，只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好，最坏情况都是O(logN)数量级的。
(2) 插入代价： AVL必须要保证严格平衡(|bf|<=1)，那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上，AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此，总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。
(3) 删除代价：AVL删除结点的算法可以参见BST的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)
AVL 效率总结 : 查找的时间复杂度维持在O(logN)，不会出现最差情况
AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。
AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。
红黑树：（摘抄https://www.cnblogs.com/skywang12345/p/3245399.html）
历史上AVL树流行的另一变种是红黑树。
二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN)的查找时间复杂度。但是这样做是否值得呢？
能不能找一种折中策略，即不牺牲太大的建立查找结构的代价，也能保证稳定高效的查找效率呢？ 答案就是：红黑树。
红黑树的性质：一棵含有n个节点的红黑树的高度至多为2log(n+1)（https://www.cnblogs.com/skywang12345/p/3245399.html）
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以 **O(log2n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡。但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。
在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。
典型的用途是实现关联数组
RBT 的操作代价分析：
(1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。
(2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。
(3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。
**RBT 效率总结:**查找效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。
插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
http://blog.csdn.net/sun_tttt/article/details/65445754
**1.红黑树的实现其实是一个2、3、4树，只是将双节点或者三节点用红色进行了标示，如果你将红色节点放到和它父元素相同的高度，并把它和父元素看做是一个元素，你就会发现，变成了一个高度为lgN的二叉树，这个2.3.4树对红黑树很有启发意义。 **
**2.上面的步骤其实可以不用死记硬背，是可以推导出来的，因为我们是把一个平衡但通过插入或者删除破坏了平衡的红黑树再次平衡，同过旋转让位，改变红黑颜色，使之符合那五条基本性质。比如遇到删除操作情况四的时候，我们可以把那个删除元素去除，发现左边比右边少一个黑元素，这个时候，怎么办，我们发现兄弟节点的子元素有一个红元素，操作这个不会影响那五条性质，所以我们通过变换颜色，旋转，即可让左右两边的的黑色数目一样。 **
**3.旋转操作的目的是出让一个元素到另外的地方并且符合二叉树左小右大的性质，交换颜色的目的是为了保持红黑树的那五条性质。 **
4.要时刻记得 ，一切的操作都是为了保持那五条性质。
**最后的最后，其实还有一种更为简单的红黑二叉树，这个简单的红黑二叉树实际上是一个2.3树，他只允许左节点为红节点，但是性能上肯定是不如这个红黑树。这个简单的红黑二叉树在《算法》第四版有介绍，掌握完之后再看这个简单的红黑二叉树，就会觉着简单 easy。 **
最后的最后的最后，一定要尝试着自己推导一下插入删除规则啊，不然经常忘，是睡一觉起来再看就有点懵逼的那种忘。
插入：
RB-INSERT(T, z)
y ← nil[T] // 新建节点“y”，将y设为空节点。
x ← root[T] // 设“红黑树T”的根节点为“x”
while x ≠ nil[T] // 找出要插入的节点“z”在二叉树T中的位置“y”
do y ← x
if key[z] < key[x]
then x ← left[x]
else x ← right[x]
p[z] ← y // 设置 “z的父亲” 为 “y”
if y = nil[T]
then root[T] ← z // 情况1：若y是空节点，则将z设为根
else if key[z] < key[y]
then left[y] ← z // 情况2：若“z所包含的值” < “y所包含的值”，则将z设为“y的左孩子”
else right[y] ← z // 情况3：(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子”
left[z] ← nil[T] // z的左孩子设为空
right[z] ← nil[T] // z的右孩子设为空。至此，已经完成将“节点z插入到二叉树”中了。
color[z] ← RED // 将z着色为“红色”
RB-INSERT-FIXUP(T, z) // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转，让树T仍然是一颗红黑树
RB-INSERT-FIXUP(T, z)
while color[p[z]] = RED // 若“当前节点(z)的父节点是红色”，则进行以下处理。
do if p[z] = left[p[p[z]]] // 若“z的父节点”是“z的祖父节点的左孩子”，则进行以下处理。
then y ← right[p[p[z]]] // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”
if color[y] = RED // Case 1条件：叔叔是红色
then color[p[z]] ← BLACK ▹ Case 1 // (01) 将“父节点”设为黑色。
color[y] ← BLACK ▹ Case 1 // (02) 将“叔叔节点”设为黑色。
color[p[p[z]]] ← RED ▹ Case 1 // (03) 将“祖父节点”设为“红色”。
z ← p[p[z]] ▹ Case 1 // (04) 将“祖父节点”设为“当前节点”(红色节点)
else if z = right[p[z]] // Case 2条件：叔叔是黑色，且当前节点是右孩子
then z ← p[z] ▹ Case 2 // (01) 将“父节点”作为“新的当前节点”。
LEFT-ROTATE(T, z) ▹ Case 2 // (02) 以“新的当前节点”为支点进行左旋。
color[p[z]] ← BLACK ▹ Case 3 // Case 3条件：叔叔是黑色，且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
color[p[p[z]]] ← RED ▹ Case 3 // (02) 将“祖父节点”设为“红色”。
RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 // (03) 以“祖父节点”为支点进行右旋。
else (same as then clause with "right" and "left" exchanged) // 若“z的父节点”是“z的祖父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
color[root[T]] ← BLACK
删除
RB-DELETE(T, z)
if left[z] = nil[T] or right[z] = nil[T]
then y ← z // 若“z的左孩子” 或 “z的右孩子”为空，则将“z”赋值给 “y”；
else y ← TREE-SUCCESSOR(z) // 否则，将“z的后继节点”赋值给 “y”。
if left[y] ≠ nil[T]
then x ← left[y] // 若“y的左孩子” 不为空，则将“y的左孩子” 赋值给 “x”；
else x ← right[y] // 否则，“y的右孩子” 赋值给 “x”。
p[x] ← p[y] // 将“y的父节点” 设置为 “x的父节点”
if p[y] = nil[T]
then root[T] ← x // 情况1：若“y的父节点” 为空，则设置“x” 为 “根节点”。
else if y = left[p[y]]
then left[p[y]] ← x // 情况2：若“y是它父节点的左孩子”，则设置“x” 为 “y的父节点的左孩子”
else right[p[y]] ← x // 情况3：若“y是它父节点的右孩子”，则设置“x” 为 “y的父节点的右孩子”
if y ≠ z
then key[z] ← key[y] // 若“y的值” 赋值给 “z”。注意：这里只拷贝z的值给y，而没有拷贝z的颜色！！！
copy y's satellite data into z
if color[y] = BLACK
then RB-DELETE-FIXUP(T, x) // 若“y为黑节点”，则调用
return y
RB-DELETE-FIXUP(T, x)
while x ≠ root[T] and color[x] = BLACK
do if x = left[p[x]]
then w ← right[p[x]] // 若 “x”是“它父节点的左孩子”，则设置 “w”为“x的叔叔”(即x为它父节点的右孩子)
if color[w] = RED // Case 1: x是“黑+黑”节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
then color[w] ← BLACK ▹ Case 1 // (01) 将x的兄弟节点设为“黑色”。
color[p[x]] ← RED ▹ Case 1 // (02) 将x的父节点设为“红色”。
LEFT-ROTATE(T, p[x]) ▹ Case 1 // (03) 对x的父节点进行左旋。
w ← right[p[x]] ▹ Case 1 // (04) 左旋后，重新设置x的兄弟节点。
if color[left[w]] = BLACK and color[right[w]] = BLACK // Case 2: x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
then color[w] ← RED ▹ Case 2 // (01) 将x的兄弟节点设为“红色”。
x ← p[x] ▹ Case 2 // (02) 设置“x的父节点”为“新的x节点”。
else if color[right[w]] = BLACK // Case 3: x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
then color[left[w]] ← BLACK ▹ Case 3 // (01) 将x兄弟节点的左孩子设为“黑色”。
color[w] ← RED ▹ Case 3 // (02) 将x兄弟节点设为“红色”。
RIGHT-ROTATE(T, w) ▹ Case 3 // (03) 对x的兄弟节点进行右旋。
w ← right[p[x]] ▹ Case 3 // (04) 右旋后，重新设置x的兄弟节点。
color[w] ← color[p[x]] ▹ Case 4 // Case 4: x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。
color[p[x]] ← BLACK ▹ Case 4 // (02) 将x父节点设为“黑色”。
color[right[w]] ← BLACK ▹ Case 4 // (03) 将x兄弟节点的右子节设为“黑色”。
LEFT-ROTATE(T, p[x]) ▹ Case 4 // (04) 对x的父节点进行左旋。
x ← root[T] ▹ Case 4 // (05) 设置“x”为“根节点”。
else (same as then clause with "right" and "left" exchanged) // 若 “x”是“它父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
color[x] ← BLACK
PS：后续节点是指左子树的最右子或者右子树的最左子。
黑+黑的意思是：“上面的修复情况看起来有些复杂，下面我们用一个分析技巧：我们从被删节点后来顶替它的那个节点开始调整，并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的节点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父节点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这重额外的黑色，原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。”–saturnman。
RB-DELETE-FIXUP的思想是：将x所包含的额外的黑色不断沿树上移(向根方向移动)，直到出现下面的姿态：
a) x指向一个”红+黑”节点。此时，将x设为一个”黑”节点即可。
b) x指向根。此时，将x设为一个”黑”节点即可。
c) 非前面两种姿态。
参考https://www.cnblogs.com/skywang12345/p/3245399.html
http://blog.csdn.net/v_JULY_v/article/details/6105630
B树：
定义：
知乎总结：（https://www.zhihu.com/question/30527705）
AVL树：最早的平衡二叉树之一，应用相对其他数据结构比较少，windows对进程地址空间的管理使用到了AVL树。
红黑树：平衡二叉树，广泛用在C++的STL中，如map和set都是用红黑树实现的。
B/B+树：磁盘文件组织，数据索引和数据库索引。
Trie树（字典树）：用在统计和排序大量字符串，如自动机。