简介

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树. [4]

树的左旋(2张)

质。

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

如右图。

1.节点插入算法

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

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； } [2] 

对上述算法分析，如果新插入的是黑色节点，那么它所在的路径上就多出一个黑色的节点，所以新插入的节点一定要设成红 色。 但是如果 z 的父节点也是红色，这就违反了每个红色节点的两个子节点都黑色的性质。 [2] 

2.节点删除算法

与红黑树的的插入算法一样，对一个节点的删除算法要花 O(log n)时间，只是删 除算法略微复杂些，删除算法如下： [2] 

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 指向代替删除节点的节点 */ } [2] 

对以上算法分析，若删除的节点是红色，则不做任何操作，红黑树的任何属性都不会被破坏；若删除的节点是黑色的，显然它所 在的路径上就少一个黑色节点，红黑树的性质就被破坏了，这时执行一个 Delete-Fixup（）来修补这棵树。 一个节点被删除之后，一定 有一个它的节点代替了它的位置，即使是叶节点被删除后，也会有一个空节点来代替它的位置。 设指针 x 指向这个代替位置的节 点，同时引入指向 x 兄弟的指针 w，这里均假设 x 是 x->parent 的左子节点，则 w 是 x->parent 的右子节点，如果实际遇到相反的情 况，只要把所有操作中的左、右 互反一下就可以了。

（图一图二如下）

图2 Delete-Fixup（T，x）修补过程示意图

图1 Insert-Fixup(T,z)修补过程示意图

红黑树

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