7.5.3　红黑树的使用方法

红黑树容器由ngx_rbtree_t结构体承载，ngx_rbtree_t的成员和它相关的方法在图7-7中可以看到，下面进行详细介绍。首先，需要了解一下红黑树的节点结构，如图7-8所示。

图　7-8　红黑树节点的结构体及其提供的方法

ngx_rbtree_node_t结构体用来表示红黑树中的一个节点，它还提供了7个方法用来操作节点。下面了解一下ngx_rbtree_node_t结构体的定义，代码如下。

typedef ngx_uint_t ngx_rbtree_key_t；

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即可。在调用图7-7中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_troot，

ngx_rbtree_node_tnode,ngx_rbtree_node_tsentinel）；

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种简单行为的添加节点方法，见表7-4。

表7-4中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_tngx_str_rbtree_lookup（ngx_rbtree_trbtree,ngx_str_t*name,uint32_t hash）；

其中，hash参数是要查询节点的key关键字，而name是要查询的字符串（解决不同字符串对应相同key关键字的问题），返回的是查询到的红黑树节点结构体。

关于红黑树操作的方法见表7-5。

在初始化红黑树时，需要先分配好保存红黑树的ngx_rbtree_t结构体，以及ngx_rbtree_node_t类型的哨兵节点，并选择或者自定义ngx_rbtree_insert_pt类型的节点添加函数。

对于红黑树的每个节点来说，它们都具备表7-6所列的7个方法，如果只是想了解如何使用红黑树，那么只需要了解ngx_rbtree_min方法。

表7-5中的方法大部分用于实现或者扩展红黑树的功能，如果只是使用红黑树，那么一般情况下只会使用ngx_rbtree_min方法。

本节介绍的方法或者结构体的简单用法的实现可参见7.5.4节的相关示例。