【C言語】二分探索木の操作関数の使い方【tsearch/tfind/tdelete/twalk/twalk

悩んでいる人

C言語で二分探索木の操作関数の使い方を教えて！

こういった悩みにお答えします．

本記事の信頼性

リアルタイムシステムの研究歴12年．
東大教員の時に，英語でOS（Linuxカーネル）の授業．
2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．

（AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
（スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．

こういった私から学べます．

C言語を独学で習得することは難しいです．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る

二分探索木の操作関数

二分探索木の操作関数を紹介します．

typedef enum { preorder, postorder, endorder, leaf } VISIT;
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, VISIT which,
                               int depth));
void twalk_r(const void *root,
                void (*action)(const void *nodep, VISIT which,
                               void *closure),
                void *closure);
void tdestroy(void *root, void (*free_node)(void *nodep));

typedef enum { preorder, postorder, endorder, leaf } VISIT;

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, VISIT which,

int depth));

void twalk_r(const void *root,

void (*action)(const void *nodep, VISIT which,

void *closure),

void *closure);

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

tsearch/tfind/twalk/tdelete関数は，二分探索木を操作する関数です．

これらの関数は，Knuth (6.2.2) Algorithm T（The Art of Computer ProgrammingのVolume 3の6.2.2項「Binary Tree Searching」（pp. 426--457））に基づいています．

木構造における各ノードの最初のフィールドは，対応するデータアイテムへのポインタです．

参照先のデータは，呼び出しプログラムで用意します．

comparは比較関数への関数ポインタです．

比較ルーチンは，アイテムへのポインタ2つを引数に持ちます．

比較ルーチンの返り値は，1つ目のアイテムが2つ目のアイテムよりも「小さい，等しい，大きい」によって，「負，0，正」の整数値でなければなりません．

tsearch関数は，木構造からアイテムを検索する関数です．

keyは，検索するアイテムへのポインタです．

rootpは木構造の根へのポインタへのポインタです．

木構造がノードを含まない場合，rootpの参照している変数はNULLに設定されていなければなりません．

木構造にアイテムが見つかった場合，tsearch関数はそのアイテムへのポインタを返します．

見つからなかった場合は，アイテムを木構造に追加し，追加したアイテムへのポインタを返します．

tfind関数は，tsearch関数に似ていますが，アイテムが見つからなかった場合はNULLを返す点が異なります．

tdelete関数は木構造からアイテムを削除します．

tdelete関数の引数はtsearch/tfind関数と同じです．

tsearch関数は，木の中の一致するノードへのポインタ，または新しく追加されたノードへのポインタを返します．

キーにマッチする項目が複数ある場合，そのノードを返す項目は不定です．

tdelete関数は，削除したノードの親ノードへのポインタを返します．

削除されたノードがルートノードであった場合，tdelete関数はアクセスしてはならないダングリングポインタを返します．

tsearch/tfind/tdelete関数は，rootpがNULLの場合はNULLを返します．

twalk関数は，二分木を深さ優先（depth-first）で，左から右に検索する関数です．

rootは起点となるノードへのポインタです．

rootに根以外のノードを指定すると，部分木が対象となります．

twalk関数は，ノードを訪れる度にユーザ関数actionを呼び出します．

内部ノードに対しては3回，葉に対しては1回呼び出しが行われます．

actionには以下の順に3つの引数が与えられます．

最初の引数：訪れたノードへのポインタです．ノードの構造体は規定されていないが，ポインタを要素へのポインタのポインタにキャストし，ノードに格納された要素にアクセスできます．アプリケーションは，この引数が指す構造体を変更してはなりません．
2番目の引数：内部ノードの場合は訪問回数に応じてpreorder，postorder，endorderのいずれかの整数，葉を最初に訪れた場合はleafの値が渡されます．
3番目の引数：ノードの深さで，根の場合は深さ0です．

twalk_r関数はtwalk関数と似ていますが，引数depthの代わりに引数closureポインタがアクションコールバックの各呼び出しに変更されずに渡されています．

closureポインタは，グローバル変数に頼ることなく，スレッドセーフな方法でコールバック関数との間で情報を渡すために利用できます．

tdestroy関数は，rootが指す木構造全体を削除し，tsearch関数で確保されたリソースを全て解放します．

木構造の各ノードについて，free_node関数が呼び出されます．

データへのポインタがこの関数の引数として渡されます．

例えば，malloc関数でリソースを確保した場合は，free関数のポインタを引数として渡します．

リソースを解放する処理が必要でなければ，free_nodeは何もしない関数へのポインタでなければなりません．

二分探索木の操作関数の使い方

二分探索木の操作関数の使い方は以下になります．

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <search.h>

static void *root = NULL;

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

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

  switch (which) {
  case preorder:
    break;

  case postorder:
    datap = *(int **) nodep;
    printf("%d\n", *datap);
    break;

  case endorder:
    break;

  case leaf:
    datap = *(int **) nodep;
    printf("%d\n", *datap);
    break;

  default:
    fprintf(stderr, "Error: unknown action %d\n", which);
    break;
  }
}

void free_node(void *nodep)
{
  /* do nothing. */
}

int main(void)
{
  int i;
  int array[] = {11, -100, 33, 22, 567, -44, 77};
  size_t size = sizeof(array) / sizeof(array[0]);
  int *key = &array[size - 1];

  for (i = 0; i < size; i++) {
    if (tsearch(&array[i], &root, compare) == NULL) {
      fprintf(stderr, "Error: insufficient memory\n");
      exit(i + 1);
    }
  }

  twalk(root, action);

  if (tfind(key, &root, compare) != NULL) {
    printf("%d is found and deleted.\n", array[size - 1]);
    tdelete(key, &root, compare);
  } else {
    fprintf(stderr, "%d is not found.\n", *key);
  }

  twalk(root, action);
  tdestroy(root, free_node);
  return 0;
}

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#define _GNU_SOURCE

#include <stdio.h>

#include <stdlib.h>

#include <search.h>

static void *root = NULL;

static int compare(const void *pa, const void *pb)

{

if (*(int *) pa < * (int *) pb) {

return -1;

} else if (*(int *) pa > *(int *) pb) {

return 1;

} else {

return 0;

}

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

{

int *datap;

switch (which) {

case preorder:

break;

case postorder:

datap = *(int **) nodep;

printf("%d\n", *datap);

break;

case endorder:

break;

case leaf:

datap = *(int **) nodep;

printf("%d\n", *datap);

break;

default:

fprintf(stderr, "Error: unknown action %d\n", which);

break;

}

void free_node(void *nodep)

{

/* do nothing. */

}

int main(void)

{

int i;

int array[] = {11, -100, 33, 22, 567, -44, 77};

size_t size = sizeof(array) / sizeof(array[0]);

int *key = &array[size - 1];

for (i = 0; i < size; i++) {

if (tsearch(&array[i], &root, compare) == NULL) {

fprintf(stderr, "Error: insufficient memory\n");

exit(i + 1);

}

twalk(root, action);

if (tfind(key, &root, compare) != NULL) {

printf("%d is found and deleted.\n", array[size - 1]);

tdelete(key, &root, compare);

} else {

fprintf(stderr, "%d is not found.\n", *key);

}

twalk(root, action);

tdestroy(root, free_node);

return 0;

}

実行結果は以下になります．

$ gcc tsearch.c
$ a.out 
-100
-44
11
22
33
77
567
77 is found and deleted.
-100
-44
11
22
33
567

$ gcc tsearch.c

$ a.out

-100

-44

567

77 is found and deleted.

-100

-44

567

まとめ

二分探索木の操作関数の使い方を紹介しました．

二分探索木の標準ライブラリ関数を利用する時に参考にして下さい．

ハッシュテーブルの管理関数を知りたいあなたはこちらからどうぞ．

【C言語】ハッシュテーブルの管理関数の使い方【hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数】

こういった悩みにお答えします．こういった私から学べます．ハッシュテーブルの管理関数ハッシュテーブルの管理関数を紹介します．

int hcreate(size_t nel);
ENTRY *hsearch(ENTRY item, ACTION action);
void hdestroy(void);
int hcreate_r(size_t nel, struct hsearch_data *htab);
int hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab);
void hdestroy_r(struct hsearch_data *htab)

int hcreate(size_t nel);

ENTRY *hsearch(ENTRY item, ACTION action);

void hdestroy(void);

int hcreate_r(size_t nel, struct hsearch_data *htab);

int hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab);

void hdestroy_r(struct hsearch_data *htab)

hc ...

続きを見る

C言語を独学で習得することは難しいです．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る

【C言語】二分探索木の操作関数の使い方【tsearch/tfind/tdelete/twalk/twalk_r/tdestroy関数】

元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

二分探索木の操作関数

二分探索木の操作関数の使い方

まとめ

【C言語】ハッシュテーブルの管理関数の使い方【hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数】

元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社