ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 演習part2、およびAVL木

演習part2、およびAVL木

投稿者: in 情報構造論, 斉藤徹, 講義録 投稿日:

前回、2分木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。

2分木へのデータ追加と不均一な木の成長

先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。

しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか？

  • 86, 53, 11 – 降順のデータ
  • 12, 24, 42 – 昇順のデータ

この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。

AVL木

このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで改善が可能となる。例えば、以下のような木では、赤の左側に偏っている。

このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、木の段数を均一に近づけることができる。この例では、11,65,92の木が、右回転して 11 の木の位置が上がっている。(右回転)

この様に、左右の枝の大きさが不均一な場所を見つけ、右回転(もしくは左回転)を行う処理を繰り返すことで、段数が均一な2分木に修正ができる。この様な処理でバランスの良い木に修正された木は、AVL木と呼ばれる。

理解確認

  • 木の根からの段数を求める関数を作成せよ。
    例えば、上のAVL木の説明の図であれば、4段なので4を返すこと。
// 木の段数を数える関数
_____ tree_depth( _______________ p ) {
   if ( p == NULL ) {
      return _____ ;
   } else {
      int d_L = ______________ ;
      int d_R = ______________ ;
      if ( d_L > d_R )
         return _____ ;
      else
         return _____ :
   }
}

void main() {
   printf( "%d¥n" , tree_depth( top ) ) ;
}

デバッグのテクニック

課題のプログラムを作っているとき、動作に自信が無い時は、変数の中身を確認するための表示処理を埋め込むことが多い。しかし、プログラムが無事完成した後には、表示処理を消すことが多いだろう。この時、どのように命令を消すと良いのだろうか？

// /**/コメントで消す
void foo( int x ) {
   /* printf( "%d" , x ) ; */
}
// "//"で消す
void foo( int x ) {
   // printf( "%d" , x ) ;
}
void bar() { // "/**/"コメントは途中にコメントがあるとダメ
   /*
   a() ;
   b() ; /* comment */
   c() ;
   d() ;
   */
}
void bar() { // "//"コメントは全行に入れる必要あり
   // a() ;
   // b() ;
   // c() ;
   // d() ;
}

では、効率のよいコメントアウトはどうするのか？

void bar() {  // #if は、プリプロセッサで
#if 0         // 条件が偽の時は、#endifまでが消される。
   a() ;
   b() ;
   c() ;
   d() ;
#endif
}

一般的には、#if は、defined() と共に使われる。

#define DEBUG  // 完成したら、#defineの前に//を入れる。
  :
void bar() {
#if defined( DEBUG )
  :
#endif
}
// 通常は、コンパイルオプションを使うのが普通
// gcc -DDEBUG bar.c

タグ: ,