7.5.2　红黑树的特性

本节讲述红黑树的特性，对于只想了解如何使用ngx_rbtree_t容器的读者，可以跳过本节。

红黑树是指每个节点都带有颜色属性的二叉查找树，其中颜色为红色或黑色。除了二叉查找树的一般要求以外，对于红黑树还有如下的额外的特性。

特性1：节点是红色或黑色。

特性2：根节点是黑色。

特性3：所有叶子节点都是黑色（叶子是NIL节点，也叫“哨兵”）。

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

特性5：从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。

这些约束加强了红黑树的关键性质：从根节点到叶子节点的最长可能路径长度不大于最短可能路径的两倍，这样这个树大致上就是平衡的了。因为二叉树的操作（比如插入、删除和查找某个值的最慢时间）都是与树的高度成比例的，以上的5个特性保证了树的高度（最长路径），所以它完全不同于普通的二叉查找树。

这些特性为什么可以导致上述结果呢？因为特性4实际上决定了1个路径不能有两个毗连的红色节点，这一点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色节点和黑色节点。根据特性5可知，所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能大于其他路径长度的两倍。

在本节的例子中，仍然按照顺序将这10个升序递增的元素添加到空的ngx_rbtree_t红黑树容器中，此时，我们会发现根节点不是第1个添加的元素1，而是元素11。实际上，依次添加元素1、6、8、11、13、15、17、22、25、27后，红黑树的形态如图7-7所示。

图　7-7　ngx_rbtree_t红黑树的典型图示（其中无底纹节点表示红色，有底纹节点表示黑色）

如图7-7所示的是一棵相对平衡的树，它满足红黑树的5个特性，最长路径长度不大于最短路径的2倍。在ngx_rbtree_t红黑树在发现自身满足不了上述5个红黑树特性时，将会通过旋转（向左旋转或者向右旋转）子树来使树达到平衡。这里不再讲述红黑树的旋转功能，实际上它非常简单，读者可以通过ngx_rbtree_left_rotate和ngx_rbtree_right_rotate方法来了解旋转功能的实现。