Nginx学习(8)—红黑树

红黑树ngx_rbtree_t

ngx_rbtree_t是使用红黑树实现的关联容器，Nginx核心模块（定时器管理、文件缓存模块）在快速检索、查找场合下需要使用。

红黑树特性

红黑树是一种自平衡二叉查找树，每个节点都带有颜色属性。红黑树除了满足二叉查找树的一般要求之外，还有如下额外特性：

1. 节点是红色或者黑色；
2. 根节点为黑色；
3. 所有叶子节点都为黑色（叶子是NIL节点，即”哨兵“）；
4. 每个红色节点的两个子节点都为黑色（每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）；
5. 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点；

所有这些特性保证了红黑树的关键性质： 从根节点到叶子节点的最长可能路径长度不大于最短可能路径的两倍。

在发现自身满足不了其中5个特性时，会通过左右旋转 最小不平衡子树使树重新达到平衡（Nginx中使用ngx_rbtree_left_rotate和ngx_rbtree_right_rotate方法）。

ngx_rbtree_t结构

[cpp]  view plain copy

1. typedef ngx_uint_t  ngx_rbtree_key_t;  
2.   
3. typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;  
4. struct ngx_rbtree_node_s {  
5.     ngx_rbtree_key_t       key;     // 无符号整型关键字   
6.     ngx_rbtree_node_t     *left;  
7.     ngx_rbtree_node_t     *right;  
8.     ngx_rbtree_node_t     *parent;  
9.     u_char                 color;   // 颜色属性  
10.     u_char                 data;  
11. }; // 使用红黑树必须用到的数据结构，一般将其放于自定义结构体中首个成员，以方便类型强转  

ngx_rbtree_node_t是实现红黑树必须用到的数据结构，其中的key成员即每个红黑树节点的关键字。

[cpp]  view plain copy

1. typedef struct ngx_rbtree_s  ngx_rbtree_t;  
2. struct ngx_rbtree_s {  
3.     ngx_rbtree_node_t     *root;       // 根节点  
4.     ngx_rbtree_node_t     *sentinel;   // 哨兵节点  
5.     ngx_rbtree_insert_pt   insert;     // 添加节点方法的函数指针，自行实现  
6. };  

这里，insert成员是一个单独的函数指针，如下：

[cpp]  view plain copy

1. typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,  
2.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);  

红黑树作为一个通用的数据结构，其节点可以是包含基本红黑树节点（这里比如ngx_rbtree_node_t）的任意结构体。而对于不同的结构体，一些场合，不同节点关键字唯一；而有一些场合又允许不同节点拥有相同关键字，因此插入方法要视具体业务而灵活定义，或增加或替换。
Nginx中为红黑树已实现三种数据添加方法，分别是：

[cpp]  view plain copy

1. /* 每个节点关键字唯一 */      
2. void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,  
3.     ngx_rbtree_node_t *sentinel);  
4.       
5. /* 每个节点关键字表示时间或者时间差 */  
6. void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,  
7.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);  
8.       
9. /* 关键字节点可以不是唯一，以字符串作为唯一标识，存放在ngx_str_node_t中 */  
10. void ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,  
11.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);  

对于第三种ngx_str_node_t节点，Nginx提供ngx_str_rbtree_lookup方法用于检索。

[cpp]  view plain copy

1. ngx_str_node_t *ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *name,  
2.     uint32_t hash);  

ngx_rbtree_node_t操作

Nginx中，为红黑树ngx_rbtree_t提供初始化，插入，删除3种操作方法。为每一个红黑树节点，也提供对应操作。

关于对于红黑树ngx_rbtree_t中插入节点与ngx_rbtree_t中inserte成员的关系：

[cpp]  view plain copy

1. void  
2. ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,  
3.     ngx_rbtree_node_t *node)  
4. {  
5.     ...  
6.   
7.     /* 调用节点的插入方法 */  
8.     tree->insert(*root, node, sentinel);    
9.       
10.     /* 插入之后，旋转，保持二叉树平衡 */   
11.     ...  
12. }  

自定义插入成员方法

分析下ngx_str_rbtree_insert_value的源码。

[cpp]  view plain copy

1. void  
2. ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,  
3.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)  
4. {  
5.     ngx_str_node_t      *n, *t;  
6.     ngx_rbtree_node_t  **p;  
7.   
8.     for ( ;; ) {  
9.         /* 注意类型强转技巧，这里就是将ngx_rbtree_node_t作为ngx_str_node_t首成员的意义 */  
10.         n = (ngx_str_node_t *) node;  
11.         t = (ngx_str_node_t *) temp;  
12.   
13.         /* 关键字key作为第一索引 */  
14.         if (node->key != temp->key) {  
15.           
16.             p = (node->key < temp->key) ? &temp->left : &temp->right;  
17.               
18.         } else if (n->str.len != t->str.len) {  
19.             /* 关键字key相同，以字符串长度作为第二索引 */  
20.             p = (n->str.len < t->str.len) ? &temp->left : &temp->right;  
21.   
22.         } else {  
23.             /* 关键字与字符串长度均相同，则比较字符串内容 */  
24.             p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)  
25.                  ? &temp->left : &temp->right;  
26.         }  
27.   
28.         /* 若遍历的当前节点是哨兵，则跳出循环 */  
29.         if (*p == sentinel) {  
30.             break;  
31.         }  
32.   
33.         temp = *p;  
34.     }  
35.   
36.     *p = node;  
37.     node->parent = temp;     // 设置插入节点父节点  
38.     node->left = sentinel;  
39.     node->right = sentinel;  // 插入的节点的子节点均为哨兵节点  
40.       
41.     /* 将插入节点置红色，此颜色在调用ngx_rbtree_insert方法时，由于需要保持自平衡，在旋转过程中可能会重置 */  
42.     ngx_rbt_red(node);         
43. }  

总结

学习这一章过程中，将平衡二叉树的内容又复习一遍。对于通过旋转怎么保持自平衡也重新有了了解。之后打算把平衡二叉树再记录记录了。