演習part2、およびAVL木
前回、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