漫游红黑树之插入篇


		

1. 红黑树简介
2. 红黑树性质介绍
3. 漫游红黑树
4. 我的EasyCoding库
5. 参考资料及代码下载 
<1>. 红黑树简介 
红黑树是一种平衡的二叉查找树，是一种计算机科学中常用的数据结构，最典型的应用是实现数据的关联，例如map等数据结构的实现。1972年，鲁道夫贝尔最先发明，但是他称之为“对称二叉B树”，真正的称之为“红黑树”是在1978年Leo J. Guibas 和 Robert Sedgewick的一篇论文开始的。这么算起来，红黑树已经存在了将近30年，时至今日，仍旧另初学者头痛不已。
<2>. 性质简介
红黑树拓展了二叉查找树，给每个树的节点增加了一个Color属性，每个节点必须是红色或者是黑色，另外为了达到树的平衡，增加了如下的限制（下面是用“限制”来指明）：
1. 节点必须是红色或者是黑色
2. 根节点是黑色的，如果不是黑色，根据下面的性质4，将无法插入新节点
3. 所有的叶子节点是黑色的，这里可以增加哨兵元素，作为叶子节点，该节点是黑色，也就是说该条件是一定满足的。
4. 每个红色节点的两个子节点是黑色的，也就是不能存在父子两个节点全是红色
5. 从任意每个节点到其每个叶子节点的所有简单路径上黑色节点的数量是相同的。
上面的这些约束保证了这个树大致上是平衡的，这也决定了红黑树的插入，删除，查询等操作是比较快速的。 
<3>. 漫游红黑树 
很多初学者在学习红黑树时，总是首先查看别人的思路（比如《算法导论》等），然后基本上就陷入了泥潭，那么我们不妨静下心来自己想一想如果我去实现需要该怎么做？好的，准备好，开始漫游红黑树的？这里不仅仅是列出插入操作分为那些情况，更重要的是知道问什么这么分类？
好的，现在我们是一无所有，假设这是第一次插入一个节点，为了满足上面的1-5条性质，很显然仅仅需要很少量的操作即可：

生成一个新节点，并拷贝数据;
节点颜色表明为黑色;
 通过上面的操作生成的只有一个节点的树，满足1-5条性质，显然该树是红黑树。
 
 特殊情况考虑完成之后，下面假设又开始添加节点，我们面对的第一个问题是新增加的节点是标记成红色还是黑色？显然无论是新插入的节点是黑色或者是红色，红黑树限制1，2，3一定是满足的，那么如果将新插入的节点标识成黑色的话，可能违反5，但是如果将新插入的节点标识成红色，肯能违反4，看似好像是两个是类似的。
但是考虑这样的一种情况：如果新插入的节点标识成红色，并且新插入的节点的父节点是黑色，那么是违反性质4的，也就是说是不需要重新调整红黑树的。
 
但是如果标识成黑色的话，那么是一定会违反性质5，好的，我们还是选择将插入的节点标识成红色吧，至少运气好的话，就不需要重新调整红黑树了。 
 确定了新插入的节点的颜色之后，现在开始具体的实现插入操作，由于红黑树实际上也是一种二叉查找树，那么新插入的顶点一定是在红黑树的最低端，我们忽略掉这个查找节点的过程，这里仅仅关心插入节点之后如何调整红黑树。数学上的常用方法:分类讨论
case 1. 如果插入的节点是根节点，也就是说初始的红黑树为空，这是最简单的情况，直接将该节点标识成黑色即可。

 void insert_case1(struct node *n) 
{
        if (n->parent == NULL)
                n->color = BLACK;
        else
                insert_case2(n);
}
case 2. 如果新插入的节点不是红黑树的根节点，如果新插入的节点的父节点是黑色的话，那么红黑树是不需要调整的
 
代码：

void insert_case2(struct node *n)
{
        if (n->parent->color == BLACK)
                return; /* Tree is still valid */
        else
                insert_case3(n);

} 
case 3. 如果新插入的节点的父节点是红色的话，显然这里违反

补充：综合编程 , 其他综合 ,