更新时间：2024-09-21 17:43
红黑树是一种自平衡二叉查找树。它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树，在1978年被Leo J. Guibas和Robert Sedgewick改称为“红黑树”。
红黑树的特点如下：每个节点非红即黑。黑色决定平衡，红色不决定平衡。这对应了2至3树中一个节点内可以存放1至2个节点。根节点总是黑色的。每个叶子节点都是黑色的空节点（NIL节点）。这里指的是红黑树都会有一个空的叶子节点，是红黑树自己的规则。如果节点是红色的，则它的子节点必须是黑色的（反之不一定）。通常这条规则也叫不会有连续的红色节点。一个节点最多临时会有3个节点，中间是黑色节点，左右是红色节点。从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。每一层都只是有一个节点贡献了树高决定平衡性，也就是对应红黑树中的黑色节点。
在Java集合框架中，很多部分（HashMap，TreeMap，TreeSet 等）都有红黑树的应用。
它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(包括set, multiset,map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。其他平衡树还有：AVL，SBT，伸展树，TREAP 等等。
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。
1.结点插入算法
插入过程首先是根据一般二叉查找树的插入步骤，把新结点 插入到 某个叶结点的位置上，然后将 z 着 为红色。为了保证红黑树的性质能继续保 持，再对有关结点重点着色并旋转，其插入算法如下：
RB-INSERT (T,z) {
1 按二叉查找树的插入步骤将结点 z 插入到 T 中；
2 color[z]=红色；
3 while(z 不是根结点 &&color[z->parent]= =RED) {Insert-Fixup(T,z);}
对上述算法分析，如果新插入的是黑色结点，那么它所在的路径上就多出一个黑色的结点，所以新插入的结点一定要设成红 色。但是如果 z 的父结点也是红色，这就违反了每个红色结点的两个子结点都黑色的性质。
2.结点删除算法
与红黑树的的插入算法一样，对一个结点的删除算法要花 O(log n)时间，只是删 除算法略微复杂些，删除算法如下：
RB-DELETE(T,z) {
1 if (z 的左右子结点均为NIL)
2 { NIL 结点代替 z 的位置； delete(z); }
3 else if (z 有一个子结点为 NIL)
4 {z 的非 NIL 子结点代替 z 的位置；delete(z); }
5 else
6 {将红黑树中序遍历中 z 的后继结点 s 的值赋给 z; delete(s); }
7 if (删除的结点是黑色的) Delete-Fixup(T,x); /*x 指向代替删除结点的结点 */ }
对以上算法分析，若删除的结点是红色，则不做任何操作，红黑树的任何属性都不会被破坏；若删除的结点是黑色的，显然它所 在的路径上就少一个黑色结点，红黑树的性质就被破坏了，这时执行一个 Delete-Fixup（）来修补这棵树。一个结点被删除之后，一定 有一个它的结点代替了它的位置，即使是叶结点被删除后，也会有一个空结点来代替它的位置。设指针 x 指向这个代替位置的结点，同时引入指向 x 兄弟的指针 w，这里均假设 x 是 x->parent 的左子结点，则 w 是 x->parent 的右子结点，如果实际遇到相反的情 况，只要把所有操作中的左、右 互反一下就可以了。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3. 每个叶节点（NIL节点，空节点）是黑色的。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点不包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用 "nil 叶子" 或"空(null)叶子"，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好象同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字地块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当起始位置的功能，它不是任何节点的儿子，我们称之为根节点或根。它有最多两个"儿子"，都是它连接到的其他节点。所有这些儿子都可以有自己的儿子，以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。
如果一个节点没有儿子，我们称之为叶子节点，因为在直觉上它是在树的边缘上。子树是从特定节点可以延伸到的树的某一部分，其自身被当作一个树。在红黑树中，叶子被假定为 null 或空。
由于红黑树也是二叉查找树，它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
1.Linux非实时任务调度中的应用
Linux 的稳定内核版本在 2． 6． 24 之后，使用了新的调度程序 CFS，所有非实时可运行进程都以虚拟运行时间为 key 只能挂在一棵红黑树上，以完成更公平高效地调度所有任务。CFS 弃用 active /expired 数组和动态计算优先级，不再跟踪任务的睡眠时间和区别是否交互任务，并且在调度中采用基于时间计算键值的红黑树来选取下一个任务，根据所有任务占用 CPU 时间的状态来确定调度任务优先级。
32 位 Linux 内核虚拟地址空间划分 0 － 3G 为用户空间，3 － 4G 内核空间，因此每个进程可以使用 4GB的虚拟空间。同时，Linux 定义了虚拟存储区域( VMA) 以便于更更地的表程序所所使用的虚拟空间，每个 VMA是某个进程的一段连续虚拟空间，其中的单元具有相同的特征，所有的虚拟区域按照地址排序由指针链接为一个链表。当发生缺页中断时搜索 VMA 到指定区域时，则需要频繁操作，因此选用了红黑树以减少查找时间。
3.检测树的平衡性上的应用
红黑树是一种自平衡二叉搜索树，它的每个结点都被“着色”为红色或者黑色，这些结点的颜色被用来检测树的平衡性。红黑树作为嵌入式数据库中的索引机制，可以获得更好的性能，对于SQLite数据库，可以采用红黑树实现索引机制的优化。
在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也是二叉查找树。但是，在插入和删除之后，红黑可能会变得变得违规。恢复红黑属少量时间要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次，但是它导致了非常复杂的操作。
红黑树.JavaGuide.2024-01-20
深入理解红黑树.iangeli.com.2024-01-20