查找算法之红黑二叉查找树
红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-节点构成）和一些额外信息（替换3-节点）来表示2-3树。我们将树中的链接分为两种类型：红链接将两个2-节点连接起来构成3-节点，黑链接是2-3树中的普通链接。确切地说，我们将3-节点表示为由一条左斜的红色链接（两个2-节点其中之一是另一个的左子节点）相连的两个2-节点
定义
红黑树的另一种定义是含有红黑链接并满足下列条件的二叉树：
1、红链接均为左链接
2、没有任何一个节点同时和两条红链接相连
3、该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同
一一对应
我们将一棵红黑树的红链接画平，那么所有的空链接到根节点的距离都是相同的。如果我们将由红链接相连的节点合并，得到的就是一棵2-3树
旋转
左旋转
当红色链接出现在右链接的时候，必须要进行左旋转
右旋转
当出现两条连续的红链接时，进行右旋转。
颜色反转
当出现一个临时的4-node的时候，即一个节点的两个子节点均为红色，如下图
需要将E提升为父节点，就是把E对应的子节点的连线设置为黑色，自己的颜色设置为红色
插入
往一个2-node节点底部插入新的节点
首先我们看对于只有一个节点的红黑树，插入一个新的节点的操作：
这种情况很简单，只需要：
标准的二叉查找树遍历即可，新插入的节点标记为红色
如果新插入的节点在父节点的右子节点，则需要进行左旋操作。
往一个3-节点底部插入新的节点
先假设往只有两个节点的树中插入元素，如下图，根据待插入元素与已有元素的大小，可以分为三种情况：
有了以上基础，总结一下往3-节点底部插入新的节点的操作步骤，下面是典型的操作过程图：
步骤如下：
1、执行标准的二叉查找树插入操作，新插入的节点元素用红色标识。
2、如果需要对4-node节点进行旋转操作
3、如果需要，调用FlipColor方法将红色节点提升
4、如果需要，左旋操作使红色节点左倾
5、在有些情况下，需要递归调用