nginx 红黑树
ngx_rbtree_t（红黑树）是一种非常有效的高级数据结构，它在许多系统中都作为核心数
据结构存在。它在检索特定关键字时不再需要像以上容器那样遍历容器，同时，ngx_rbtree_t容器在检索、插入、删除元素方面非常高效，且其针对各种类型的数据的平均时间都很优异。与散列表相比，ngx_rbtree_t还支持范围查询，也支持高效地遍历所有元素，因此，Nginx的核心模块是离不开ngx_rbtree_t容器的。同时，一些较复杂的Nginx模块也都用到了ngx_rbtree_t容器。用户在需要用到快速检索的容器时，应该首先考虑是不是使用ngx_rbtree_t。
顺序容器的检索效率通常情况下都比较差，一般只能遍历检索指定元素。当需要容器的检索速度很快，或者需要支持范围查询时，ngx_rbtree_t红黑树容器是一个非常好的选择。
红黑树实际上是一种自平衡二叉查找树，但什么是二叉树呢？二叉树是每个节点最多有两个子树的树结构，每个节点都可以用于存储数据，可以由任1个节点访问它的左右子树或者父节点。
那么，什么是二叉查找树呢？二叉查找树或者是一棵空树，或者是具有下列性质的二叉树。
- 每个节点都有一个作为查找依据的关键码（key），所有节点的关键码互不相同。
- 左子树（如果存在）上所有节点的关键码都小于根节点的关键码。
- 右子树（如果存在）上所有节点的关键码都大于根节点的关键码。
- 左子树和右子树也是二叉查找树。
这样，一棵二叉查找树的所有元素节点都是有序的。在二叉树的形态比较平衡的情况下，它的检索效率很高，有点类似于二分法检索有序数组的效率。一般情况下，查询复杂度是与目标节点到根节点的距离（即深度）有关的。然而，不断地添加、删除节点，可能造成二叉查找树形态非常不平衡，在极端情形下它会变成单链表，检索效率也就会变得低下。例如，在本节的例子中，依次将这10个数据1、6、8、11、13、15、17、22、25、27添加到一棵普通的空二叉查找树中，它的形态如下图所示。
第1个元素1添加到空二叉树后自动成为根节点，而后陆续添加的元素正好以升序递增，最终的形态必然如下图所示，也就是相当于单链表了，由于树的深度太大，因此各种操作的效率都会很低下。
普通的二叉查找树可能非常不平衡
什么是自平衡二叉查找树？在不断地向二叉查找树中添加、删除节点时，二叉查找树自身通过形态的变换，始终保持着一定程度上的平衡，即为自平衡二叉查找树。自平衡二叉查找树只是一个概念，它有许多种不同的实现方式，如AVL树和红黑树。红黑树是一种自平衡性较好的二叉查找树，它在Linux内核、C++的STL库等许多场合下都作为核心数据结构使用。本节讲述的ngx_rbtree_t容器就是一种由红黑树实现的自平衡二叉查找树。
ngx_rbtree_t红黑树容器中的元素都是有序的，它支持快速的检索、插入、删除操作，也支持范围查询、遍历等操作，是一种应用场景非常广泛的高级数据结构。
红黑树的特性
红黑树是指每个节点都带有颜色属性的二叉查找树，其中颜色为红色或黑色。除了二叉查找树的一般要求以外，对于红黑树还有如下的额外的特性。
- 节点是红色或黑色。
- 根节点是黑色。
- 所有叶子节点都是黑色（叶子是NIL节点，也叫“哨兵”）。
- 每个红色节点的两个子节点都是黑色（每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）。
- 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。
这些约束加强了红黑树的关键性质：从根节点到叶子节点的最长可能路径长度不大于最短可能路径的两倍，这样这个树大致上就是平衡的了。因为二叉树的操作（比如插入、删除和查找某个值的最慢时间）都是与树的高度成比例的，以上的5个特性保证了树的高度（最长路径），所以它完全不同于普通的二叉查找树。
这些特性为什么可以导致上述结果呢？因为特性4实际上决定了1个路径不能有两个毗连的红色节点，这一点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色节点和黑色节点。根据特性5可知，所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能大于其他路径长度的两倍。
在本节的例子中，仍然按照顺序将这10个升序递增的元素添加到空的ngx_rbtree_t红黑树容器中，此时，我们会发现根节点不是第1个添加的元素1，而是元素11。实际上，依次添加元素1、6、8、11、13、15、17、22、25、27后，红黑树的形态如下图所示。
ngx_rbtree_t红黑树的典型图示
如图所示的是一棵相对平衡的树，它满足红黑树的5个特性，最长路径长度不大于最短路径的2倍。在ngx_rbtree_t红黑树在发现自身满足不了上述5个红黑树特性时，将会通过旋转（向左旋转或者向右旋转）子树来使树达到平衡。这里不再讲述红黑树的旋转功能，实际上它非常简单，读者可以通过ngx_rbtree_left_rotate和ngx_rbtree_right_rotate方法来了解旋转功能的实现。
红黑树的使用方法
红黑树容器由ngx_rbtree_t结构体承载，ngx_rbtree_t的成员在上图可以看到，相关的方法如下：
#define ngx_rbt_red(node) ((node)->color = 1)
#define ngx_rbt_black(node) ((node)->color = 0)
#define ngx_rbt_is_red(node) ((node)->color)
#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)
/* a sentinel must be black */
#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)
static ngx_inline ngx_rbtree_node_t *
ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
while (node->left != sentinel) {
node = node->left;
}
return node;
}
下面进行详细介绍。首先，需要了解一下红黑树的节点结构，如下所示
typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;
struct ngx_rbtree_node_s {
// 无符号整型的关键字
ngx_rbtree_key_t key;
// 左子节点
ngx_rbtree_node_t *left;
// 右子节点
ngx_rbtree_node_t *right;
// 父节点
ngx_rbtree_node_t *parent;
// 节点的颜色，0表示黑色，1表示红色
u_char color;
// 仅1个字节的节点数据。由于表示的空间太小，所以一般很少使用
u_char data;
};
ngx_rbtree_node_t是红黑树实现中必须用到的数据结构，一般我们把它放到结构体中的第1个成员中，这样方便把自定义的结构体强制转换成ngx_rbtree_node_t类型。例如：
typedef struct {
/* 一般都将ngx_rbtree_node_t节点结构体放在自定义数据类型的第1位，以方便类型的强制转换 */
ngx_rbtree_node_t node;
ngx_uint_t num;
} TestRBTreeNode;
如果这里希望容器中元素的数据类型是TestRBTreeNode，那么只需要在第1个成员中放上ngx_rbtree_node_t类型的node即可。在调用ngx_rbtree_t容器所提供的方法时，需要的参数都是ngx_rbtree_node_t类型，这时将TestRBTreeNode类型的指针强制转换成ngx_rbtree_node_t即可。
ngx_rbtree_node_t结构体中的key成员是每个红黑树节点的关键字，它必须是整型。红黑树的排序主要依据key成员（当然，自定义ngx_rbtree_insert_pt方法后，节点的其他成员也可以在key排序的基础上影响红黑树的形态）。在图7-7所示例子中，1、6、8、11、13、15、17、22、25、27这些数字都是每个节点的key关键字。
下面看一下表示红黑树的ngx_rbtree_t结构体是如何定义的，代码如下。
typedef struct ngx_rbtree_s ngx_rbtree_t;
/* 为解决不同节点含有相同关键字的元素冲突问题，红黑树设置了ngx_rbtree_insert_pt指针，这样可灵活地添加冲突元素 */
typedef void (ngx_rbtree_insert_pt) (ngx_rbtree_node_t root,
ngx_rbtree_node_t node, ngx_rbtree_node_t *sentinel);
struct ngx_rbtree_s {
// 指向树的根节点。注意，根节点也是数据元素
ngx_rbtree_node_t *root;
// 指向NIL哨兵节点
ngx_rbtree_node_t *sentinel;
// 表示红黑树添加元素的函数指针，它决定在添加新节点时的行为究竟是替换还是新增
ngx_rbtree_insert_pt insert;
};
在上段代码中，ngx_rbtree_t结构体的root成员指向根节点，而sentinel成员指向哨兵节点，这很清晰。然而，insert成员作为一个ngx_rbtree_insert_pt类型的函数指针，它的意义在哪里呢？
红黑树是一个通用的数据结构，它的节点（或者称为容器的元素）可以是包含基本红黑树节点的任意结构体。对于不同的结构体，很多场合下是允许不同的节点拥有相同的关键字的（参见图7-8中的key成员，它作为无符号整型数时表示树节点的关键字）。例如，不同的字符串可能会散列出相同的关键字，这时它们在红黑树中的关键字是相同的，然而它们又是不同的节点，这样在添加时就不可以覆盖原有同名关键字节点，而是作为新插入的节点存在。因此，在添加元素时，需要考虑到这种情况。将添加元素的方法抽象出ngx_rbtree_insert_pt函数指针可以很好地实现这一思想，用户也可以灵活地定义自己的行为。
Nginx帮助用户实现了3种简单行为的添加节点方法如下
Nginx为红黑树已经实现好的3种数据添加方法
ngx_str_rbtree_insert_value函数的应用场景为：节点的标识符是字符串，红黑树的第一排序依据仍然是节点的key关键字，第二排序依据则是节点的字符串。因此，使用ngx_str_rbtree_insert_value时表示红黑树节点的结构体必须是ngx_str_node_t，如下所示。
typedef struct {
ngx_rbtree_node_t node;
ngx_str_t str;
} ngx_str_node_t;
同时，对于ngx_str_node_t节点，Nginx还提供了ngx_str_rbtree_lookup方法用于检索红黑树节点，下面来看一下它的定义，代码如下。
ngx_str_node_t *ngx_str_rbtree_lookup(ngx_rbtree_t rbtree, ngx_str_t name, uint32_t hash);
其中，hash参数是要查询节点的key关键字，而name是要查询的字符串（解决不同字符串对应相同key关键字的问题），返回的是查询到的红黑树节点结构体。
关于红黑树操作的方法如下
红黑树容器提供的方法
在初始化红黑树时，需要先分配好保存红黑树的ngx_rbtree_t结构体，以及ngx_rbtree_node_t类型的哨兵节点，并选择或者自定义ngx_rbtree_insert_pt类型的节点添加函数。
对于红黑树的每个节点来说，它们都具备上述所列的针对结点的方法，如果只是想了解如何使用红黑树，那么只需要了解ngx_rbtree_min方法。
红黑树节点提供的方法
容器提供的方法大部分用于实现或者扩展红黑树的功能，如果只是使用红黑树，那么一般情况下只会使用ngx_rbtree_min方法。
本节介绍的方法或者结构体的简单用法的实现可参见如下示例。
使用红黑树的简单例子
本节以一个简单的例子来说明如何使用红黑树容器。首先在栈中分配rbtree红黑树容器结构体以及哨兵节点sentinel（当然，也可以使用内存池或者从进程堆中分配），本例中的节点完全以key关键字作为每个节点的唯一标识，这样就可以采用预设的ngx_rbtree_insert_value方法了。最后可调用ngx_rbtree_init方法初始化红黑树，代码如下所示。
ngx_rbtree_t rbtree;
ngx_rbtree_node_t sentinel;
ngx_rbtree_init(&rbtree, &sentinel, ngx_rbtree_insert_value);
本例中树节点的结构体使用如上介绍的TestRBTreeNode结构体，树中的所有节点都取自上图，每个元素的key关键字按照1、6、8、11、13、15、17、22、25、27的顺序向红黑树中添加，代码如下所示。
TestRBTreeNode rbTreeNode[10];
rbTreeNode[0].num = 1;
rbTreeNode[1].num = 6;
rbTreeNode[2].num = 8;
rbTreeNode[3].num = 11;
rbTreeNode[4].num = 13;
rbTreeNode[5].num = 15;
rbTreeNode[6].num = 17;
rbTreeNode[7].num = 22;
rbTreeNode[8].num = 25;
rbTreeNode[9].num = 27;
for (i = 0; i < 10; i++)
{
rbTreeNode[i].node.key = rbTreeNode[i].num;
ngx_rbtree_insert(&rbtree,&rbTreeNode[i].node);
}
以这种顺序添加完的红黑树形态如上图所示。如果需要找出当前红黑树中最小的节点，可以调用ngx_rbtree_min方法获取。
ngx_rbtree_node_t *tmpnode = ngx_rbtree_min(rbtree.root, &sentinel);
当然，参数中如果不使用根节点而是使用任一个节点也是可以的。下面来看一下如何检索1个节点，虽然Nginx对此并没有提供预设的方法（仅对字符串类型提供了ngx_str_rbtree_lookup检索方法），但实际上检索是非常简单的。下面以寻找key关键字为13的节点为例来加以说明。
ngx_uint_t lookupkey = 13;
tmpnode = rbtree.root;
TestRBTreeNode *lookupNode;
while (tmpnode != &sentinel) {
if (lookupkey != tmpnode->key) {
// 根据key关键字与当前节点的大小比较，决定是检索左子树还是右子树
tmpnode = (lookupkey < tmpnode->key) tmpnode->left : tmpnode->right;
continue;
}
// 找到了值为13的树节点
lookupNode = (TestRBTreeNode *) tmpnode;
break;
}
从红黑树中删除1个节点也是非常简单的，如把刚刚找到的值为13的节点从rbtree中删除，只需调用ngx_rbtree_delete方法。
ngx_rbtree_delete(&rbtree,&lookupNode->node);
如何自定义添加成员方法
由于节点的key关键字必须是整型，这导致很多情况下不同的节点会具有相同的key关键字。如果不希望出现具有相同key关键字的不同节点在向红黑树添加时出现覆盖原节点的情况，就需要实现自有ngx_rbtree_insert_pt方法。
许多Nginx模块在使用红黑树时都自定义了ngx_rbtree_insert_pt方法（如geo、filecache模块等），现以介绍过的ngx_str_rbtree_insert_value为例，来说明如何定义这样的方法。先看一下ngx_str_rbtree_insert_value的实现。代码如下。
void
ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
ngx_rbtree_node_t node, ngx_rbtree_node_t sentinel)
{
ngx_str_node_t n, t;
ngx_rbtree_node_t **p;
for ( ;; ) {
n = (ngx_str_node_t ) node;
t = (ngx_str_node_t ) temp;
// 首先比较key关键字，红黑树中以key作为第一索引关键字
if (node->key != temp->key) {
// 左子树节点的关键节小于右子树
p = (node->key < temp->key) &temp->left : &temp->right;
}
// 当key关键字相同时，以字符串长度为第二索引关键字
else if (n->str.len != t->str.len) {
// 左子树节点字符串的长度小于右子树
p = (n->str.len < t->str.len) &temp->left : &temp->right;
} else {
// key关键字相同且字符串长度相同时，再继续比较字符串内容
p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0) &temp->left : &temp->right;
}
// 如果当前节点p是哨兵节点，那么跳出循环准备插入节点
if (*p == sentinel) {
break;
}
// p节点与要插入的节点具有相同的标识符时，必须覆盖内容
temp = p;
}
p = node;
// 置插入节点的父节点
node->parent = temp;
// 左右子节点都是哨兵节点
node->left = sentinel;
node->right = sentinel;
/* 将节点颜色置为红色。注意，红黑树的ngx_rbtree_insert方法会在可能的旋转操作后重置该节点的颜色 */
ngx_rbt_red(node);
}
可以看到，该代码与前文中介绍过的检索节点代码很相似。它所要处理的主要问题就是当key关键字相同时，继续以何种数据结构作为标准来确定红黑树节点的唯一性。Nginx中已经实现的诸多ngx_rbtree_insert_pt方法都是非常相似的，开发者完全可以参照ngx_str_rbtree_insert_value方法来自定义红黑树节点添加方法。
本文暂取自代码、网络或书籍，只用作学习备忘，不作盈利等他用，如有侵权，请联系Linkerist@163.com
