红黑树，并非想象中的那么复杂

红黑树是非常popular的一种self-adjusted的平衡二叉排序树。

通常他给我们的印象是很复杂，有很多case，要小心的旋转。有人说，曾将在某公司的面试时，被要求实现红黑树。他觉得这很没有道理，几乎很少有人能在不参考教科书的情况下，记清楚那么多的case。

在这一章里，我将向你展示目前我所见过的最简洁的红黑树实现。简洁到什么程度呢？我打赌你看过后能轻松通过上面的面试——Wow, 红黑树原来可以这么简单！

这个实现，来自Chris Okasaki在卡耐基梅隆大学(CMU)的博士研究成果。他启发我用同样的方法简洁地实现了AVL tree和Splay tree。

这一章我们讲红黑树，大致内容如下：
  1. 简介——我们看看普通的排序二叉树致命弱点，并且给出树旋转的概念；
  2. 红黑树的定义——我们看看为什么红黑树的性质能解决平衡问题，从而胜过排序二叉树；
  3. 插入——我们给出红黑树插入算法的数学定义，这里是本章的精华；
  4. 删除——删除本来不是个问题，但是我们要展示下删除比起插入有多复杂；
  6. 传统实现——我们看看传统实现的红黑树插入算法有多复杂，并做进一步的比较分析；传统实现的删除算法我们留作练习。
  7. 其他——多说两句

全文在
https://sites.google.com/site/algoxy/rbtree

附件是PDF版。

全部源代码在github可以获得：
https://github.com/liuxinyu95/AlgoXY