红黑二叉树
1.红黑树的产生
在网上查找的各种关于红黑树的博客，一般就直接把红黑树的五个性质摆上，直接开始介绍，但并不说为什么要使用遵循这些规则性质，为什么会产生他。最近在看《算法》正好看到了红黑二叉树，在此总结一下。
在了解二叉树前必须先提一下2-3树
2-3树就是既有2节点又有3节点的树。在我们使用二叉查找树时，不能保证其总在最优情况，也就是保证其为一个平衡的二叉树，只有这时他的查找时间复杂度才是nlogn, 而他在最坏情况下，很有可能事件复杂度变成n，也就是变成了链表。如下情况：
所以一般的二叉查找树并不稳定，于是就出现了2-3树。2-3树的插入分许多不同的情况，十分复杂。也正是因为2-3树插入时所做的各种规定改变，使得2-3树最终是会自平衡的，从而达到平衡二叉树的目的。
实现这些不仅需要大量的代码，而却它们所产生的而外开销会可能使算法比标准的二叉查找树更慢。平衡一棵树的初衷是为了消除最坏情况，单我们希望这种保障所需要的代码能够越少越好。于是，就有了红黑树
所以红黑树是2-3树的变形，以2-3树的角度去理解红黑树就容易多了
2.介绍
红黑二叉树背后的基本思想时用标准的二叉查找树（全是2节点）和一些额外的信息（用红黑节点来代替3节点）来表示2-3树。实现：
- 红链接将两个2节点连起来构成3节点
- 黑链接则是2-3树中的普通链接
（有些地方称之为红黑节点，将3节点的第一个元素，作为第二个元素的左节点，并用红色的线连接，此时红色线连接的节点就相当于红色。）
于是红黑二叉树和2-3树的等价的定义：
- 红链接均为左链接
- 没有任何一个节点同时和两条红链接相连
- 该树是完美黑色平衡的，即任意空连接到根节点的路径上黑节点的数量相同
满足这些条件的红黑树就和2-3树一一对应：如果将红链接画平，那么所有空连接到根节点的路径相同（高度相同），将红链接合并，得到的就是一颗2-3树。这样既保证了二叉树的平衡，又能使用普通二叉树的查找方法，代价很小。变换修复方式：
这两种变换都是局部性的，不会影响到整棵树的黑色平衡性其实这些变换都是与2-3树里的插入时需要的变换是一一对应的，只不过红黑二叉树用红黑链将其简化，所以要是不知道这些变换的原因，就请先去学习2-3树的插入变换1.旋转
在实现某些操作时很可能出现红色有链接后者两条连续的红链接，或两条连续的红链接。所以我们需要对这种情况进行修复： - 左旋转： 需要将一条红色有链接转换为左链接，
- 右旋转：相反
2.颜色转换：
- 将两个子节点的颜色变黑，同时将父节点的颜色由黑变红。注意当根节点为红色时我们需要把他变黑，（也就是说根节点总是黑色）这是树的黑链接高度+1（原因参考2-3树的建立）
3. 操作
因为这些变换都是局部的，所以我们只需递归的执行即可，只需执行左旋转，右旋转和颜色变化呢这三种简单操作，即可保证插入后的红黑树和2-3树一一对应，沿着插入点到根节点的路径向上移动时所经过的每个节点中顺序完成以下操作：
- 如果右节点是红色而作节点是黑色，则进行左旋转；
- 如果左节点是红色的且它的左子节点也是红色，进行右旋转
- 如果左右节点均为红色，则进行颜色变化
仅仅上面三个简单操作就可已概括复杂的2-3树插入时的各种情况
最后
- 上述方法的代码实现均可在《算法》一书中找到，大部分结论方法也均出自此书中，有兴趣的可自行参考
- 一篇很好的讲解2-3树的实现的博客从2-3树理解红黑树