7.5.4　使用红黑树的简单例子

本节以一个简单的例子来说明如何使用红黑树容器。首先在栈中分配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）；

本例中树节点的结构体将使用7.5.3节中介绍的TestRBTreeNode结构体，树中的所有节点都取自图7-7，每个元素的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）；

}

以这种顺序添加完的红黑树形态如图7-7所示。如果需要找出当前红黑树中最小的节点，可以调用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）；