红黑树

自平衡二叉查找树

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

简介

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低，其平均统计性能要强于 AVL 。

由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

特征

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 结点是红色或黑色。

性质2. 根结点是黑色。

性质3. 所有叶子都是黑色。（叶子是NIL结点）

性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

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

是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。

因为红黑树是一种特化的二叉查找树，所以红黑树上的只读操作与普通二叉查找树相同。

树的旋转

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。

为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。

如右图。

1.结点插入算法

插入过程首先是根据一般二叉查找树的插入步骤，把新结点插入到某个叶结点的位置上，然后将 z 着为红色。为了保证红黑树的性质能继续保持，再对有关结点重点着色并旋转，其插入算法如下：

RB-INSERT (T,z) {

1 按二叉查找树的插入步骤将结点 z 插入到 T 中；

2 color[z]=RED；

3 while(z 不是根结点 &&color[z->parent]= =RED) {Insert-Fixup(T,z);}

4 color[root[T]]=BLACK； }

对上述算法分析，如果新插入的是黑色结点，那么它所在的路径上就多出一个黑色的结点，所以新插入的结点一定要设成红色。但是如果 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 的右子结点，如果实际遇到相反的情况，只要把所有操作中的左、右互反一下就可以了。

（图一图二如下）

操作

在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也是二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更（这在实践中是非常快速的）并且不超过三次树旋转（对于插入是两次）。这允许插入和删除保持为 O（log n)）次，但是它导致了非常复杂的操作。

用途

1.Linux非实时任务调度中的应用

Linux 的稳定内核版本在 2． 6． 24 之后，使用了新的调度程序 CFS，所有非实时可运行进程都以虚拟运行时间为 key 值挂在一棵红黑树上，以完成更公平高效地调度所有任务。CFS 弃用 active /expired 数组和动态计算优先级，不再跟踪任务的睡眠时间和区别是否交互任务，并且在调度中采用基于时间计算键值的红黑树来选取下一个任务，根据所有任务占用 CPU 时间的状态来确定调度任务优先级。

2.Linux虚拟内存中的应用

32 位 Linux 内核虚拟地址空间划分 0 － 3G 为用户空间，3 － 4G 为内核空间，因此每个进程可以使用 4GB的虚拟空间。同时，Linux 定义了虚拟存储区域( VMA) 以便于更好表示进程所使用的虚拟空间，每个 VMA是某个进程的一段连续虚拟空间，其中的单元具有相同的特征，所有的虚拟区域按照地址排序由指针链接为一个链表。当发生缺页中断时搜索 VMA 到指定区域时，则需要频繁操作，因此选用了红黑树以减少查找时间。

3.检测树的平衡性上的应用

红黑树是一种自平衡二叉搜索树，它的每个结点都被“着色”为红色或者黑色，这些结点的颜色被用来检测树的平衡性。红黑树作为嵌入式数据库中的索引机制，可以获得更好的性能，对于SQLite数据库，可以采用红黑树实现索引机制的优化。

数据结构简述

它的统计性能要好于平衡二叉树（有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树），因此，红黑树在很多地方都有应用。目前，基于拥有上述特性，红黑树已广泛应用Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪等一系列场景中。其他平衡树还有：AVL，SBT，伸展树，TREAP等等。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省