好久没有写博客了。除了一部分的时间在做实验室的东西，其他的时间都在研究数据结构。每天的书桌上都放着两本砖头一般厚的书：一本是经典的算法导论，还有一本是带有一些c++描述的算法与数据结构。算法导论以前就看过一些，总体而言偏重于数学理论和思维逻辑，每个算式都是有理有据的推导，结论也十分的明确，但是推导的过程比较繁复，实现方面也是用的伪代码。照理说伪代码是最好的，可以翻译成各种语言的代码，但是同时它也是最没有针对性的，可以说不是任何一种代码，这时，后者就可以弥补这一方面的缺陷。
通过最近一段时间的学习，数据结构的内容已经完成过半。在学习的过程中，红黑树部分可以说是碰到的第一个让人有点喘不过气的部分，所以在学习的同时希望记录下来，以供后续阶段的复习回顾。
红黑树的介绍
算法导论对R-B Tree的介绍：
红黑树，一种二叉查找树，它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。
前面说了，红黑树是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质，所以在开始之前也有必要了解下二叉查找树的一般性质。二叉查找树满足下列性质：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
3）任意节点的左、右子树也分别为二叉查找树;
4）没有键值相等的节点（no duplicate nodes）。
所以在二叉查找树中执行查找、插入、删除等操作时，其时间复杂度满足下面的特点：（1）正比于O(lgn)（2）最坏可达到n。上述（1）特点是因为一棵随机构造的二叉查找树的高度为O(lgn)，而执行查找、插入、删除等操作的时间复杂度是和树高有关系的。（2）特点是由于构造时出现的特殊情况，比如一个从小到大顺序输入的数组，这时二叉查找树相当于一个n长链表，其高度为n，所以复杂度也是n。红黑树由于加上了一些限制条件，可以保证在最坏的情况下，上述操作的时间复杂度也保持在O(lgn)。那么下面我们就要看一看红黑树到底加了什么限制条件来保证这么好的性质。
一般来说，满足了下面的条件，我们才称其为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
上文中我们所说的叶结点或NULL结点，如上图所示，它不包含数据而只充当树在此结束的指示，这些节点在绘图中经常被省略。
红黑树的旋转
当对红黑树执行插入和删除等操作时，对树作修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。
树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。首先，介绍左旋操作。
如上图所示，当在某个结点pivot上，做左旋操作时，我们假设它的右孩子Y不是NIL，pivot可以为任何不是NIL的结点。左旋使Y成为该子树的新根，而Y的左孩子b则成为pivot的右孩子。
|
|
上述程序中，x代表结点类，其数据域中应该有left（左子指针）、right（右子指针）、p（父结点指针）、key（键值）、color（颜色）。
下面要介绍的是右旋，其实看示意图我们就可以看出，右旋和左旋是一个对称的关系。
如上图所示，当在某个结点pivot上，做右旋操作时，我们假设它的左孩子y不是NIL，pivot可以为任何不是NIL的结点。左旋使Y成为该子树的新根，而Y的右孩子c则成为pivot的左孩子。
|
|
我们从上面的解释上可以看到：树在经过左旋右旋之后，二叉搜索的性质保持不变，但红黑性质则被破坏了，所以，红黑树插入和删除数据后，需要结合旋转与颜色重涂来重新恢复树的红黑性质。
上述的内容参考了http://blog.csdn.net/v_JULY_v/article/details/6105630
版权：本文采用以下协议进行授权，自由转载 - 非商用 - 非衍生 - 保持署名 | Creative Commons BY-NC-ND 3.0，转载请注明作者及出处。