红黑树

定义：一棵二叉查找树如果满足下面的红黑性质，则为一棵红黑树：

         1）每个结点不是红的就是黑的

         2）根结点是黑的

         3）每个叶结点是黑的

         4）如果一个结点是红的，它的两个儿子都是黑的（即不可能有两个连续的红色结点）

         5）对于每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点

性质：

         这些约束确保了红黑树的关键特性: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

         要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的路径可能都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

来源与应用：

*1972年 由Rudolf Bayer发明的，他称之为“对称二叉B树”，它现代的名字是Leo J. Guibas和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

*红黑树多用在内部排序，即全放在内存中的，微软STL的map和set的内部实现就是红黑树。B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。

*在Linux中有很多地方用到了RD树。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。anticipatory, deadline, 和CFQ I/O调度都使用的是RB树进行请求跟踪，还有CD/DVD驱动的包管理也是如此。高精度计时器（high-resolutiontimer）使用RB树组织定时请求。

复杂度：

一棵有n个结点的红黑树的高度最多为2log(n+1)

操作：

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。

维基百科：红黑树