平衡搜索树（BST），所有操作的Θ(lgn)
（平衡树有可能不是二叉树，这一节只讨论二叉树的情况）
有多重平衡树结构
- AVL trees
- 2-3 trees
- 2-3-4 trees
- B trees
- Red-black trees
- Skip lists
- Treaps
红黑树 Red-black trees
BST的一种
- 每个结点有一个色域，要么为黑结点，要么为红结点
- 根节点和叶子结点都为黑结点
- 每个红结点的父亲都为黑结点，即不可能出现两个红色结点相连的情况
- 从根节点到任意叶节点的路径中的黑色结点数目相等，这个数目也称为黑高度
由以上性质，可以保证红黑树的高度为O(lgn)
Example.
证明
将红黑树的所有红结点，都与其父节点（黑）合并，可以得到一颗2-3-4 tree（即每个结点的子节点数目为2~4个）
并且所有节点的高度都是黑节点的高度，也就是所有叶子节点有相同的深度，意味着树是平衡的
假设整棵树高度为h，那么叶子结点数应为h2~h4
原红黑树的叶子结点个数为带键值结点个数n+1（平衡树叶子节点的数量总是内部节点的数量加1）
leaf = n+1 | n是key的数量
=> h'2 <= n+1 <= h'4
=> h' <= lg n+1
树最高情况是红黑相间的时候，因此其高度最高只有h <= 2h' <= 2lg n+1
树的高度为O(lgn)
树操作
红黑树的查询操作和普通BST一样，删除和插入操作则相对复杂
我们要保证红黑树的性质，因为这些性质是红黑树为平衡树的保证，能够保证红黑树的高度为Olgn，这样红黑树的基本操作都可以保证在O(lgn)的时间复杂度内完成
为了保持红黑性需要三种操作
- BST操作
- 改变节点颜色
- 利用旋转改变节点关系
旋转
保持二叉搜索树的性质，并且只需要常数时间
LEFT_ROTATE(T,x)
y = right[x] //获取右孩子
rihgt[x] = left[y] //设置x的右孩子为y的左孩子
if left[y] != NIL
then parent[left[x]] = x
parent[y] = parent[x] //设置y的父节点为x的父节点
if parent[x] == NIL
then root[T] = y
else if x==left[parent[x]
then left[parent[x]] = y
else right[[parent[x]] = y
left[y] = x //设置y的左孩子为x
parent[x] =y
插入
插入一个新结点的过程是在二叉查找树插入过程的基础上改进的，先按照二叉排序的插入过程插入到红黑树中，然后将新插入的结点标记为红色（插入黑色会影响树的深度，很容易破坏红黑性质，标记红色只可能影响性质3）。然后调整结点并重新着色，使得满足红黑树的性质。
如果每次插入新的结点z导致红黑树性质被破坏，最多只有一个性质被破坏，并且不是性质2就是性质4。违反性质2是因为z是根且为红色，只需要改变跟节点的颜色，违反性质4是因为z和其父节点parent[z]都是红色的。
以下分析的大前提是z的父结点是红色，建立在z的父结点是左孩子基础上（相反情况类似，不做分析）
插入后有多种情况
情况1：z的叔叔结点y是红色的
此时父节点parent[z] A和叔叔节点y D都是红色的，解决办法是将z的父节点parent[z] A和叔叔结点y D都变为黑色，将z的祖父结点parent[parent[z]] C变为红色，然后从祖父结点parent[parent[z]] C继续向上判断是否破坏红黑树的性质
情况2：z的叔叔y是黑色的，而且z是右孩子
情况3：z的叔叔y是黑色的，而且z是左孩子
情况2和情况3中叔叔节点y D都是黑色的，通过z是左孩子还是右孩子进行区分的。可以将情况2通过旋转为情况3。情况2中z是右孩子，旋转后成为情况3，使得z变为左孩子，可以在parent[z]结点出使用一次左旋转来完成。
无论是间接还是直接的通过情况2进入到情况3，z的叔叔y总是黑色的。在情况3中，将父节点parent[z] B着为黑色，祖父节点parent[parent[z]] C着为红色，然后从祖父节点parent[parent[z]] C处进行一次右旋转。
RB_INSERT(T,z)
y = NIL
x =root(T)
while x != NIL
do y=x
if key[z]<key[x]
then x=left[x]
else x=right[x]
parent[z] = y
if y =NIL
then root =z
else if key[z] < key[y]
then left[y] =z
else right[y] =z
left[z] = NIL
right[z] =NIL
color[z] = RED //新插入结点标记为红色
RB_INSERT_FIXUP(T,z) //进行调整，使得满足红黑树性质
RB_INSERT_FIXUP(T,z)
while color[parent[z]] = RED
do if parent[z] == left[parent[parent[z]]]
then y = right[parent[parent[z]]]
if color[y] == RED //情况1，z的叔叔为红色
then color[parent[z]] = BLACK
color[y] = BLACK
color[parent[parent[z]]=RED
z= parent[parent[z]]
else if z == right[parent[z]] //情况2，z的叔叔为黑色，z为右孩子
then z = parent[z]
LEFT_ROTATE(T,z)
color[parent[z]]=BLACK //情况3，z的叔叔为黑色，z为左孩子
color[parent[parent[z]] = RED
RIGHT_ROTATE(T, parent[parent[z]])
else (same as then clause with “right” and “left” exchanged)
color(root(T)) = BLACK; //将根结点设置为黑色
