红黑树（RBTree）之建树过程图解
【 声明：欢迎转载，请注明原文出处】
红黑树的应用广泛，包括操作系统线程调度时、STL中就会用到红黑数，红黑树检索的高效性深受编程人员的欢迎，下面介绍一下红黑树的基本定义，然后通过图解的方式来分析建立红黑树的过程，也就是使用插入操作的全过程。
我们知道二叉树指的是：任何节点最多只能有两个子节点的树。而二叉搜索树首先是一颗二叉树，且它的节点满足如下旋转规则是：任何节点的键值一定大于其左子节点树中的每个节点的键值，并小于其右子树中的每个节点的键值。
因此，从树节点一直往左走到底，即得最小元素；从根节点一直往右走到底，却得最大元素。
但若插入值无规律，二叉搜索树可能失去平衡，甚至变成链表，造成搜索效率低落的情况。解决办法就是尽量使树形左右“平衡”，对于何为“平衡”，没有一个绝对的定义，大致的意思就是“没有一个节点过深”。常见的平衡二叉树有AVL-tree, RB-tree, AA-tree，它们都比上面说的一般二叉树复杂，插入节点和删除节点时要做一些额外操作来维护树形平衡，但是它们可以避免极难应付的极不平衡的情况，而且由于它们总是保持某种程度的平衡，所以元素访问时间平均而言就比较少。
SGI STL实现的搜索树是RB-tree，它在一般二叉树的基础上增加了以下必须满足的条件：
1）每个节点不是红色就是黑色；
2）根节点为黑色；
3）如果节点为红，其子节点必须为黑，如果节点为黑，则随意；
4）任一节点至NULL（树尾端）的任何路径，所含的黑节点数量必须相同。
根据规则4，新增节点必须为红色；根据规则3，新增节点的父节点必须为黑。当新节点根据一般二叉树搜索规则到达其插入点，却未能符合上述条件时，就必须调整节点颜色和旋转树形。注意经过调整后，叶节点可能为黑色。【摘自STL源码剖析】
概念就先介绍到这儿，下面看看红黑树的建树过程吧，在这里以（10，15，20，5，8，3，30，40，25，35，38，36）这个序列为例进行建树操作：
由于一个节点时简单，直接从第2步开始。
step2：
step3：
虚线箭头所指代表新结点20将插入的位置，由于新结点的插入导致不满足条件3，进行左旋转，得到下面的图。当新结点需要插入时，根据规则4，新增节点必须为红色；再根据红黑树又是二叉搜索树，新结点的插入必须同时满足这两条件，然后根据红黑树的4条规则加以判断。下面的图就没有画出 应该插入哪个位置了，相信读者一看就知道插入点在哪。
step4：
step5：
step6：
step7：
step8：
step9：
step10：
step11：
step12：
step12有3个图，看的顺序是从左到右，从上到下，第一个图虚线箭头代表新结点36，第2个图是经过一次调整后的情形，第3个图是最终形成的图，也是整个序列通过插入所建立的红黑树。
另外说明一点，叶子结点的下一个结点是NULL（树尾端）。通过上面的图解过程，希望没有接触过红黑树的朋友有一个感性的认识，也是我在学习过程中的一点体会，希望能给大家一点帮助，因为本人水平有限，若此文存在漏洞或者错误，请读者留言，欢迎大家批评指正。
