前回、2分木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。
2分木へのデータ追加と不均一な木の成長
先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。
しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか？
- 86, 53, 11 – 降順のデータ
- 12, 24, 42 – 昇順のデータ
この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。
AVL木
このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで改善が可能となる。例えば、以下のような木では、赤の左側に偏っている。
このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、木の段数を均一に近づけることができる。この例では、11,65,92の木が、右回転して 11 の木の位置が上がっている。(右回転)
この様に、左右の枝の大きさが不均一な場所を見つけ、右回転(もしくは左回転)を行う処理を繰り返すことで、段数が均一な2分木に修正ができる。この様な処理でバランスの良い木に修正された木は、AVL木と呼ばれる。
理解確認
- 木の根からの段数を求める関数 tree_depth() を作成せよ。
例えば、上のAVL木の説明の図であれば、4段なので4を返すこと。 - malloc() 関数を使うために必要な #include のヘッダファイルは何か?
// 木の段数を数える関数
_____ 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 ) ) ;
}
2分ヒープ
2分探索木では、１つのノードにつき2つのポインタを持ちメモリの使用が多い。配列を用いて2分探索木を作る方法として、2分ヒープがある。通常の2分探索法のように配列内に昇順でデータを保存すると、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。しかし、2分木の上から番号を以下の様に振ると、i番目の、左の枝は 2*i+1 番目、右の枝は 2*i+2 番目であることが判る。
このような配列の使い方を、2分ヒープと呼ぶ。この方式ではれば、アルゴリズムの説明は省略するが、O(log(N))で挿入が可能となる。
int a[ 7 ] = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;
void print_heap( int array[] , int idx , int size ) {
if ( idx < size ) {
// 左の枝を表示
print_heap( array , 2*idx + 1 , size ) ;
// 真ん中の枝を表示
printf( "%d " , array[ idx ] ) ;
// 右の枝を表示
print_heap( array , 2*idx + 2 , size ) ;
}
}
void main() {
print_heap( a , 0 , 7 ) ;
}