ホーム » 「2分探索法」タグがついた投稿

タグアーカイブ: 2分探索法

2021年10月
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最新の投稿(電子情報)

アーカイブ

カテゴリー

2分探索木

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

繰り返し処理と処理時間の見積もり

単純サーチの処理時間

ここで、プログラムの実行時間を細かく分析してみる。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int a[ SIZE ] ; // 配列
int size ;      // 実際のデータ数(Nとする)
int key ;       // 探すデータ
for( int i = 0 ; i < size ; i++ )
   if ( a[i] == key )
      break ;

例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その1つ1つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を とする。

この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。

ここで例題

この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか?

感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、Tβ,Tα は何秒だったのだろうか? 上記のT(N)=Tα+NTβ に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。

ここで一番のポイントは、データ処理では N が小さな値の場合はあまり考えない。N が巨大な値であれば、Tαは、1000Tβに比べれば微々たる値という点である。よって

で考えれば良い。これであれば、T(1000)=5μ秒=Tβ×1000 よって、Tβ=5n秒となる。この結果、T(10000)=Tβ×10000=50μ秒 となる。

2分探索法と処理時間

次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。

// ((case-2))
// 2分探索法
int L=0 , R=size ; // プログラムは複雑になった 
while( L != R ) {
   int M = (L + R) / 2 ;
   if ( a[M] == key )
      break ;
   else if ( a[M] < key )
      L = M + 1 ;
   else
      R = M ;
}

このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。

    …両辺のlogをとる

2分探索は、繰り返し処理であるから、処理時間は、

ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式で係数が出てくるが、これはTβに含めて考えればいい。

単純なソート(選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。

int a[ 1000 ] = { 対象となるデータ } ;
int size = N ;

for( int i = 0 ; i < size - 1 ; i++ ) {
    int tmp ;
    // i..size-1 の範囲で一番大きいデータの場所を探す
    int m = i ;
    for( int j = i + 1 ; j < size ; j++ ) {
        if ( a[j] > a[m] )
            m = j ;
    }
    // 一番大きいデータを先頭に移動
    tmp = a[i] ;
    a[i] = a[m] ;
    a[m] = tmp ;
}

このプログラムの処理時間T(N)は…

… i=0の時
… i=1の時
:
         … i=N-1の時

        …(参考 数列の和の公式)

となる。

オーダー記法

ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。

単純サーチ
2分探索法
最大選択法

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ オーダーNのアルゴリズム
2分探索法 オーダー log N のアルゴリズム
最大選択法 オーダー N2 のアルゴリズム

練習問題

  1. ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか?
  2. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
    データ10000件なら何[sec]かかるか?
    (ヒント: 底変換の公式)
  3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このようなアルゴリズムの例を答えよ。
  4. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?
    (ヒント: ロピタルの定理)
  • 2と4の解説
  • 1は、N→∞において、N2<<2Nなので、O(2N) 。厳密に回答するなら、練習問題4と同様の説明を行う。
  • 3は、O(1)。誤答の例:O(0)と書いちゃうと、T(N)=Tα×0=0になってしまう。事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)

再帰呼び出しの予習

次の講義の基礎を確認という意味で、再帰呼出しと簡単な処理の例を説明する。

最初に定番の階乗(fact)

次に、フィボナッチ数列の場合

次の講義への導入問題

ここで示す導入問題をすべて答えるには、若干の予習が必要です。まずはどういう考え方をすれば解けるかな…を考えてみてください。

  • fact(N)の処理時間を、のような式で表現し、処理時間をオーダ記法で答えよ。
  • 以下のプログラムの実行結果を答えよ。また、関数sum()の処理時間を対象となるデータ件数N=RLを用いてのような式で表現せよ。
int a[] = { 1 , 5 , 8 , 9 , 2 , 3 , 4 , 7 } ;
int sum( int a[] , int L , int R ) {
   if ( R-L == 1 ) {
      return a[L] ;
   } else {
      int M = (L + R) / 2 ;
      return sum( a , L , M ) + sum( a , M , R ) ;
   }
}
int main() {
   printf( "%d¥n" , sum( a , 0 , 8 ) ) ;
   return 0 ;
}

2分探索木

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば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 ;
}

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

再帰方程式の理解度確認の解答

再帰呼び出しと再起方程式の資料の中の「理解度確認」の解答

解答

pyraをループで

// pyra() をループで書いたら。
int pyra( int x ) {
   int ans = 0 ;
   for( int i = 1 ; i <= x ; i++ )
      ans += i * i ;
   return ans ;
}

2分探索法を再帰で

// 2分探索を再帰で書いたら
int find( int array[] , int L , int R , int key ) {
   if ( R == L ) {
      return 0 ; // みつからない
   } else {
      int M = (L + R) / 2 ;
      if ( array[ M ] == key )     // みつかった
         return 1 ;           
      else if ( array[ M ] > key ) // 左側にある - 末尾再帰
         return find( array , L , M , key ) ;
      else                         // 右側にある
         return find( array , M+1 , R , key ) ;
   }
}

このプログラムでは、検索する範囲がLとRで与えられ、この範囲の幅が再帰が呼び出される毎に半分になっていく。

であれば、処理時間は対象となるデータ件数 N = R – L によって、処理時間は変化するので、T(N) で考えると、(ただし途中でデータが見つからない最悪の場合で式を示す)

データ件数0件では、if,R==L,return 0の処理を行う。このため、以下の様な再帰方程式の細小時での処理時間は、

  … ①

となる。(find(件数=1)の次は必ずfind(件数=0)が実行されるのででも良い。)

Nは整数という条件をつけないと、N=1/2, 1/4, 1/8…で止まらない…と勘違いする人もいるし、データ件数が1件になったら再帰がとまると考えた方が分かりやすいので、の方が都合がいいかな…

データが1以上の時で、対象データが L..Mの範囲にあるのなら、再帰の時に対象データ件数は半分になるから、if,R==L,else,if,array[M]==key,else-if,array[M]>keyの処理時間(Tb) と find(…,L,M,…) の処理時間を要するので、次の式となる。

  … ②

一方、(M+1)..Rの範囲にあるのなら同様に、if,R==L,else,if,array[M]==key,else-if,array[M]>key,elseの処理時間(Tc)と、find(…,M+1,R,…) の処理時間なので、

  … ③

となる。ただ、処理時間の見積もりでは厳密な分析が求められないので、(N-1)/2 だと一般式が複雑になるので、N/2 で考える。さらにTbTcの処理時間は少しの時間の違いだし、確率1/2でTbTcのどちらかを実行するので、その平均時間をTbで表すことにすれば、③は②とほぼ同じと見なすことができるので、再帰方程式は①と②で良い。

fib()の再帰方程式

再帰のフィボナッチ数 fib() の処理時間に相応しい再帰方程式は、xの値(Nとする)が2以下の時は、return を実行するだけ。3以上の時は、if,else,return,+ の処理時間と、fib(x-2)の処理時間、fib(x-1)の処理時間を要する。

よって、再帰方程式は、以下の式となる。

これを代入法で一般式を求めると、T(N)=fib(N-2)×Tb+fib(N+1)×Tかな?よって、再帰のfib()の処理時間は、フィボナッチ数に比例する。ちなみに、フィボナッチ数ピネの公式で一般項が示されているので、処理時間のオーダーは、次式となる。

ループ処理時間とオーダー記法と再帰

先週に、単純繰り返し処理の時間分析をやったので、次のステップに。

2分探索法の処理時間

データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。

// 2分探索法 O(log N)
int a[ 1000 ] = { 対象となるデータ } ;
int size = N ;  // データ数 N
int L = 0 ;     // L=下限のデータの場所
int R = size ;  // R=上限のデータ+1の場所
while( L != R ) {
   int M = (L + R) / 2 ;  // 計算は整数型で行われることに注意
   if ( a[M] == key )     // 見つかった
      break ;
   else if ( a[M] < key ) // |L         |M.         |R
      L = M + 1 ;         // |----------|-+---------|
   else                   // |L---------|M|
      R = M ;             //              |M+1------|R
}

上記のようなプログラムの場合、処理に要する時T(N)は、

 # Mは繰り返し回数

処理は、対象となるデータ件数が繰り返し毎に半分となり、対象データ件数が1件になれば処理が終わる。このことから、

となることから、 の関係が成り立つ。よって、は、以下のように表せる。

単純なソート(最大選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

int a[ 1000 ] = { 対象となるデータ } ;
int size = N ;

for( int i = 0 ; i < size - 1 ; i++ ) {
    int tmp ;
    // i..size-1 の範囲で一番大きいデータの場所を探す
    int m = i ;
    for( int j = i + 1 ; j < size ; j++ ) {
        if ( a[j] > a[m] )
            m = j ;
    }
    // 一番大きいデータを先頭に移動
    tmp = a[i] ;
    a[i] = a[m] ;
    a[m] = tmp ;
}

このプログラムの処理時間T(N)は… (参考 数列の和の公式)

となる。

オーダー記法

ここまでのアルゴリズムをまとめると、処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。

単純サーチ
2分探索法
最大選択法

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ オーダーNのアルゴリズム
2分探索法 オーダー log N のアルゴリズム
最大選択法 オーダー N2 のアルゴリズム

練習問題

  1. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
    データ10000件なら何[sec]かかるか?
    (ヒント: 底変換の公式)
  2. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このようなアルゴリズムの例を答えよ。
  3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?
    (ヒント: ロピタルの定理)

再帰呼び出しの予習

若干、時間が余ったので、再帰呼出しと簡単な処理の例を説明する。

最初に定番の階乗(fact)

次に、フィボナッチ数列の場合

2分探索木

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば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)の処理時間がかかるため、先頭からデータを探すため、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 ) {
      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 &gt key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ; // 見つからなかった
}
struct Tree* top = NULL ;

void main() {
   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つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。

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 ;
}