Maison  >  Article  >  développement back-end  >  ngx_rbtree_t红黑树

ngx_rbtree_t红黑树

WBOY
WBOYoriginal
2016-08-08 09:20:111580parcourir

ngx_rbtree_t红黑树

红黑树的特性

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

红黑树节点结构体

<code><span>typedef</span> ngx_uint_t ngx_rbtree_key_t;

<span>typedef</span><span>struct</span> ngx_rbtree_node_s ngx_rbtree_node_t;

<span>struct</span><span>struct</span> ngx_rbtree_node_s {
    <span>//无符号整型关键字</span>
    ngx_rbtree_key_t        key;
    <span>//左子节点</span>
    ngx_rbtree_node_t   *left;
    <span>//右子节点</span>
    ngx_rbtree_node_t   *right;
    <span>//父节点</span>
    ngx_rbtree_node_t   *parent;
    <span>//节点的颜色,0:黑,1:红</span>
    u_char                  color;
    <span>//仅一字节的数据</span>
    u_char              data;
    };</code>

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

i.e.

<code><span>typedef</span><span>struct</span> {
    ngx_rbtree_node_t   node;
    ngx_uint_t          num;
    }TestRBTreeBode;</code>

红黑树节点提供的函数

函数名 参数含义 执行意义
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的节点颜色复制给n1
ngx_rbtree_node_t *ngx_rbtree_min(node,sentinel) node、sentinel都是ngx_rbtree_node_t *类型 找到当前节点及其子树中的最小节点(按照key)
ngx_rbtree_sentinel_init(node) node同上 初始化哨兵节点

红黑树结构体

<code><span>typedef</span><span>struct</span> ngx_rbtree_s ngx_rbtree_t;

<span>/* 为解决不同节点含有相同关键字的元素冲突问题所存在的指针*/</span><span>typedef</span><span>void</span> (*ngx_rbtree_insert_pt)(ngx_rbtree_node_t *root,ngx_rbtree_node_t *node,ngx_rbtreenode_t *sentinel);

<span>struct</span> ngx_rbtree_s {
    <span>//指向树的根节点(可以直接强制转化为数据元素)</span>
    ngx_rbtree_node_t       *root;
    <span>//指向NIL哨兵节点</span>
    ngx_rbtree_node_t       *sentinel;
    <span>//红黑树添加元素的指针</span>
    ngx_rbtree_insert_pt    insert;
    };</code>

红黑树容器提供的函数

函数名 参数含义 执行意义
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教程有兴趣的朋友有所帮助。

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Article précédent:centos快速安装lampArticle suivant:PHP获取文件大小并格式化