先週の2分木の概念を分かってもらうための基本に引き続き、 今週は2分木の様々な操作プログラムを説明する。
2分木と再帰
先週の授業の最後では、データ数カウントを再帰で説明したので、 違う視点の再帰ということで、ループ版の代わりの再帰版を説明し、 今週は課題の合計と全データ表示などを演習とした。
int find( struct Tree* p , int key ) { if ( p == NULL ) return 0 ; // 見つからない else if ( p->data == key ) return 1 ; // みつかった else if ( p->data > key ) return find( p->left , key ) ; else return find( p->right , key ) ; }
ちなみに、上記のようなfindは、処理の末端に再帰呼び出しが書かれているため、 一般的に末尾再帰呼び出しと呼ばれ、コンパイラによっては最適化によって ループ処理に置き換えられるかもしれない…といった説明もしておく。
void print( struct Tree*p ) { if ( p != NULL ) { print( p->left ) ; printf( "%d" , p->data ) ; print( p->right ) ; } }
上記のprintを演習とした際には、「全データを表示せよ」としか説明しなかったので、 学生さんの解いてくれたプログラムの表示順序をトレースし、 改めて上記のプログラムを示し、表示順序が「小さいもの順」となることを説明する。
データの追加処理
struct Tree* top = NULL ; void entry( int key ) { struct Tree** tail = &top ; while( *tail != NULL ) { if ( (*tail)->data == key ) break ; else if ( (*tail)->data > key ) tail = &( (*tail)->left ) ; else tail = &( (*tail)->right ) ; } if ( *tail == NULL ) *tail = tcons( key , NULL , NULL ) ; }
データの追加処理として、上記プログラムを示す。 この動作トレースにて、昇順済みのデータを与えた場合、 一方向にだけ伸びる効率の悪いO(N)木が生成される可能性を説明する。 さらに、この対応としてバランスを修正したAVL木について、紹介する。
2分木の利点欠点とハッシュ
最後にまとめとして、2分木の利点欠点をまとめる。 2分木は、検索がO(log N),追加もO(log N)であることを示す。 しかし欠点として、メモリの使用効率が悪いことなども説明。 この際に、配列の2分探索法は、データ追加では挿入場所を作るために、 データを(平均N/2回)ループでずらす処理が必要であり、O(N)で効率が 悪いことを説明する。そして、この改善のための方法として、 ハッシュがあることを説明する。
+--+--+--+--+--+--+--+---+ index| 0| 1| 2| 3| 4| 5| 6|...| value|53|28|76|13|30|62|90|...| +--+--+--+--+--+--+--+---+ i番目のデータの 左の枝は、(i*2+1)番目 右の枝は、(i*2+2)番目