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

名称

tsearch, tfind, tdelete, twalkバイナリ (2 進) 検索木を操作する

書式

#include < search.h>

void *
tdelete( const void * restrict key, void ** restrict rootp, int (*compar) (const void *, const void *));

void *
tfind( const void *key, void * const *rootp, int (*compar) (const void *, const void *));

void *
tsearch( const void *key, void **rootp, int (*compar) (const void *, const void *));

void
twalk( const void *root, void (*action) (const void *, VISIT, int));

解説

tdelete(), tfind(), tsearch() と twalk() 関数は、Knuth (6.2.2) からのアルゴリズム T および D に基づいたバイナリ (2 進) 検索木を管理します。ユーザによって渡された比較関数は strcmp(3) と同じスタイルの返り値を持っています。

rootp をルート (根) とするバイナリ (2 進) 木で引数 key によって一致したデータの tfind() 関数捜索は、それが見つかる場合に、データへのポインタを返します。そうでなければ NULL を返します。

tsearch() 関数は、一致が見つからない場合、 key が木に挿入される以外は tfind() と同一です。また、それへのポインタが返されます。 rootp が NULL 値を指す場合、新しいバイナリ (2 進) 検索木が作成されます。

tdelete() 関数は指定されたバイナリ (2 進) 検索木からノードを削除します。そして、削除されるノードの親のポインタを返します。それは、 tfind() と tsearch() と同じ引数をとります。削除されるノードがバイナリ (2 進) 検索木のルート (根) である場合、 rootp が調節されるでしょう。

twalk() 関数は、 root をルート (根) としたバイナリ (2 進) 検索木を歩きます。また、各ノードで関数 action を呼び出します。 action 関数は 3 つの引数で呼ばれます。現在のノードへのポインタ、横断タイプを指定する typedef enum { preorder, postorder, endorder, leaf } VISIT; enum からの値、およびノードレベル (レベル 0 が木のルート (根) です) です。

戻り値

新しいノードの割り付けが失敗する場合 (通常自由なメモリの不足により)、 tsearch() 関数は NULL を返します。

rootp が NULL か、データを見つけることができない場合、 tfind(), tsearch() と tdelete() 関数は、NULL を返します。

twalk() 関数は、値を返しません。

June 15, 1997 FreeBSD