ngx_rbtree_t紅黑樹

ngx_rbtree_t紅黑樹

紅黑樹的特性

1. 節點是紅色或黑色；
2. 根節點是黑色；
3. 所有葉子節點都是黑色（即NILAIL節點節點）；的兩個子節點都是黑色；
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_black(node) _rbtree_node_t類型的節點指標判斷node是否為紅色ngx_rbt_is_black(node)node是ngx_rbtree_node_t類型的節點指標判斷是否為黑色、n node、sentinel都是ngx_rbtree_node_t*類型 it(node) node同上初始化哨兵節點紅黑樹結構體紅黑樹容器提供的函數義字treeidr_rbmmm; tree同上；node是新增的節點指標新增節點，自動旋轉保持特性void ngx_rbtree_delete(ngx_rbtree_t *tree,ngx_rbtree_node_t *node)

參數	node是ngx_rbtree_node_t類型的節點指針	設定node為紅色
node是ngx_rbtree_node_t類型的節點指標	值node為黑色
將n2的節點顏色複製給n1		ngx_rbtree_node_t *ngx_rbtree_min(node,sentinel)
	<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型別的新增函數	初始化紅黑樹

)

---

的節點指標

； ，自動旋轉保持特性

以上就介紹了ngx_rbtree_t紅黑樹，包含了方面的內容，希望對PHP教學有興趣的朋友有幫助。

版權聲明：Pain is just in your mind.