漫游红黑树之插入篇

http://www.cnblogs.com/xuqiang/archive/2011/05/16/2047001.html

 

<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. 如果新插入的节点的父节点是红色的话，显然这里违反了红黑树中不能存在父节点和子节点同时为红色的性质，。

 

于是需要调整，我们的调整的目标是在不违反红黑树性质（或者是可调整）如何将两个相邻的红色节点分隔开来，显然最终的结果是我们需要将新插入的节点的父节点更改成黑色（新插入节点是如法作出调整的，实现将两个红色节点分割开的，除非将该节点标识为黑色，但是这会增加黑高度），但是如果是单纯的修改父节点为黑色的话，那么将会违背黑色顶点数目的性质，直接修改是行不通，那么能否通过交换两个两个节点达到目的呢？

显然新插入的节点的祖父节点一定是黑色的，那么是否能够通过交换父节点和祖父节点的红黑性质来达到目的呢？显然这可能违反将新插入节点的叔叔子树的红黑树性质破坏掉。但是如果叔叔节点是红色的话，问题似乎变得很简单了。 

 

我们仅仅需要将主父节点改成红色，同时将父节点和叔叔节点改成黑色即可。

 

但是这将引入新的问题， 显然我们将G节点表示成红色之后，那么G节点和G的父节点是可能违反红黑性质的，为了解决这个问题，这里使用尾递归的形式来对节点G进行调整。

void insert_case3(struct node *n)
{
        struct node *u = uncle(n), *g;
 
        if ((u != NULL) && (u->color == RED)) {
                n->parent->color = BLACK;
                u->color = BLACK;
                g = grandparent(n);
                g->color = RED;
                insert_case1(g);
        } else {
                insert_case4(n);
        }

}  

一种情况已经解决。下面将是更加艰巨的任务，如果叔叔节点是黑色的，该如何是好？

 case 4：我们来看看还剩下的就是这种情况了，P为红色，U为黑色，G为黑色，怎么解决？对了，到这里是否忘了我们的最终目的是什么？

 在不违反红黑树性质（或者是可调整）如何将两个相邻的红色节点分隔开来. 

 

 

直接将P节点修改成黑色是不行的，这将增加G-P-U路径上的黑高度， 没有思路，好的，来回头看看case 3的情况，毕竟已经解决了一种情况，case 3中我们修改了节点G的颜色，为什么能够修改，显然是说G是最顶点（辈份最高）的节点，最顶点的节点的颜色可以是红色（重新调整）或者是黑色。

那如果我们呢将P节点提升至现在G的位置呢（通过树的旋转）？

 

现在可以将P的颜色标识成黑色，但是会破坏P-G-U的黑路径，运用一下交换的思想吧，交换P和G的颜色即可。

现在基本上已经解决了红黑树中如果叔叔是黑色的情况，剩下的工作就是分析旋转方向，根据节点P和N是左孩子还是右孩子进行相应旋转。

这是case 4情况：

 

或者是：

 

void insert_case4(struct node *n)
{
        struct node *g = grandparent(n);
 
        if ((n == n->parent->right) && (n->parent == g->left)) {
                rotate_left(n->parent);
                n = n->left;
        } else if ((n == n->parent->left) && (n->parent == g->right)) {
                rotate_right(n->parent);
                n = n->right;
        }
        insert_case5(n);

} 

这样将P和U不再同一条直线的情景转换成在统一条直线上的情况，case 5我们处理在同一条直线上的情况：

case 5：

 

或者是：

 

void insert_case5(struct node *n)
{
        struct node *g = grandparent(n);
 
        n->parent->color = BLACK;
        g->color = RED;
        if ((n == n->parent->left) && (n->parent == g->left)) {
                rotate_right(g);
        } else { /* (n == n->parent->right) and (n->parent == g->right) */
                rotate_left(g);
        }

}  

红黑树的插入的所有情况分析完了，也就是说我们的分类讨论是完整的吗？

 

好的，看来我们穷举了所有的红黑树的插入情况，红黑树插入漫游完毕。 这里有一个applet的动画演示，很生动。

<4>. 我的EasyCoding库 

最后说一说现在正在开发的一个基于c#语言算法实现库吧，正在开发之中，还存在很多技术上的难点（对我这种菜鸟而言），我给这个项目名了个不是很响亮的名字EasyCoding，基本的项目的结构：

 

Collections中主要是一些数据结构的实现，现在已经完成了Bag，Association，BinarySearchTree，HashList，Heap，PriorityQueue，VisitableHashtable，

VisitableLinkedList

，VisitableList，VisitableQueue，VisitableStack这些集合类，有一些是对.net集合类的重新封装，例如Visitable-XXX集合类的话，其内部使用的是.net提供的集合类，但是重新实现了访问者模式（主要是为了集合类的功能的拓展性），下面是Test项目中的一段代码，演示的是如何使用访问者模式对集合类进行功能拓展：

        [Test]
public void TestVisitor()
        {
            VisitableStack<int> stack = new VisitableStack<int>();
            stack.Push(2);
            stack.Push(4);
            stack.Push(9);
            stack.Push(3);

            ComparableFindingVisitor<int> visitor = new ComparableFindingVisitor<int>(9);
            stack.Accept(visitor);

            Assert.AreEqual(visitor.Found, true);

            visitor = new ComparableFindingVisitor<int>(5);
            stack.Accept(visitor);
            Assert.AreEqual(visitor.Found, false);
        }

 接下来打算开始实现一些比较复杂的数据结构，例如这里的红黑树，avl树，跳表，FibonacciHeap，图的顶层存储容器等。

Algorithm主要是算法库的实现，暂时完成了一些简单的排序算法，打算添加一些搜索算法和图论常见算法；

Test项目使用的是unuit测试框架对Collection和Algorithm进行测试；

Visualization主要是想完成数据结构和算法的可视化运行，暂时还未开始（技术上不熟练啊），打算是使用silverllght来做。

 

路漫漫其修远兮，继续吧。

<5>. 参考资料及代码下载 

http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

http://libredblack.sourceforge.net/ 

红黑树动态演示：http://secs.ceas.uc.edu/~franco/C321/html/RedBlack/redblack.html 

http://gauss.ececs.uc.edu/RedBlackTester/redblack.html 

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/red_black.html 

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/red_black_op.html

http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91 

http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx 

http://en.wikipedia.org/wiki/Red-black_tree#Operations