红黑树是60年代中期计算机科学界找寻一种算法复杂度稳定，容易实现的数据存储算法的产物。在优先级队列、字典等实用领域都有广泛地应用，更是70年代提出的关系数据库模型--B树的鼻祖。在Linux kernel中，高精度定时器也工作在红黑树之上。为便于初学者掌握其基本算法，本文一步一步地演示了红黑树的创建过程。
首先回顾一下红黑树的基本性质：
1. 红黑树本质上是一个二叉查找树（BST），但是它从根到最远叶子的长度不会超过到最近叶子长度的两倍，因此是近似平衡的。
2. 红黑树的节点不是黑的就是红的，不会有第三种颜色。
3. 树根必须是黑色。
4. 叶子所指的空节点必须是黑色。
5. 如果某个节点是红色，那么它的两个儿子必须都是黑色。
6. 从任意节点出发的所有向下的路径上包含相同个数的黑节点。这个个数我们称为黑高度Bh。
有了上面的认识，我们要从无到有构造一颗红黑树的话，心里就有底了。这个构造的过程可以分两步：
第一步：执行BST的插入算法；
第二步：对节点着色；
第一步不会有什么问题，关键是第二步怎么对节点着色才不会违反红黑树的基本性质；
这是一个难点，我在写这篇文章的时候脑子也卡了一下，节点不多的时候好办，但是如果节点很多了，就必须找到一种普遍适用的算法来处理。通过这两天的观察，我发现这六条性质中最关键的其实是最后一条---从任意结点出发的任意路径黑高度相等！这才是红黑树算法保持近似平衡的精华所在！其它性质要么是这条性质的产物，要么就是为这条性质服务的。
现在我演示一下怎么从无到有生成一棵红黑树。
例如我们有一组数：{9，7，15，6，11，19}，现在按照从左到右的顺序存放在一颗红黑树中。
第一个数是9，很自然地成为了树根，如图：
图-1
每个新节点都默认地被渲染成了红色，为什么要这么做呢？后面我们将会看到它的好处！现在先忽略不谈。
根节点9是红色，这违背了性质3，所以必须改成黑色，如图：
图-2
下一个数字是7，显然要被插入到9的左边，并且这时满足红黑树的所有性质，如图:
图-3
下一个数字是15，要插入到9的右边，并且也满足红黑树的所有性质，如图：
图-4
下一个数字是6，要插入到7的左边，这回似乎有麻烦了，性质5被违背了，如图：
图-5
可能有人会说，那很简单，既然违背了性质5，那我改一下6的颜色不就OK了？
图-6
现在，恭喜你---也走进了我曾经走过的误区：）你的无意之举改变了新增节点路径上面的黑高度，这棵树已经不是红黑树了！
写代码的人都知道，对树的遍历，最简单的方法就是递归，那么树的数学模型就是一个可穷举的递归式。递归式中每一步的正确性都建立在前一步正确的基础之上。现在我们回过头来想想为什么每次插入的新节点都被渲染成红色呢？你肯定猜到了，因为我们要保证红黑树的核心性质--黑高度不发生变化，虽然牺牲了性质5，但这是可以补救的，并且代价很小。再来看看图-5
既然我们不能通过改变新插入节点的颜色来维持红黑树的性质，那么就只好从原来的树结构入手了。
我们注意到新插入的节点的父亲是一个红节点，其叔叔也是一个红节点。那么假如我把它的父亲改成黑色，则恢复了性质5，可是从树根出发的黑高度还是不相等，干脆把它的叔叔也改成黑色吧！结果如下：
图-7
现在它满足红黑树所有的性质。好了，我们继续。
插入数字11和19的过程平淡无奇，不深入探讨，最终的树如图：
图-8
如果现在要插入数字10怎么办？它肯定会是11的左节点：
图-9