最近博客一直断更，一时想不到要写什么比较好。这次趁着刚刚学完红黑树的机会，就开篇文章谈谈红黑树吧。
相信稍微对于数据结构都些了解的人都了解过二叉搜索树，二叉搜索树的优点很明显，就是在树基本平衡的情况下（每个分支的深度都差不多）的情况下，对于树节点的增删改查在对数时间（O(lgN))内就能够完成。但是其缺点也很明显，就是必须要在 平衡 的情况下，才能有这么高的效率，如果树只向一个方向增长（最坏情况）的话，其效率就变得和线性表一样了，甚至还要低下。
平衡二叉树和不平衡二叉树比较
于是，就有人想要发明一种能够在最坏情况下仍然拥有对数时间的效率的数据结构，“自平衡二叉查找树”便诞生了。英文名叫做"Balanced tree",简称B树hhh。说这么多，估计各位心里仍然没有一点B树Orz。其实所谓平衡树，就是在插入，删除的时候，使用一些树的变换手段（一般是旋转），来使树达到平衡的数据结构，其本质仍然是一棵二叉搜索树。
最早提出的平衡树是AVL树，但是由于种种原因，其并未得到工业界的广泛使用，具体介绍由于篇幅限制这里就不展开了，有兴趣的读者可以自行搜索。目前工业界最为广泛使用的平衡树,便是本次要介绍的红黑树，但为了让我们更容易实现红黑树，我在此并不直接介绍红黑树，而是效率和红黑树差不多的一种变体——左倾红黑树。
在介绍红黑树之前，请让我先介绍一种和红黑树等价的数据结构：”2-3树”。这种树是有点像二叉搜索树，但是又有些不同，重点在于其有两种节点，一种节点和二叉树一样，有一个键和两条指向子节点的链接。另外一种就比较厉害了，他有两个键和三条链接，这三条链接分别指向：同时小于两个键的节点，大小在两个键之间的节点，以及同时大于两个键的节点。
当插入一个键的时候，首先对这个键进行搜索，按照二叉树的方法找到插入的位置，如果要插入的位置在一个2-节点，那就好办了，只要插入这个节点中合适的位置，让这个节点变成3-节点，这样做的话树的平衡性并没有改变。但如果插入的位置已经是一个3-节点的话，事情就变得有些棘手，我们必须在不改变树的平衡性的前提下完成插入操作。
我们可以首先将这个键插入3-节点，变成一个临时的4-节点，然后，沿着根的方向，依次分解遇到的4-节点。将4-节点中的处于中间大小的键放到他的父节点中。这样依次进行变换，一直到根节点，如果遇到根节点也变成了4-节点的情况，就可以直接将这个4-节点拆成三个2-节点，这样做的话，树的每条分支增长的速度就是一样的了，因为树由从上向下生长改为了 从下向上 生长。
2-节点和3-节点