概述：本文从排序二叉树作为引子，讲解了红黑树，最后把红黑树和AVL树做了一个比较全面的对比。

1 排序二叉树

排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。 排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树： ? 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； ? 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； ? 它的左、右子树也分别为排序二叉树。 下图显示了一棵排序二叉树：

对排序二叉树，若按中序遍历就可以得到由小到大的有序序列。中序遍历得： {2，3，4，8，9，9，10，13，15，18} 排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插入节点集本身是大到小排列）；或所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种情况下，排序二叉树就变成了普通链表，其检索效率就会很差。

2 红黑树

《算法导论》关于红黑树的定义：

正如在CLRS中定义的那样（CLRS指的是就是算法导论这本书《Introduction to Algorithms》，CLRS是该书作者Cormen, Leiserson, Rivest and Stein的首字母缩写），一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：

1. 每个结点或者为黑色或者为红色。

2. 根结点为黑色。

3. 每个叶结点(实际上就是NULL指针)都是黑色的。

4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。

5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。

数据项只能存储在内部结点中（internal node）。我们所指的"叶结点"在其父结点中可能仅仅用一个NULL指针表示，但是将它也看作一个实际的结点有助于描述红黑树的插入与删除算法，叶结点一律为黑色。 定义详解： 根据性质 5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）”。 性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 – 黑节点 – 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 – 红节点 – 黑节点 – 红节点 – 黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路径就是一条红黑交替的路径。 根据定义我们做如下练习： -不符合定义的一颗非红黑树： 红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看图1中的左边这张图，如果不使用黑哨兵，它完全满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。 -两颗正确的红黑树：  定理：

一棵拥有n个内部结点的红黑树的树高h<=2log(n+1)

由此我们可以得出结论：对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，最长路径长度为 2 * (N-1)。 提示：排序二叉树的深度直接影响了检索的性能，正如前面指出，当插入节点本身就是由小到大排列时，排序二叉树将变成一个链表，这种排序二叉树的检索性能最低：N 个节点的二叉树深度就是 N-1。 红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高，这样保证红黑树在最坏情况下都是高效的，不会出现普通排序二叉树的情况。 由于红黑树只是一个特殊的排序二叉树，因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同，只是红黑树保持了大致平衡，因此检索性能比排序二叉树要好很多。 但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都需要进行一定的维护，以保证插入节点、删除节点后的树依然是红黑树。

3 红黑树和AVL树的比较

一棵AVL树满足以下的条件:

1>它的左子树和右子树都是AVL树

2>左子树和右子树的高度差不能超过1

1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)

2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).

3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).