ngx_rbtree_t red black tree

ngx_rbtree_tRed-black tree

Characteristics of red-black tree

1. node is red or black;
2. root node is black;
3. all leaf nodes are black (i.e. NIL sentinel nodes);
4. each red node Both child nodes of are black;
5. All simple paths from any node to each of its leaf nodes contain the same number of black nodes.

Red-black tree node structure

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

Place such a tree node at the first member position of the element, which facilitates direct coercion.

i.e.

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

Function provided by the red-black tree node

Function name	Parameter meaning	Execution meaning
ngx_rbt_red(node)	node is a node pointer of type ngx_rbtree_node_t	Set node to red
ngx_rbt_black(node)	node is a node pointer of type ngx_rbtree_nod e_t	Set node to black
ngx_rbt_is_red(node)	node is ngx _rbtree_node_t type node pointer	Judge node Whether it is red
ngx_rbt_is_black(node)	node is a node pointer of type ngx_rbtree_node_t	Determine whether the node is black
ngx_rbt_copy_color(n1,n2)	n1, n2 Same as above	Change the node color of n2 Copy to n1
ngx_rbtree_node_t *ngx_rbtree_min(node,sentinel)	node and sentinel are both ngx_rbtree_node_t *type	Find the smallest node in the current node and its subtree (according to key)
ngx_rbtree_s entire_init(node)	Node is the same as above	Initialize the sentinel node

---

Red-black tree structure

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

Function provided by the red-black tree container

Function name	Parameter meaning	Execution meaning
ngx_rbtree_init(tree,s,i)	tree is the container pointer; s is the sentinel pointer; i is the added function of ngx_rbtree_insert_pt type	Initialize the red-black tree
void ngx_rbtree_insert(ngx_rbtree_t *tree,ngx_rbtree_node_t *no de)	tree is the same as above; node is the added node pointer	Add node, automatic rotation maintains characteristics
void ngx_rbtree_delete(ngx_rbtree_t *tree,ngx_rbtree_node_t *node)	tree is the same as above; node is the node pointer that needs to be deleted	Delete node , auto-rotation retention feature

Copyright Statement: Pain is just in your mind.

The above introduces the ngx_rbtree_t red-black tree, including the relevant content. I hope it will be helpful to friends who are interested in PHP tutorials.