C LANGUAGE TECHNOLOGY

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

悩んでいる人

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

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

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

二分探索木の操作関数

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

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は何もしない関数へのポインタでなければなりません.

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

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

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

まとめ

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

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

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

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

こういった悩みにお答えします. こういった私から学べます. 目次1 ハッシュテーブルの管理関数2 ハッシュテーブルの管理関数の使い方2.1 hcreate/hsearch/hdestroy関数の使い方 ...

続きを見る

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

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

友だち追加

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

-C LANGUAGE, TECHNOLOGY
-, , , , , ,