7.5　ngx_rbtree_t红黑树

ngx_rbtree_t是使用红黑树实现的一种关联容器，Nginx的核心模块（如定时器管理、文件缓存模块等）在需要快速检索、查找的场合下都使用了ngx_rbtree_t容器，本节将系统地讨论ngx_rbtree_t的用法，并以一个贯穿本节始终的例子对它进行说明。在这个例子中，将有10个元素需要存储到红黑树窗口中，每个元素的关键字是简单的整型，分别为1、6、8、11、13、15、17、22、25、27，以下的例子中都会使用到这10个节点数据。

7.5.1　为什么设计ngx_rbtree_t红黑树

上文介绍的容器都是顺序容器，它们的检索效率通常情况下都比较差，一般只能遍历检索指定元素。当需要容器的检索速度很快，或者需要支持范围查询时，ngx_rbtree_t红黑树容器是一个非常好的选择。

红黑树实际上是一种自平衡二叉查找树，但什么是二叉树呢？二叉树是每个节点最多有两个子树的树结构，每个节点都可以用于存储数据，可以由任1个节点访问它的左右子树或者父节点。

那么，什么是二叉查找树呢？二叉查找树或者是一棵空树，或者是具有下列性质的二叉树。

❑每个节点都有一个作为查找依据的关键码（key），所有节点的关键码互不相同。

❑左子树（如果存在）上所有节点的关键码都小于根节点的关键码。

❑右子树（如果存在）上所有节点的关键码都大于根节点的关键码。

❑左子树和右子树也是二叉查找树。

这样，一棵二叉查找树的所有元素节点都是有序的。在二叉树的形态比较平衡的情况下，它的检索效率很高，有点类似于二分法检索有序数组的效率。一般情况下，查询复杂度是与目标节点到根节点的距离（即深度）有关的。然而，不断地添加、删除节点，可能造成二叉查找树形态非常不平衡，在极端情形下它会变成单链表，检索效率也就会变得低下。例如，在本节的例子中，依次将这10个数据1、6、8、11、13、15、17、22、25、27添加到一棵普通的空二叉查找树中，它的形态如图7-6所示。

第1个元素1添加到空二叉树后自动成为根节点，而后陆续添加的元素正好以升序递增，最终的形态必然如图7-6所示，也就是相当于单链表了，由于树的深度太大，因此各种操作的效率都会很低下。

图　7-6　普通的二叉查找树可能非常不平衡

什么是自平衡二叉查找树？在不断地向二叉查找树中添加、删除节点时，二叉查找树自身通过形态的变换，始终保持着一定程度上的平衡，即为自平衡二叉查找树。自平衡二叉查找树只是一个概念，它有许多种不同的实现方式，如AVL树和红黑树。红黑树是一种自平衡性较好的二叉查找树，它在Linux内核、C++的STL库等许多场合下都作为核心数据结构使用。本节讲述的ngx_rbtree_t容器就是一种由红黑树实现的自平衡二叉查找树。

ngx_rbtree_t红黑树容器中的元素都是有序的，它支持快速的检索、插入、删除操作，也支持范围查询、遍历等操作，是一种应用场景非常广泛的高级数据结构。