2分探索木

後期最初の授業ということで、今までの内容の総括っぽい 質問を交えながらの授業。

単純リストでは、中央値の参照がO(N)であるため、 そのままでは２分探索法のような処理はできない。

そこで、データと２つの枝からなるノードを作り、 データより小さい値を要素にもつ枝を左に、 大きいものは右枝に格納し、この状態がどこでも成り立つようにする。この方式は、2分木(2分探索木)と呼ばれる。

struct Tree {
   int data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tcons( int v ,
                    struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = v ;
      n->left = l ;
      n->right = r ;
   }
   return n ;
}
int find( struct Tree* p , int key ) {
   while( p != NULL )
      if ( p->data == key )
         return 1 ;
      else if ( p->data < key )
         p = p->left ;
      else
         p = p->right ;
   }
   return 0 ;
}
void main() {
   struct Tree* top =
      tcons( 53 ,
         tcons( 28 ,
            tcons( 14 , NULL , NULL ) ,
            tcons( 40 , NULL , NULL ) ) ,
         tcons( 80 ,
            tcons( 63 , NULL , NULL ) ,
            tcons( 91 , NULL , NULL ) ) ) ;
   if ( find( top , 80 ) )
      printf( "find 80\n" ) ;
}

この方式であれば、m段のピラミッド状の木であれば、データ件数 N = 2^m-1となり、 m段が綺麗に充填されていれば、最悪の場合のループ回数がmであることから、 処理速度は、O(log(N))となる。

データの挿入では、NULLが入った末端まで辿り着いて、新しい枝を挿入することから、 挿入場所の決定(O(log N)),枝追加(O(1))の時間であり、配列(O(N))などに比べても高速となる。 ただし、このデータのような data 部が小さい場合には、data 1件につき2本のポインタを 使用することから、メモリの使用効率は良くない。

ヒープ

2分木とおなじ考え方で、配列の添字をうまくつかった方式にヒープがある。 この方式では、前述の2分探索木のデータを、配列に以下のように格納する。

この方式を取れば、i番目の要素の左枝は(i*2+1) , 右枝は(i*2+2)といった 簡単な計算で求められる。この方式であれば、ポインタは不要となる。 ただし、新たなデータの挿入処理では、段の上からデータを入れ替えを繰り返すなどの 処理が必要となる。

次回には、このデータを操作するための処理で、再帰呼び出しなどを用いる事例を紹介。