ホーム » 「2分探索木」タグがついた投稿
タグアーカイブ: 2分探索木
2分探索木にデータ追加と演習
2分探索木にデータを追加
前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになるだろう。
struct Tree* top = NULL ;
// 2分探索木にデータを追加する処理
void entry( int d ) {
struct Tree** tail = &top ;
while( *tail != NULL ) {
if ( (*tail)->data == d ) // 同じデータが見つかった
break ;
else if ( (*tail)->data > d )
tail = &( (*tail)->left ) ; // 左の枝に進む
else
tail = &( (*tail)->right ) ; // 右の枝に進む
}
if ( (*tail) == NULL )
*tail = tcons( NULL , d , NULL ) ;
}
int main() {
char buff[ 100 ] ;
int x ;
while( fgets( buff , sizeof( buff ) , stdin ) != NULL )
if ( sscanf( buff , "%d" , &x ) != 1 )
break ;
entry( x ) ;
return 0 ;
}
このプログラムでは、struct Tree** tail というポインタへのポインタ型を用いている。tail が指し示す部分をイメージするための図を以下に示す。
理解確認
- 関数entry() の14行目の if 判定を行う理由を説明せよ。
- 同じく、8行目の tail = &( (*tail)->left ) の式の各部分の型について説明せよ。
- sscanf() の返り値を 1 と比較している理由を説明せよ。
- entry() でデータを格納する処理時間のオーダを説明せよ。
// 前述プログラムは、データ追加先が大域変数なのがダサい。 // 局所変数で追加処理ができるように、したいけど... void entry( struct Tree* top , int d ) { struct Tree** tail = &top ; while( *tail != NULL ) { : // 上記の entry() と同じとする } void main() { // 追加対象の top は局所変数 struct Tree* top = NULL ; char buff[ 100 ] ; int x ; while( fgets(buff,sizeof(buff),stdin) != NULL ) { if ( sscanf( buff , "%d" , &x ) != 1 ) break ; entry( top , x ) ; } }上記のプログラム↑は動かない。なぜ？
このヒントは、このページ末尾に示す。
演習課題
以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。
- 名前(name)と電話番号(phone)
- 名前(name)と誕生日(year,mon,day)
- 名前(name)とメールアドレス(mail)
プログラムは以下の機能を持つこと。
- 1行1件でデータを入力し、2分木に追加できること。
- 全データを昇順(or降順)で表示できること。
- 検索条件を入力し、目的のデータを探せること。
レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。考察のネタが無い人は、このページの理解確認の内容について記述しても良い。
// プログラムのおおまかな全体像の例
struct Tree {
//
// この部分を考えて
// 以下の例は、名前と電話番号を想定
} ;
struct Tree* top = NULL ;
void tree_entry( char n[] , char ph[] ) {
// n:名前,ph:電話番号 を追加
}
void tree_print( struct Tree* p ) {
// 全データを表示
}
struct Tree* tree_search_by_name( char n[] ) {
// n:名前でデータを探す
}
int main() {
char name[ 20 ] , phone[ 20 ] ;
char buff[ 1000 ] ;
struct Tree* p ;
// データを登録する処理(空行を入力するまで繰り返し)
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
if ( sscanf( buff , "%s%s" , name , phone ) != 2 )
break ; // 入力で、2つの文字列が無い場合はループを抜ける
tree_entry( name , phone ) ;
}
// 全データの表示
tree_print( top ) ;
// データをさがす
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
if ( sscanf( buff , "%s" , name ) != 1 )
break ; // 入力で、1つの文字列が無い場合はループを抜ける
if ( (p = tree_search_by_name( name )) == NULL )
printf( "見つからない¥n" ) ;
else
printf( "%s %s¥n" , p->name , p->phone ) ;
}
return 0 ;
}
動かないプログラムのヒント
// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...
// ちなみに、こう書くと動く
// Tree*を返すように変更
struct Tree* entry( struct Tree* top , int d ) {
:
// 最初の entry と同じ
:
return top ;
}
void main() {
// 追加対象のポインタ
struct Tree* top = NULL ;
while( ... ) {
:
// entry() の返り値を top に代入
top = entry( top , x ) ;
}
}
fgets()とsscanf()による入力の解説
前述のプログラムの入力では、fgets() と sscanf() による処理を記載した。この関数の組み合わせが初見の人も多いと思うので解説。
// scanf() で苦手なこと -------------------------//
// scanf() のダメな点
// (1) 何も入力しなかったら...という判定が難しい。
// (2) 間違えて、abc みたいに文字を入力したら、
// scanf()では以後の入力ができない。(入力関数に詳しければ別だけどさ)
int x ;
while( scanf( "%d" , &x ) == 1 ) {
entry( x ) ;
}
// scanf() で危険なこと -------------------------//
// 以下の入力プログラムに対して、10文字以上を入力すると危険。
// バッファオーバーフローが発生する。
char name[ 10 ] ;
scanf( "%s" , name ) ;
// 安全な入力 fgets() ---------------------------//
// fgets() は、行末文字"¥n"まで配列 buff[]に読み込む。
// ただし、sizeof(buuf) 文字より長い場合は、途中まで。
char buff[ 100 ] ;
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
// buff を使う処理
}
// 文字列からデータを抜き出す sscanf() -------------//
// sscanf は、文字列の中から、データを抜き出せる。
// 入力が文字列であることを除き、scanf() と同じ。
char str[] = "123 abcde" ;
int x ;
char y[10] ;
sscanf( str , "%d%s" , &x , y ) ;
// x=123 , y="abcde" となる。
// sscanf() の返り値は、2 (2個のフィールドを抜き出せた)
理解確認
- 標準入力からの1行入力関数 gets() 関数が危険な理由を説明せよ。
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。
// 2分探索法
int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ;
int bin_search( int a[] , int key , int L , int R ) {
// Lは、範囲の左端
// Rは、範囲の右端+1 (注意!!)
while( R > L ) {
int m = (L + R) / 2 ;
if ( a[m] == key )
return key ;
else if ( a[m] > key )
R = m ;
else
L = m + 1 ;
}
return -1 ; // 見つからなかった
}
void main() {
printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ;
}
一方、リスト構造ではデータ列の真ん中のデータを取り出すのにO(N)の処理時間がかかるため、先頭からデータを探すため、O(N)となってしまい、極めて効率が悪い。リスト構造でもっとデータを高速に探すことはできないものか？
2分探索木
ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。
この枝の特徴は何だろうか？この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。
特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。
このデータ構造をプログラムで書いてみよう。
struct Tree {
struct Tree* left ;
int data ;
struct Tree* right ;
} ;
// 2分木を作る補助関数
struct Tree* tcons( struct Tree* L ,
int d ,
struct Tree* R ) {
struct Tree* n = (struct Tree*)malloc(
sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->left = L ;
n->data = d ;
n->right = R ;
}
return n ;
}
// 2分探索木よりデータを探す
int tree_search( struct List* p , int key ) {
while( p != NULL ) {
if ( p->data == key )
return key ;
else if ( p->data > key )
p = p->left ;
else
p = p->right ;
}
return -1 ; // 見つからなかった
}
struct Tree* top = NULL ;
void main() {
top = tcons( tcons( tcons( NULL , 13 , NULL ) ,
27 ,
tcons( NULL , 38 , NULL ) ) ,
42 ,
tcons( tcons( NULL , 64 , NULL ) ,
72 ,
tcons( NULL , 81 , NULL ) ) ) ;
printf( "%d¥n" , tree_search( top , 64 ) ) ;
}
この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。
2分木に対する処理
2分探索木に対する簡単な処理を記述してみよう。
// データを探す
int search( struct Tree* p , int key ) {
// 見つかったらその値、見つからないと-1
while( p != NULL ) {
if ( p->data == key )
return key ;
else if ( p->data > key )
p = p->left ;
else
p = p->right ;
}
return -1 ;
}
// データを全表示
void print( struct Tree* p ) {
if ( p != NULL ) {
print( p->left ) ;
printf( "%d¥n" , p->data ) ;
print( p->right ) ;
}
}
// データ件数を求める
int count( struct Tree* p ) {
if ( p == NULL )
return 0 ;
else
return 1
+ count( p->left )
+ count( p->right ) ;
}
// データの合計を求める
int sum( struct Tree* p ) {
if ( p == NULL )
return 0 ;
else
return p->data
+ count( p->left )
+ count( p->right ) ;
}
// データの最大値
int max( struct Tree* p ) {
while( p->right != NULL )
p = p->right ;
return p->data ;
}
