名前

       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, const void **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>

       void *root = NULL;

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

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

       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.54 の一部 である。プロジェクトの説明とバグ報告
       に関する情報は http://www.kernel.org/doc/man-pages/ に書かれている。

GNU                                                2012-08-03                                         TSEARCH(3)