教你透彻了解红黑树
本文参考：Google、算法导论、STL源码剖析、计算机程序设计艺术。
本人声明：个人原创，转载请注明出处。
推荐阅读：Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008.
直接下载：http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
一、红黑树的介绍
先来看下算法导论对R-B Tree的介绍：
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其
他路径长出俩倍，因而是接近平衡的。
前面说了，红黑树，是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质。
下面，在具体介绍红黑树之前，咱们先来了解下 二叉查找树的一般性质：
1.在一棵二叉查找树上，执行查找、插入、删除等操作，的时间复杂度为O（lgn）。
因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。
//至于n个结点的二叉树高度为lgn的证明，可参考算法导论 第12章 二叉查找树 第12.4节。
2.但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。
而红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。
ok，我们知道，红黑树上每个结点内含五个域，color，key，left，right。如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
下图所示，即是一颗红黑树：
此图忽略了叶子和根部的父结点。
二、树的旋转知识
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些结点的颜色及指针结构，以达到对红黑树进行
插入、删除结点等操作时，红黑树依然能保持它特有的性质（如上文所述的，五点性质）。
树的旋转，分为左旋和右旋，以下借助图来做形象的解释和介绍：
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 ys left subtree into xs right subtree.
3 p[left[y]] ← x
4 p[y] ← p[x] ▹ Link xs 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 ys left.
11 p[x] ← y
2.右旋
右旋与左旋差不多，再此不做详细介绍。
对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，
在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。
至于有些书如 STL源码剖析有对双旋的描述，其实双旋只是单旋的两次应用，并无新的内容，
因此这里就不再介绍了，而且左右旋也是相互对称的，只要理解其中一种旋转就可以了。
三、红黑树插入、删除操作的具体实现
三、I、ok，接下来，咱们来具体了解红黑树的插入操作。
向一棵含有n个结点的红黑树插入一个新结点的操作可以在O（lgn）时间内完成。
算法导论：
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)，将z插入红黑树T 之内。
为保证红黑性质在插入操作后依然保持，上述代码调用了一个辅助程序RB-INSERT-FIXUP
来对结点进行重新着色，并旋转。
14 left[z] ← nil[T]
15 right[z] ← nil[T] //保持正确的树结构
第16行，将z着为红色，由于将z着为红色可能会违背某一条红黑树的性质，
所以，在第17行，调用RB-INSERT-FIXUP（T,z）来保持红黑树的性质。
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
5 then color[p[z]] ← BLACK ▹ Case 1
6 color[y] ← BLACK ▹ Case 1
7 color[p[p[z]]] ← RED ▹ Case 1
8 z ← p[p[z]] ▹ Case 1
9 else if z = right[p[z]]
10 th
补充：软件开发 , Vc ,
