正文
简介红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
简介#
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。
红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。
由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。
特征#
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。3 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
* 性质1. 节点是红色或黑色。 * 性质2. 根节点是黑色。 * 性质3. 所有叶子都是黑色。（叶子是NUIL节点） * 性质4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点） * 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
是性质4导致路径上不能有两个连续的红色节点确保了这个结果。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
因为红黑树是一种特化的二叉查找树，所以红黑树上的只读操行与普通二叉查找树相同。
用途#
- 红黑树在Linux非实时任务调度中的应用
Linux 的稳定内核版本在 2． 6． 24 之后，使用了新的调度程序 CFS，所有非实时可运行进程都以虚拟运行时间为 key 值挂在一棵红黑树上，以完成更公平高效地调度所有任务。CFS 弃用 active /expired 数组和动态计算优先级，不再跟踪任务的睡眠时间和区别是否交互任务，并且在调度中采用基于时间计算键值的红黑树来选取下一个任务，根据所有任务占用 CPU 时间的状态来确定调度任务优先级。
- 红黑树在Linux虚拟内存中的应用
32 位 Linux 内核虚拟地址空间划分 0 － 3G 为用户空间，3 － 4G 为内核空间，因此每个进程可以使用 4GB的虚拟空间。同时，Linux 定义了虚拟存储区域( VMA) 以便于更好表示进程所使用的虚拟空间，每个 VMA是某个进程的一段连续虚拟空间，其中的单元具有相同的特征，所有的虚拟区域按照地址排序由指针链接为一个链表。当发生缺页中断时搜索 VMA 到指定区域时，则需要频繁操作，因此选用了红黑树以减少查找时间。
- 红黑树在检测树的平衡性上的应用
红黑树是一种自平衡二叉搜索树，它的每个节点都被“着色”为红色或者黑色，这些节点的颜色被用来检测树的平衡性。红黑树作为嵌入式数据库中的索引机制，可以获得更好的性能，对于SQLite数据库，可以采用红黑树实现索引机制的优化。
