ngx_rbtree_t 赤黒の木

ngx_rbtree_t赤黒ツリー

赤黒ツリーの特徴

ルートノードは黒です
1. すべての赤いノードの両方の子ノードは黒です。
2. 任意のノードからその各リーフ ノードへのすべての単純なパスには、同じ数の黒いノードが含まれます。
4. 赤黒ツリーノード構造

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

5. このようなツリーノードを要素の最初のメンバー位置に配置すると、直接強制が容易になります。

つまり

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

赤黒ツリーノードによって提供される関数

関数名 パラメータの意味実行の意味ngx_rbt_red(no) de) node はノードポインタですngx_rbtree_node_t 型のノードです​​ノードを red に設定しますngx_rbt_black(node)node は ngx_rbtree_nod e_t 型のノードポインタですノードを black に設定しますngx_rbt_is_red (ノード)ノードはngx _rbtree_node_tタイプのノードですpointerノードが赤かどうかを判定ngx_rbt_is_black(node)nodeがngx_rbtree_node_t型のノードポインタであるノードが黒かどうかを判定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 *type現在のノードとそのサブツリーで最小のノードを見つけます(キーに従って)ngx_rbtree_s fully_init(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>

赤黒ツリーコンテナが提供する関数

---

関数名

パラメータの意味実行の意味treeはコンテナポインタ、iはngx_の追加関数です。 rbtree_insert_pt type赤黒ツリーを初期化しますノードを追加し、自動回転により特性が維持されますノードの削除、自動回転保持機能著作権に関する声明: 痛みはあなたの心の中にあるだけです。

		ngx_rbtree_init(tree,s,i)
	void ngx_rbtree_insert(ngx_rbtree_t *tree,ngx_rbtree_node_t *no de)	treeは上記と同じです; ノードは追加されたノードポインタです
	void ngx_rbtree_delete(ngx_rbtree_t *tree,ngx_rbtree_node_t *node)	treeは上記と同じです;ノードは削除する必要があるノードポインタです

上記では、ngx_rbtree_t red-black ツリーを関連コンテンツも含めて紹介しています。PHP チュートリアルに興味のある友人に役立つことを願っています。