前回の授業で説明したハッシュ法は、データから簡単な計算(ハッシュ関数)で求まるハッシュ値をデータの記憶場所とする。しかし、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いか？

ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁の場所に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか？

オープンアドレス法

先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。

これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。

// オープンアドレス法
// table[] は大域変数で0で初期化されているものとする。

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 )
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故？
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ;
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 ) {
      if ( table[ idx ].phone == phone )
         return table[ idx ].name ;
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故？
   return NULL ; // 見つからなかった
}

• hash-openaddr.cxx

注意：このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。

この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。

チェイン法

前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。ハッシュ値を求めたら、そのリスト構造の中からひとつづつ目的のデータを探す処理となる。

この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。

#define SIZE 100
int hash_func( int ph ) {
   return ph % SIZE ;
}
struct PhoneNameList {
   int phone ;
   char name[ 20 ] ;
   struct PhoneNameList* next ;
} ;
struct PhoneNameList* hash[ SIZE ] ; // NULLで初期化

struct PhoneNameList* cons( int ph ,
                            char* nm ,
                            struct PhoneNameList* nx ) {
   struct PhoneNameList* ans ;
   ans = (struct PhoneNameList*)malloc(
                      sizeof( struct PhoneNameList ) ) ;
   if ( ans != NULL ) {
      ans->phone = ph ;
      strcpy( ans->name , nm ) ;
      ans->next = nx ;
   }
   return ans ;
}

void entry( int phone , char* name ) {
   int idx = hash_func( phone ) ;
   hash[ idx ] = cons( phone , name , hash[ idx ] ) ;
}
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   struct PhoneNameList* p ;
   for( p = hash[ idx ] ; p != NULL ; p = p->next ) {
      if ( p->phone == phone )
         return p->name ;
   }
   return NULL ;
}

• hash-chain.cxx

前半は中間試験の返却と解説を行う。後半は次のテーマのハッシュ法の導入話。

ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか？

究極のシンプルなやり方(メモリの無駄)

最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。

// メモリ無駄遣いな超高速方法
struct PhoneName {
   int  phone ;
   char name[ 20 ] ;
} ;

// 電話番号は6桁とする。
struct PhoneName table[ 1000000 ] ; // 携帯電話番号ならどーなる!?!?

// 配列に電話番号と名前を保存
void entry( int phone , char* name ) {
   table[ phone ].phone = phone ;
   strcpy( table[ phone ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   return table[ phone ].name ;
}

• hash0.cxx

しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。

ハッシュ法

先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。

// ハッシュ衝突を考えないハッシュ法

#define HASH_SIZE 100 ;
struct PhoneName table[ HASH_SIZE ] ;

// ハッシュ関数
int hash_func( int phone ) {
   return phone % HASH_SIZE ;
}

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   return table[ idx ].name ;
}

• hash1.cxx

ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。

たとえ話で言うなら、100個の椅子が連番付きで並んでいて、自分の電話番号末尾2桁の場所に座ろうとしたら、先に座っている人がいるような状態である。このような状態で、あなたなら何処に座るだろうか？

ハッシュ関数に求められる特性

ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムでなくなってしまう。このことから、ハッシュ関数には以下のような特徴が必要となる。

• 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
• 簡単な計算で求まること。
• 同じデータに対し常に、同じハッシュ値が求まること。

2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+　　# 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式を機械語の命令に置き換える際に役立つ。

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

逆ポーランド記法の式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '
// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
         //    ~~~~~~~~(B)
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}
' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
         //    ~~~~~~~~(B)
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}

• eval-rpn.cxx

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして、上記の構文木のデータを作る処理と、その構文木の値を計算するプログラムを示す。

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x ) // 数値のノード
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op , // 演算子のノード
                   struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {     // ~~~~~~~~~~~~~~~~~~~~~(D)
      n->data  = op ;
      n->left  = l ;
      n->right = r ;
   }
   return n ;
}
// 与えられた演算子の木を計算する関数
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL ) {
      // 数値のノードは値を返す
      return p->data ;
   } else {
      // 演算子のノードは、左辺値,右辺値を求め
      // その計算結果を返す
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }              // ~~~~~~~~~~~~~~~(E)      ~~~~~~~~(F)
   }
}

void main() {
   struct Tree* exp =  // 1+(2*3) の構文木を生成
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) ,
                        tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

• eval-tree.cxx

理解度確認

• push(),pop() のスタックは、保存と取り出しの順序を表す単語の頭文字4つを使って何と呼ばれるか？
• 上記プログラム中の(A)～(F)の型を答えよ。

前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:うちの子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　氷枕で病院　　解熱剤で病院　　速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ?" ,
                    dtree( "速攻で病院",NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",NULL,NULL ) ,
                    dtree( "氷枕で病院",NULL,NULL ) ) ) ;
   // 決定木をたどる
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

• decision-tree.cxx

コンパイラと言語処理系

2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

• インタプリタ(interpreter:通訳)
  • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
• コンパイラ(compiler:翻訳)
  • ソースプログラムから機械語を生成し、実行する際には機械語を実行
• トランスコンパイラ
  • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
    最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
• バイトコードインタプリタ
  • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
• エミュレーター
  • 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
    近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。
    • 同じCPUで異なるOSを動かす場合は、CPU仮想化。

に分けられる。

C言語で機械語が生成されるまで

C言語のプログラムから、機械語の命令が生成されるまでは、以下のような処理が行われる。
一般的にコンパイラの処理というと、ソースコードから機械語を生成するまでの処理を指すが、C言語ではプリプロセッサ処理を含んだり、コンパイラの処理(ソースコードからオブジェクトファイル生成まで)のほかにリンク処理を含んで使われることも多い。

foo.c C言語のソース
↓     プリプロセッサ処理
foo.c(#行の無いC言語のソース)
↓     コンパイラ
foo.obj(オブジェクトファイル/中間コード)
↓
(+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの)
↓     リンカ(リンケージエディタ)
foo.exe

コンパイラの処理

コンパイラが命令を処理する際には、以下の処理が行われる。

1. 字句解析(lexical analysys)
   文字列を言語要素(token)に分解
2. 構文解析(syntax analysys)
   tokenの並び順に意味を反映した構造を生成
3. 意味解析(semantics analysys)
   命令に合わせた中間コードを生成
4. 最適化(code optimization)
   中間コードを変形して効率よいプログラムに変換
5. コード生成(code generation)
   実際の命令コード(オブジェクトファイル)として出力

バイトコードインタプリタとは

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
　↓       Java コンパイラ
foo.class (中間コード)
　↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

トークンと正規表現(字句解析)

規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言　　　  「abd|acd」は、abd または acd にマッチする。
グループ化　「a(b|c)d」は、真ん中の c|b をグループ化
量化　　　　パターンの後ろに、繰り返し何回を指定
　　　　　　? 直前パターンが0個か1個
　　　　　　　「colou?r」
　　　　　　* 直前パターンが0個以上繰り返す
　　　　　　　「go*gle」は、ggle,gogle,google
　　　　　　+ 直前パターンが1個以上繰り返す
　　　　　　　「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
　　　　　　「[0-9]+」012,31415,...数字の列
^　　　　　行頭にマッチ
$　　　　　行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

• 情報処理技術者試験で出題された正規表現の問題と解説

構文とバッカス記法

言語の文法を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

　　＋
　／　＼
１　　　＊
　　　／　＼
　　23　　　456

理解度確認

• インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
• 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)

// 2分探索法
int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ;

int bin_search( int a[] , int key , int L , int R ) {
   // Lは、範囲の左端
   // Rは、範囲の右端+1 (注意!!)
   while( R > L ) {
      int m = (L + R) / 2 ;
      if ( a[m] == key )
         return key ;
      else if ( a[m] > key )
         R = m ;
      else
         L = m + 1 ;
   }
   return -1 ; // 見つからなかった
}

void main() {
   printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ;
}

一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか？

2分探索木

ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。

この枝の特徴は何だろうか？この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。

特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。

このデータ構造をプログラムで書いてみよう。

struct Tree {
   struct Tree* left ;
   int          data ;
   struct Tree* right ;
} ;

// 2分木を作る補助関数
struct Tree* tcons( struct Tree* L ,
                    int          d ,
                    struct Tree* R ) {
   struct Tree* n = (struct Tree*)malloc(
                       sizeof( struct Tree ) ) ;
   if ( n != NULL ) { /* (A) */
      n->left = L ;
      n->data = d ;
      n->right = R ;
   }
   return n ;
}

// 2分探索木よりデータを探す
int tree_search( struct List* p , int key ) {
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ; // 見つからなかった
}
struct Tree* top = NULL ;

void main() {
   // 木構造をtcons()を使って直接生成 (B)
   top = tcons( tcons( tcons( NULL , 13 , NULL ) ,
                       27 ,
                       tcons( NULL , 38 , NULL ) ) ,
                42 ,
                tcons( tcons( NULL , 64 , NULL ) ,
                       72 ,
                       tcons( NULL , 81 , NULL ) ) ) ;
   printf( "%d¥n" , tree_search( top , 64 ) ) ;
}

この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。

理解度確認

• 上記プログラム中の、補助関数tcons() の(A)の部分 “if ( n != NULL )…” の判定が必要な理由を答えよ。
• 同じくmain() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。

2分木に対する処理

2分探索木に対する簡単な処理を記述してみよう。

// データを探す
int search( struct Tree* p , int key ) {
   // 見つかったらその値、見つからないと-1
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ;
}
// データを全表示
void print( struct Tree* p ) {
   if ( p != NULL ) {
      print( p->left ) ;
      printf( "%d¥n" , p->data ) ;
      print( p->right ) ;
   }
}
// データ件数を求める
int count( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1
             + count( p->left )
             + count( p->right ) ;
}
// データの合計を求める
int sum( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data
             + count( p->left )
             + count( p->right ) ;
}
// データの最大値
int max( struct Tree* p ) {
   while( p->right != NULL )
      p = p->right ;
   return p->data ;
}

これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。

(2021/10/12)
print() の再帰の処理の流れを説明するなかで、「じゃあデータを降順で表示したかったらどうすればいい？」「じゃあ、データが根っこに近い方から表示したかったらどうすればいい？」みたいな話を、高専プロコンの競技部門の組み合わせ問題に考えてほしくなって、つぶやいちゃったもんだから、話がそれて「再帰で記載するのは、枝の先の処理が終わってから、残りの枝の処理を行うので、深さ優先探索法になる。」、「根っこに近い方から表示したかったら幅優先探索法」になるよ…という話をする。ついでの雑談で、「将棋とかチェスのプログラムだと、次の手を打った後の評価で先読みするけど、あれどうやってる？」という話をして、その中でαβ法というのがあってね…静的評価で良い手の候補を選び、その手は動的評価で再帰処理を行い、本当に良い手を選ぶ…という説明を行った。来週は、２分木の sum() とか count() を考えてもらうことから始めよう。

• 2分探索木の深さ優先探索と幅優先探索