ngx_rbtree_t红黑树

红黑树的特性

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

红黑树节点结构体

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;
    };

将这样的树节点放在元素的第一个成员位置，这样方便直接强制转换。

i.e.

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;
    };

红黑树容器提供的函数

版权声明：Pain is just in your mind.

以上就介绍了ngx\_rbtree_t红黑树，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。