Manpages

名 前

tsearch, tfind, tdelete, twalk, tdestroy − 二 分 木 (binary tree) の 操 作

書 式

#include <search.h>

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

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

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

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

#define _GNU_SOURCE /* feature_test_macros(7) 参 照 */
#include <search.h>

void tdestroy(void *root, void (*free_node)(void *nodep));

説 明

tsearch(), tfind(), twalk(), tdelete() は 二 分 木 を 操 作 す る 関 数 で あ る 。 こ れ ら の 関 数 は Knuth (6.2.2) Algorithm T に 基 づ い て い る 。 木 構 造 に お け る 各 ノ ー ド の 最 初 の フ ィ ー ル ド は 、 対 応 す る デ ー タ ア イ テ ム へ の ポ イ ン タ ー で あ る 。 (参 照 先 の デ ー タ は 、 呼 び 出 し プ ロ グ ラ ム で 用 意 す る 。 ) compar は 比 較 ル ー チ ン へ の ポ イ ン タ ー で あ る 。 比 較 ル ー チ ン は 、 ア イ テ ム へ の ポ イ ン タ ー 2 つ を 引 き 数 に 持 つ 。 比 較 ル ー チ ン の 返 り 値 は 、 1 つ 目 の ア イ テ ム が 2 つ 目 の ア イ テ ム よ り も 「 小 さ い 、 等 し い 、 大 き い 」 に よ っ て 、 「 負 、 0、 正 」 の 整 数 値 で な け れ ば な ら な い 。

tsearch() は 、 木 構 造 か ら ア イ テ ム を 検 索 す る 関 数 で あ る 。 key は 、 検 索 す る ア イ テ ム へ の ポ イ ン タ ー で あ る 。 rootp は 木 構 造 の 根 へ の ポ イ ン タ ー へ の ポ イ ン タ ー で あ る 。 木 構 造 が ノ ー ド を 含 ま な い 場 合 、 rootp の 参 照 し て い る 変 数 は NULL に 設 定 さ れ て い な け れ ば な ら な い 。 木 構 造 に ア イ テ ム が 見 つ か っ た 場 合 、 tsearch() は そ の ア イ テ ム へ の ポ イ ン タ ー を 返 す 。 見 つ か ら な か っ た 場 合 は 、 ア イ テ ム を 木 構 造 に 追 加 し 、 追 加 し た ア イ テ ム へ の ポ イ ン タ ー を 返 す 。

tfind() は 、 tsearch() に 似 て い る が 、 ア イ テ ム が 見 つ か ら な か っ た 場 合 NULL を 返 す 点 が 異 な る 。

tdelete() は 木 構 造 か ら ア イ テ ム を 削 除 す る 。 引 き 数 は tsearch() と 同 じ で あ る 。

twalk() は 、 二 分 木 を 深 さ 優 先 (depth−first) で 、 左 か ら 右 に た ど っ て い く 関 数 で あ る 。 root は 起 点 と な る ノ ー ド へ の ポ イ ン タ ー で あ る 。 root に 根 以 外 の ノ ー ド を 指 定 す る と 、 部 分 木 が 対 象 と な る 。 twalk() は 、 ノ ー ド を 訪 れ る 度 に ユ ー ザ ー 関 数 action を 呼 び 出 す (内 部 ノ ー ド に 対 し て は 3 回 、 葉 に 対 し て は 1 回 呼 び 出 し が 行 わ れ る )。 action に は 以 下 の 順 に 3 つ の 引 き 数 が 与 え ら れ る 。 最 初 の 引 き 数 は 訪 れ た ノ ー ド へ の ポ イ ン タ ー で あ る 。 ノ ー ド の 構 造 体 は 規 定 さ れ て い な い が 、 ポ イ ン タ ー を 要 素 へ の ポ イ ン タ ー の ポ イ ン タ ー に キ ャ ス ト し 、 ノ ー ド に 格 納 さ れ た 要 素 に ア ク セ ス す る こ と が で き る 。 ア プ リ ケ ー シ ョ ン は 、 こ の 引 き 数 が 指 す 構 造 体 を 変 更 し て は な ら な い 。 2 番 目 の 引 き 数 に は 、 内 部 ノ ー ド の 場 合 は 訪 問 回 数 に 応 じ て preorder, postorder, endorder の い ず れ か の 整 数 が 、 葉 を 最 初 に 訪 れ た 場 合 は leaf の 値 が 渡 さ れ る (こ れ ら の シ ン ボ ル は <search.h> で 定 義 さ れ て い る )。 3 番 目 の 引 き 数 は ノ ー ド の 深 さ で 、 根 の 場 合 は 深 さ 0 で あ る 。

(よ り 一 般 的 に は 、 preorder, postorder, endorder は preorder, inorder, postorder と し て 知 ら れ て い る : そ れ ぞ れ 、 子 要 素 を 辿 る 前 ・ 最 初 の 子 要 素 を 辿 っ た 後 か つ 2 番 目 の 子 要 素 を 辿 る 前 ・ 子 要 素 を 辿 っ た 後 と い う こ と を 表 し て い る 。 よ っ て postorder と い う 名 前 を 選 ぶ の は 少 し 紛 ら わ し い 。 )

tdestroy() は root が 指 す 木 構 造 全 体 を 削 除 し 、 tsearch() 関 数 で 確 保 さ れ た リ ソ ー ス を 全 て 解 放 す る 。 木 構 造 の 各 ノ ー ド に つ い て 、 関 数 free_node が 呼 び 出 さ れ る 。 デ ー タ へ の ポ イ ン タ ー が こ の 関 数 の 引 き 数 と し て 渡 さ れ る 。 そ の よ う な 動 作 が 必 要 で な け れ ば 、 free_node は 何 も し な い 関 数 へ の ポ イ ン タ ー で な け れ ば な ら な い 。

返 り 値

tsearch() は 、 木 構 造 に 見 つ か っ た ア イ テ ム か 、 新 し く 追 加 し た ア イ テ ム へ の ポ イ ン タ ー を 返 す 。 メ モ リ ー の 不 足 の た め ア イ テ ム を 追 加 で き な か っ た 場 合 は NULL を 返 す 。 tfind() は 、 ア イ テ ム へ の ポ イ ン タ ー を 返 す 。 一 致 す る ア イ テ ム が 見 つ か ら な い 場 合 は NULL を 返 す 。 検 索 条 件 に 一 致 す る 要 素 が 複 数 あ る 場 合 、 返 さ れ る 値 は 不 定 で あ る 。

tdelete() は 削 除 し た ア イ テ ム の 親 へ の ポ イ ン タ ー を 返 す 。 ア イ テ ム が 見 つ か ら な か っ た 場 合 は NULL を 返 す 。

rootp が NULL の 場 合 、 tsearch(), tfind(), tdelete() は NULL を 返 す 。

準 拠

SVr4, POSIX.1−2001. 関 数 tdestroy() は GNU の 拡 張 で あ る 。

注 意

twalk() は 根 へ の ポ イ ン タ ー を 引 き 数 に と る が 、 ほ か の 関 数 は 根 へ の ポ イ ン タ ー へ の ポ イ ン タ ー で あ る 。

tdelete() は 、 削 除 し た ノ ー ド の 使 用 し て い た メ モ リ ー を 解 放 す る が 、 ノ ー ド に 対 応 す る デ ー タ の メ モ リ ー は 、 ユ ー ザ ー が 解 放 し な け れ ば な ら な い 。 下 の プ ロ グ ラ ム 例 は 、 ユ ー ザ ー 関 数 が "endorder" か "leaf" を 引 き 数 に し て 呼 び 出 さ れ て 以 降 は 、 twalk() が そ の ノ ー ド を 参 照 し な い こ と を 前 提 と し て い る 。 こ れ は GNU ラ イ ブ ラ リ の 実 装 で は 機 能 す る が 、 System V の マ ニ ュ ア ル に は 存 在 し な い 。

例

以 下 の プ ロ グ ラ ム は 12 個 の 乱 数 を 二 分 木 に 挿 入 し た 後 、 挿 入 し た 数 を 順 番 に 出 力 す る (挿 入 の 際 、 重 複 し た 乱 数 は 1 つ に ま と め ら れ る )。

#define _GNU_SOURCE /* Expose declaration of tdestroy() */
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

static void *root = NULL;

static void *
xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if (p)
return p;
fprintf(stderr, "insufficient memory\n");
exit(EXIT_FAILURE); }

static int
compare(const void *pa, const void *pb)
{
if (*(int *) pa < *(int *) pb)
return −1;
if (*(int *) pa > *(int *) pb)
return 1;
return 0; }

static void
action(const void *nodep, const VISIT which, const int depth)
{
int *datap;

switch (which) {
case preorder:
break;
case postorder:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
case endorder:
break;
case leaf:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break; } }

int
main(void)
{
int i, *ptr;
void *val;

srand(time(NULL));
for (i = 0; i < 12; i++) {
ptr = xmalloc(sizeof(int));
*ptr = rand() & 0xff;
val = tsearch((void *) ptr, &root, compare);
if (val == NULL)
exit(EXIT_FAILURE);
else if ((*(int **) val) != ptr)
free(ptr); }
twalk(root, action);
tdestroy(root, free);
exit(EXIT_SUCCESS); }

関 連 項 目

bsearch(3), hsearch(3), lsearch(3) qsort(3)

こ の 文 書 に つ い て

こ の man ペ ー ジ は Linux man−pages プ ロ ジ ェ ク ト の リ リ ー ス 3.79 の 一 部 で あ る 。 プ ロ ジ ェ ク ト の 説 明 と バ グ 報 告 に 関 す る 情 報 は http://www.kernel.org/doc/man−pages/ に 書 か れ て い る 。