ngx_rbtree_t红黑树
红黑树的特性
节点是红色或黑色；
根节点是黑色；
所有叶子节点都是黑色（即NIL哨兵节点）；
每个红色节点的两个子节点都是黑色；
从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。
红黑树节点结构体
将这样的树节点放在元素的第一个成员位置，这样方便直接强制转换。
i.e.
红黑树节点提供的函数
X-Node企业快速建站1.0.6.0801
特色介绍： 1、ASP+XML+XSLT开发，代码、界面、样式全分离，可快速开发 2、支持语言包，支持多模板，ASP文件中无任何HTML or 中文 3、无限级分类，无限级菜单，自由排序 4、自定义版头（用于不规则页面） 5、自动查找无用的上传文件与空目录，并有回收站，可删除、还原、永久删除 6、增强的Cache管理，可单独管理单个Cache 7、以内存和XML做为Cache，兼顾性能与消耗 8、
下载
函数名参数含义执行意义ngx_rbt_red(node)node是ngx_rbtree_node_t类型的节点指针设置node为红色ngx_rbt_black(node)node是ngx_rbtree_node_t类型的节点指针设置node为黑色ngx_rbt_is_red(node)node是ngx_rbtree_node_t类型的节点指针判断node是否为红色ngx_rbt_is_black(node)node是ngx_rbtree_node_t类型的节点指针判断node是否为黑色ngx_rbt_copy_color(n1,n2)n1、n2同上将n2的节点颜色复制给n1ngx_rbtree_node_t *ngx_rbtree_min(node,sentinel)node、sentinel都是ngx_rbtree_node_t *类型找到当前节点及其子树中的最小节点（按照key）ngx_rbtree_sentinel_init(node)node同上初始化哨兵节点
红黑树结构体
红黑树容器提供的函数
函数名参数含义执行意义ngx_rbtree_init(tree,s,i)tree是容器指针；s是哨兵指针；i是ngx_rbtree_insert_pt类型的添加函数初始化红黑树void ngx_rbtree_insert(ngx_rbtree_t *tree,ngx_rbtree_node_t *node)tree同上；node是添加的节点指针添加节点，自动旋转保持特性void ngx_rbtree_delete(ngx_rbtree_t *tree,ngx_rbtree_node_t *node)tree同上；node是需要删除的节点指针删除节点，自动旋转保持特性
版权声明：Pain is just in your mind.
以上就介绍了ngx\_rbtree_t红黑树，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。
typedef ngx_uint_t ngx_rbtree_key_t;
typedefstruct ngx_rbtree_node_s ngx_rbtree_node_t;
structstruct 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;
//仅一字节的数据
u_char data;
};typedefstruct {
ngx_rbtree_node_t node;
ngx_uint_t num;
}TestRBTreeBode;typedefstruct ngx_rbtree_s ngx_rbtree_t;
/* 为解决不同节点含有相同关键字的元素冲突问题所存在的指针*/typedefvoid (*ngx_rbtree_insert_pt)(ngx_rbtree_node_t *root,ngx_rbtree_node_t *node,ngx_rbtreenode_t *sentinel);
struct ngx_rbtree_s {
//指向树的根节点（可以直接强制转化为数据元素）
ngx_rbtree_node_t *root;
//指向NIL哨兵节点
ngx_rbtree_node_t *sentinel;
//红黑树添加元素的指针
ngx_rbtree_insert_pt insert;
};