EN JA
TREE(3)
TREE(3) FreeBSD Library Functions Manual TREE(3)

名称

SPLAY_PROTOTYPE, SPLAY_GENERATE, SPLAY_ENTRY, SPLAY_HEAD, SPLAY_INITIALIZER, SPLAY_ROOT, SPLAY_EMPTY, SPLAY_NEXT, SPLAY_MIN, SPLAY_MAX, SPLAY_FIND, SPLAY_LEFT, SPLAY_RIGHT, SPLAY_FOREACH, SPLAY_INIT, SPLAY_INSERT, SPLAY_REMOVE, RB_PROTOTYPE, RB_PROTOTYPE_STATIC, RB_GENERATE, RB_GENERATE_STATIC, RB_ENTRY, RB_HEAD, RB_INITIALIZER, RB_ROOT, RB_EMPTY, RB_NEXT, RB_PREV, RB_MIN, RB_MAX, RB_FIND, RB_NFIND, RB_LEFT, RB_RIGHT, RB_PARENT, RB_FOREACH, RB_FOREACH_REVERSE, RB_INIT, RB_INSERT, RB_REMOVEスプレイ (斜角) と赤黒ツリーの実装

書式

#include < sys/tree.h>

SPLAY_PROTOTYPE( NAME, TYPE, FIELD, CMP);

SPLAY_GENERATE( NAME, TYPE, FIELD, CMP);

SPLAY_ENTRY( TYPE);

SPLAY_HEAD( HEADNAME, TYPE);

struct TYPE *
SPLAY_INITIALIZER( SPLAY_HEAD *head);

SPLAY_ROOT( SPLAY_HEAD *head);

bool
SPLAY_EMPTY( SPLAY_HEAD *head);

struct TYPE *
SPLAY_NEXT( NAME, SPLAY_HEAD *head, struct TYPE *elm);

struct TYPE *
SPLAY_MIN( NAME, SPLAY_HEAD *head);

struct TYPE *
SPLAY_MAX( NAME, SPLAY_HEAD *head);

struct TYPE *
SPLAY_FIND( NAME, SPLAY_HEAD *head, struct TYPE *elm);

struct TYPE *
SPLAY_LEFT( struct TYPE *elm, SPLAY_ENTRY NAME);

struct TYPE *
SPLAY_RIGHT( struct TYPE *elm, SPLAY_ENTRY NAME);

SPLAY_FOREACH( VARNAME, NAME, SPLAY_HEAD *head);

void
SPLAY_INIT( SPLAY_HEAD *head);

struct TYPE *
SPLAY_INSERT( NAME, SPLAY_HEAD *head, struct TYPE *elm);

struct TYPE *
SPLAY_REMOVE( NAME, SPLAY_HEAD *head, struct TYPE *elm);

RB_PROTOTYPE( NAME, TYPE, FIELD, CMP);

RB_PROTOTYPE_STATIC( NAME, TYPE, FIELD, CMP);

RB_GENERATE( NAME, TYPE, FIELD, CMP);

RB_GENERATE_STATIC( NAME, TYPE, FIELD, CMP);

RB_ENTRY( TYPE);

RB_HEAD( HEADNAME, TYPE);

RB_INITIALIZER( RB_HEAD *head);

struct TYPE *
RB_ROOT( RB_HEAD *head);

bool
RB_EMPTY( RB_HEAD *head);

struct TYPE *
RB_NEXT( NAME, RB_HEAD *head, struct TYPE *elm);

struct TYPE *
RB_PREV( NAME, RB_HEAD *head, struct TYPE *elm);

struct TYPE *
RB_MIN( NAME, RB_HEAD *head);

struct TYPE *
RB_MAX( NAME, RB_HEAD *head);

struct TYPE *
RB_FIND( NAME, RB_HEAD *head, struct TYPE *elm);

struct TYPE *
RB_NFIND( NAME, RB_HEAD *head, struct TYPE *elm);

struct TYPE *
RB_LEFT( struct TYPE *elm, RB_ENTRY NAME);

struct TYPE *
RB_RIGHT( struct TYPE *elm, RB_ENTRY NAME);

struct TYPE *
RB_PARENT( struct TYPE *elm, RB_ENTRY NAME);

RB_FOREACH( VARNAME, NAME, RB_HEAD *head);

RB_FOREACH_REVERSE( VARNAME, NAME, RB_HEAD *head);

void
RB_INIT( RB_HEAD *head);

struct TYPE *
RB_INSERT( NAME, RB_HEAD *head, struct TYPE *elm);

struct TYPE *
RB_REMOVE( NAME, RB_HEAD *head, struct TYPE *elm);

解説

これらのマクロは、異なったタイプのツリーのためのデータ構造体を定義します: スプレイ (斜角) ツリーと赤黒ツリーです。

マクロ定義では、 TYPE は、タイプ SPLAY_ENTRY または RB_ENTRY と名前が付けられた ENTRYNAME フィールドを含まなければならない、ユーザが定義した構造体の名前タグです。引数 HEADNAME は、マクロ SPLAY_HEAD() または RB_HEAD() を使用して定義しなければならない、ユーザが定義した構造体の名前タグです。引数 NAME は、定義されるあらゆるツリーのためのユニークな名前の接頭辞でなければなりません。

関数プロトタイプは、 SPLAY_PROTOTYPE(), RB_PROTOTYPE() または RB_PROTOTYPE_STATIC() で宣言されます。関数本体は、 SPLAY_GENERATE(), RB_GENERATE() または RB_GENERATE_STATIC() で生成されます。これらのマクロがどのように使用されているかの詳細な説明については以下の例を参照してください。

スプレイ (斜角) ツリー

スプレイツリーは、自己編成のデータ構造です。ツリーにおけるあらゆる操作は、スプレイが起こります。スプレイは、要求されたノードをツリーのルートに移動し、部分的に再バランスのとれた状態にします。

これは、要求されたノードがツリーの先端に移動するとき、要求場所が、より速く検索される利点があります。いっぽうで、あらゆる検索でメモリの書き込みが起きます。

バランス定理 (Balance Theorem) は O( (m + n)lg n) のような初期の空のツリーで m 操作と n 挿入するための総アクセス時間を抑制します。スプレイツリーへの m アクセスのシーケンスのための償却コストは O( lg n) です。

スプレイツリーは SPLAY_HEAD() マクロによって定義された構造体が先頭となります。構造体は、次のように宣言されます:

SPLAY_HEAD( HEADNAME, TYPE) head;

ここで、 HEADNAME は、定義される構造体の名前であり、struct TYPE は、ツリーに挿入される要素のタイプです。

SPLAY_ENTRY() マクロは、ツリーに接続されることができる要素の構造体を宣言します。

ツリー構造体を操作する関数を使用するために、それらのプロトタイプは、 SPLAY_PROTOTYPE() マクロで宣言される必要があります。ここで、 NAME は、この特定のツリーのためのユニークな識別子です。 TYPE 引数は、ツリーによって管理されている構造体のタイプです。 FIELD 引数は SPLAY_ENTRY() によって定義された要素の名前です。

関数本体は、 SPLAY_GENERATE() マクロで生成されます。それは、 SPLAY_PROTOTYPE() マクロと同じ引数を取りますが、一度だけ使用されるべきです。

最後に、 CMP 引数は、互いにツリーのノードを比較するために使用される関数の名前です。関数は、タイプ struct TYPE * の 2 つの引数を取ります。最初の引数が 2 番目より小さいなら、関数は、0 より小さな値を返します。それらが等しいなら、関数は、0 を返します。そうでなければ、それは、0 以上の値を返すべきです。比較関数は、ツリーの要素の順序を定義します。

SPLAY_INIT() マクロは head によって参照されるツリーを初期化します。

スプレイツリーは、次のように SPLAY_INITIALIZER() マクロを使用することによって、静的に初期化することもできます:

SPLAY_HEAD( HEADNAME, TYPE) head = SPLAY_INITIALIZER( &head);

SPLAY_INSERT() マクロは、新しい要素 elm をツリーに挿入します。

SPLAY_REMOVE() マクロは head によって指されたツリーから要素 elm を削除します。

SPLAY_FIND() マクロは、ツリーの中の特定の要素を見つけるために使用することができます。

struct TYPE find, *res; 
find.key = 30; 
res = SPLAY_FIND(NAME, head, &find);

SPLAY_ROOT(), SPLAY_MIN(), SPLAY_MAX() と SPLAY_NEXT() マクロは、ツリーを横断するために使用することができます:

for (np = SPLAY_MIN(NAME, &head); np != NULL; 
    np = SPLAY_NEXT(NAME, &head, np))

または、簡単に、 SPLAY_FOREACH() マクロを使用することができます:

SPLAY_FOREACH( np, NAME, head)

SPLAY_EMPTY() マクロは、スプレイツリーが空であるかどうかチェックするのに使用されます。

赤黒ツリー

赤黒ツリーは、特別な属性としてノードの色がある二分検索木です。それは、1 組の条件を実現します:
  1. あらゆるルート (根) からリーフ (葉) までのパスの検索は同じ数の黒のノードから成ります。
  2. それぞれの赤のノード (ルートを除いて) は、黒の親があります。
  3. それぞれのリーフのノードは、黒です。

赤黒ツリーにおけるあらゆる操作は O( lg n) に束縛されます。赤黒ツリーの最大の高さは 2lg( n + 1) です。

赤黒ツリーは RB_HEAD() マクロによって定義された構造体が先頭となります。構造体は、次のように宣言されます:

RB_HEAD( HEADNAME, TYPE) head;

ここで、 HEADNAME は、定義される構造体の名前であり、struct TYPE は、ツリーに挿入される要素のタイプです。

RB_ENTRY() マクロは、ツリーに接続されることができる要素の構造体を宣言します。

ツリー構造体を操作する関数を使用するために、それらのプロトタイプは、 RB_PROTOTYPE() または RB_PROTOTYPE_STATIC() マクロで宣言される必要があります。ここで、 NAME は、この特定のツリーのためのユニークな識別子です。 TYPE 引数は、ツリーによって管理されている構造体のタイプです。 FIELD 引数は RB_ENTRY() によって定義された要素の名前です。

関数本体は、 RB_GENERATE() または RB_GENERATE_STATIC() マクロで生成されます。それらのマクロは、 RB_PROTOTYPE() と RB_PROTOTYPE_STATIC() マクロと同じ引数を取りますが、一度だけ使用されるべきです。

最後に、 CMP 引数は、互いにツリーのノードを比較するために使用される関数の名前です。関数は、タイプ struct TYPE * の 2 つの引数を取ります。最初の引数が 2 番目より小さいなら、関数は、0 より小さな値を返します。それらが等しいなら、関数は、0 を返します。そうでなければ、それは、0 以上の値を返すべきです。比較関数は、ツリーの要素の順序を定義します。

RB_INIT() マクロは、 head によって参照されるツリーを初期化します。

赤黒ツリーは、次のように RB_INITIALIZER() マクロを使用することによって、静的に初期化することもできます:

RB_HEAD( HEADNAME, TYPE) head = RB_INITIALIZER( &head);

RB_INSERT() マクロは、新しい要素 elm をツリーに挿入します。

RB_REMOVE() マクロは、 head によって指されたツリーから要素 elm を削除します。

ツリー中の特定の要素を見つけるために、 RB_FIND() と RB_NFIND() マクロを使用することができます。

struct TYPE find, *res; 
find.key = 30; 
res = RB_FIND(NAME, head, &find);

RB_ROOT(), RB_MIN(), RB_MAX(), RB_NEXT() と RB_PREV() マクロは、ツリーを横断するために使用することができます:

for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))

または、簡単に、 RB_FOREACH() または RB_FOREACH_REVERSE() マクロを使用することができます:

RB_FOREACH( np, NAME, head)

RB_EMPTY() マクロは、赤黒ツリーが空であるかどうかチェックするのに使用されます。

次の方法でツリーを解放する試みは、一般的にエラーです:

SPLAY_FOREACH(var, NAME, head) { 
 SPLAY_REMOVE(NAME, head, var); 
 free(var); 
} 
free(head);

var が解放されるので、 FOREACH() マクロは、既に再割り付けされるポインタを参照します。適切なコードは、2 番目の変数を必要とします。

for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) { 
 nxt = SPLAY_NEXT(NAME, head, var); 
 SPLAY_REMOVE(NAME, head, var); 
 free(var); 
}

成功して要素がツリーに挿入されたなら、 RB_INSERT() と SPLAY_INSERT() の両方は、 NULL を返します。そうでなければ、それらは、衝突したキーの要素へのポインタを返します。

それに従って、 RB_REMOVE() と SPLAY_REMOVE() は、削除された要素へのポインタを返します。そうでなければ、それらは、エラーを示すために NULL を返します。

関連項目

queue(3)

作者

ツリーマクロの作者は、 Niels Provos です。
December 27, 2007 FreeBSD