ngx_rbtree_t 레드 블랙 트리

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>

이러한 트리 노드를 요소의 첫 번째 멤버 위치에 배치하면 직접 캐스팅이 용이합니다.

즉,

<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是需要删除的节点指针	删除节点，自动旋转保持特性

저작권: 고통은 마음속에 있습니다.

위 내용은 관련 내용을 포함하여 ngx_rbtree_t 레드-블랙 트리를 소개한 내용으로, PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.