AVL木と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を返すこと。
// 木の段数を数える関数 _____ tree_depth( _______________ p ) { if ( p == NULL ) { return _____ ; } else { int d_L = ______________ ; int d_R = ______________ ; if ( d_L > d_R ) return _____ ; else return _____ : } } // pをつなぎ替え上部を返り値で返す。 struct Tree*rot_right( struct Tree* p ) { struct Tree* pl = p->left ; struct Tree* pr = pl->right ; pl->right = p ; p->left = = pr ; return pl ; } int main() { printf( "%d¥n" , tree_depth( top ) ) ; top = rot_right( top ) ; return 0 ; }
2分ヒープ(binary heap)
2分探索木では、1つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。
これらの問題の解決法の1つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝は 2×i+1 番目、右の枝は 2×i+2 番目であることが判る。
このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、O(log(N))で挿入が可能となる。
int a[ 7 ] = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ; // 2分ヒープを表示 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 ) ; } } // 2分ヒープから key を検索 int find_heap( int array[] , int idx , int size , int key ) { while( idx < size ) { if ( array[ idx ] == key ) return idx ; // 見つかったら配列の番号を返す else if ( array[ idx ] _____ key ) // 何が入るか考えよう idx = ________________ ; else idx = ________________ ; } return -1 ; // 見つからなかったら、-1 を返す } int main() { print_heap( a , 0 , 7 ) ; if ( find_heap( a , 0 , 7 , 65 ) >= 0 ) printf( "Find!!¥n" ) ; return 0 ; }
レポート課題
以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。
- 名前(name)と電話番号(phone)
- 名前(name)と誕生日(year,mon,day)
- 名前(name)とメールアドレス(mail)
プログラムは以下の機能を持つこと。
- 1行1件でデータを入力し、2分木に追加できること。
- 全データを昇順(or降順)で表示できること。
- 検索条件を入力し、目的のデータを探せること。
レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。
集約関数と副問い合わせ
特殊な条件演算子
WHERE 節の中で使える特殊な条件演算子を紹介する。
... AND ... WHERE S.業者番号 <= 100 AND S.業者番号 >= 200 ; ... OR ... WHERE S.業者番号 >= 100 OR S.業者番号 <= 200 ; NOT ... WHERE NOT S.業者番号 >= 100 ; ... IN ... WHERE S.業者番号 IN ( 'S1' , 'S4' ) ; ... BETWEEN A AND B WHERE S.優良度 BETWEEN 50 AND 100 ; ... LIKE ... WHERE S.業者名 LIKE 'A_C社' ; _ は任意の1文字 ABC社 ADC社 WHERE S.業者名 LIKE 'A%社' ; % は任意の0~N文字 A社, AA社 ABC社 ... IS NULL WHERE S.業者名 IS NULL WHERE S.業者名 IS NOT NULL
集約関数
集約関数は、SQL の SELECT の射影部分で使える関数で、出力対象となった項目に対して、COUNT(),SUM(),AVG()といった計算を行うもの。
COUNT() - 項目の数 SUM() - 項目の合計 AVG() - 項目の平均 MAX() - 項目の最大値 MIN() - 項目の最低値 SELECT COUNT(S.業者番号) FROM S WHERE S.優良度 > 20 ;
集合計算
複数の SQL の結果に対し、集合和, 集合積, 集合差などの処理を行う。
... UNION ... 集合和 ... EXPECT ... 集合差 ... INTERSECT ... 集合積 SELECT S.業者名 FROM S WHERE S.所在 = '福井' UNION SELECT S.業者名 FROM S WHERE S.所在 = '東京'
SQLの副問い合せ
前節の結合処理は時として効率が悪い。このような場合は、副問い合わせを用いる場合も多い。
SELECT S.業者名, S.所在 FROM S WHERE S.業者番号 IN ( SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = 'G2' AND SG.在庫量 >= 200 ) ;
まず、『◯ IN { … }』 の比較演算子は、◯が{…}の中に含まれていれば真となる。また、SQLの中の (…) の中が副問い合わせである。
この SQL では、副問い合わせの内部には、テーブル S に関係する要素が含まれない。この場合、副問い合わせ(商品番号がG2で在庫量が200以上)は先に実行される。
{ (S1,G2,200), (S2,G2,400), (S3,G2,200), (S4,G2,200) }が該当し、その業者番号の{ S1, S2, S3, S4 }が副問い合わせの結果となる。最終的に SELECT … FROM S WHERE S.業者番号 IN { ‘S1’, ‘S2’, ‘S3’, ‘S4’ } を実行する。
相関副問い合わせ
SELECT G.商品名, G.色, G.価格 FROM G WHERE 'S4' IN ( SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = G.商品番号 ) ;
この副問い合わせでは、内部に G.商品番号 が含まれており、単純に()内を先に実行することはできない。こういった副問い合わせは、相関副問い合わせと呼ばれる。
処理は、Gのそれぞれの要素毎に、副問い合わせを実行し、その結果を使って WHERE節の判定を行う。WHERE節の選択で残った結果について、射影で商品名,色,価格が抽出される。
// 概念の説明用に、C言語風とSQL風を混在して記載する for( int i = 0 ; i < sizeofarray( G ) ; i++ ) { SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = G[i].商品番号 を実行 if ( WHERE 'S4' IN 副query の結果が真なら ) { printf( ... ) ; } } // 全てのG 副queryの結果 WHERE 射影 // G1 -> {S1,S2} // G2 -> {S1,S2,S3,S4} -> ◯ -> (ノート,青,170) // G3 -> {S1} // G4 -> {S1,S4} -> ◯ -> (消しゴム,白,50) // G5 -> {S1,S4} -> ◯ -> (筆箱,青,300) // G6 -> {S1}
演習課題
Paiza.io などを使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。
さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。
考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。