3 2分木を使ったツリーマップ

以前学習した2分木を使ったツリーであれば，探索と追加，削除が $O(\log_2 N)$ 程度とな り，リストやソートされた配列よりも高速である．そのためには，英単語のスペルの大小 関係の比較が出来ることが条件で，C言語ではstrcmp()という関数が用意されている． この関数は，次のようになっている．

	#include <string.h>
	int strcmp(char *s1, char *s2);

ヘッダーファイルstring.hが必要で，ポインターs1とs2が示す文字列を 比較する．文字列の大小は辞書順となる．比較の結果は，戻り値により表され，以下のようになる．

表 3: strcompの戻り値

s1 > s2	正
s1 = s2	0
s1 < s2	負

後は今まで学習したとおりであるが，もう一度，C言語のプログラムの書き方の復習をし ておく．まずは，構造体であるが，次のように定義する．

	typedef struct tag_word{
	  char *english;
	  char *japanese;
	  struct tag_word *left;
	  struct tag_word *right;
	}word_node;

メモリーの確保とデータの代入とデータの取り出しは，次のようにする．

  word_node *cc;

  cc=(word_node *)malloc(sizeof(word_node));

  cc->english="apple";
  cc->japanese="リンゴ";
  cc->left=NULL;
  cc->right=NULL;

  printf("%s\t%s\n",cc->english,cc->japanese);
 

後は，学習したとおりで，2分木で表すと図2のようになる．

図 2: 2分木を用いたマップ．アルファベット順にソートしている．

ホームページ: Yamamoto's laboratory
著者: 山本昌志