Document

２分探索と２分木
・２分探索
・ヒープ
・２分木
データを検索
・データの利用において、検索は基本のひとつ
・「データの中にこれはありますか？」という質問（こういう質
問をクエリーという）にすばやく答える方法を考えよう
－１つの方法は、バケツやハッシュを使うもの
・データのため方ではなく、検索方法のほうからアプローチ
してみよう
辞書を引く
・例えば、辞書をひく、という操作を考えよう
・何かひきたい言葉があるときに、それを辞書の中からどう
やって見つけ出すか？？
 適当にひらき、そこのページに言葉があるか調べ、な
ければそこの前か後ろを調べる
 言葉が含まれるページの候補を絞り込んでいる
・この方法を真似よう
２分探索（２分検索）
・簡単のため、データは数値の集まりとする
・まず、データを小さい順にソートして並べておく。 s をデータ
の先頭の添え字、 t をデータの最後の添え字とする
・ q はありますか、と質問が来たら、まず、真ん中を見る
 q と一致するなら、ありましたよ、と場所を返す
 一致しなければ、q と真ん中を比べて、探索範囲を絞る
t
s
１
３
７
８
９
１１１３１７１８１９
探索範囲の絞込み
・ q より真ん中が大きい
 q があるとすれば、真ん中より前
 t を、真ん中より１つ前に設定、再帰的に検索
・ q より真ん中が小さい
 q があるとすれば、真ん中より後ろ
 s を、真ん中より１つ後ろに設定、再帰的に検索
・ s より t のほうが小さくなったら終了
・探索範囲は、（およそ）半分半分と減っていく
t
s
１
３
７
８
９
s
t
１１１３１７１８１９
２分探索の計算時間
・問題毎回、探索範囲が半分以下になる
 log2 n 回後には、探索範囲の大きさが１になり、終了する
計算時間は O(log2 n) 、情報理論的に最適
・メモリは O(n)。しかも、in place。最適
・つまりは、非常にすばらしい
練習問題
・以下の数列で、8,17,19 を２分探索で検索せよ（s,t がどのよ
うに変化するか、記録すること）
１
３
７
８
９
１１１３１７１８１９
配列データの弱み
・配列データを保持する場合、挿入や削除をするのは大変
 O(n) 時間かかる
・リストを使うと挿入削除は速いが、「真ん中を見つける」のに
時間がかかる
（先の例題のように、いくつか真ん中を保持する手もあるが、そ
うすると真ん中を保持する時間がかかる）
・一般に、挿入も削除も検索も更新も速い、というのは、それ
ほど自明なことではない
・しかし、手はある
まずは最小値から
・挿入削除が速くて、かつどのセルを見つけるのも速い、は欲
張りなので、まずは、「最小値を見つけるのが速い」としよう
問題設定：
・データ（数値）を保持すること
・データの挿入＆削除（あるいは単に最小値の削除）は短時
間でできること
・データの中の最小値が（いつでも）短時間で取り出せること
・一般に、このような機能を持つデータ構造をヒープという
最強を決める
・学校で一番足の速い人を決めよう
・こういう場合、全員一度にレースをすることはできないので、
まず、各クラスで一番を決め、各クラス1番の中でさらに一番
を決める
・クラスの中も、さらに小さいグループに分けて決める
・高校野球は、最強を決めるのに、一回 2チームしか評価でき
ないので、トーナメントをする
最小を決める
・数値データでも同じようにトーナメントをしたとしよう
（最小を決めるトーナメント）
・さて、数値が１つ、値が変わった場合、最小が変わるかもしれ
ないが、どうチェックしたらいいだろう
・数値が小さくなった場合は簡単。最小と、変わった数値を比
べればいい。つまり、数値の挿入＆数値の変化は小さくしか
ならない、ならば最小値だけ覚えておけば十分
・最小値が大きくなった場合
（あるいは削除した場合）、最小値を
計算しなおさなければならない？？？
再計算は一部でいい
・最小値が大きくなった場合、どこを計算しなおさなければいけ
ないだろうか？
 実は、全部ではない
・数値が変わったものから上に行くルート上の対戦カードだけ、
チェックしなおせばいい
・逆に見れば、自分の下に変化した
数値がある対戦カードだけ、
チェックしなおせばいい
再計算の計算時間
・再計算の手間はどれくらい？
 トーナメント表の高さ
（トーナメント表のことをヒープ木とよぶこともある）
・頂上から１つずつレベルを下げていくと、チームの数は倍倍
で増えていく
・頂つまり、一番下の数値のところにいくまでに log2n +1 回か
かる
・データ更新の計算時間は O(log n )
挿入と削除
・ヒープに新しく要素を追加するときは、ヒープ木の一番右側に
追加する
・ヒープから要素を削除するときは、削除する要素にヒープ木
の一番右側の要素を代入してヒープ木を更新したあと、右端
の要素を削除し、ヒープ木の更新をする
・どちらも計算時間は O(log n )
ヒープを実現するには
・さて、ヒープを実際にメモリの中に構築するにはどうすればい
いでしょうか？
 リストのように、セルとポインタを作ればいいかな？
・ヒープ木の隣接関係がつかめるよう、上と左右の下のセルに
ポインタを張る
・実は配列で、ポインタなしで作れる
配列でヒープ構造を
・ヒープ木を上から１レベルずつ、各レベルを左から右にたどり、
対戦カードに順番に 0 から番号をつける
 一番下のレベルが n のとき、最後は 2n-2 になる
配列の大きさは 2n-1
・自分の上・左下・右下が、計算で出せる
0
2
1
3
4
5
7 8 9 10 11 12
6
隣のセルの添え字
・ヒープの対戦カード（以後セルといいます）i の
上（親という）

(i-1)/2 （切捨て）
左下（左の子という） 
i*2+1
右下（右の子という） 
i*2+2
・ i がn-1 より大きいなら、子はいない
0
2
1
3
4
5
7 8 9 10 11 12
6
ヒープの構造体
・ヒープの構造体は、配列と、配列の大きさと、ヒープの大きさ
・ i 番目のセルの値を a に変更するルーチン
typedef struct {
void AHEAP_chg ( AHEAP *H, int i, int a ){
int *h;
// array for values
int j;
int end; // size of array
H->h[i] = a;
int num; // current size of heap
while ( i>0 ){
} AHEAP;
j = i - 1 + (i%2)*2; // j := sibling of i
if ( H->h[j] < a ) a = H->h[j];
i = (i-1) / 2; // i := parent of i
if ( H->h[i] == a ) break; // no need to update
H->h[i] = a;
}
}
挿入と削除
・新しいセルを挿入する際には、num を１つ大きくして、最後にセ
ルの a に変更
void AHEAP_ins ( AHEAP *H, int a ){
H->num++;
H->h[H->num*2-3] = H->h[(H->num*2-2)/2]
AHEAP_chg ( H, H->num*2-2, a);
}
void AHEAP_del ( AHEAP *H, int i ){
AHEAP_chg ( H, i, H->h[H->num*2-2]);
AHEAP_chg ( H, (H->num*2-2)/2,
H->h[H->num*2-3]);
H->num--;
}
0
2
1
3
4
5
7 8 9 10 11 12
6
最小値を持つセルの検索
・一番上（セル i ）からスタートして、最小値を持つ子どもの方に
降りていく
int AHEAP_findmin ( AHEAP *H, int i ){
if ( H->num <= 0 ) return (-1);
while ( i < H->num-1 ){
if ( H->h[i*2+1] == H->h[i] ) i = i*2+1;
else i = i*2+2;
}
return ( i );
}
0
2
1
3
4
5
7 8 9 10 11 12
6
閾値以下の値を全て見つける
・一番左にある、閾値以下の値を持つものを見つける
int AHEAP_findlow_leftmost ( AHEAP *H, int a , int i ){
if ( H->num <= 0 ) return (-1);
if ( H->h[0] > a ) return (-1);
while ( i < H->num-1 ){
if ( H->h[i*2+1] <= a ) i = i*2+1;
else i = i*2+2;
}
return ( i );
}
・（セル i ）の直右にある、閾値以下の値を持つものを見つける
int AHEAP_findlow_nxt ( AHEAP *H, int i ){
for ( ; i>0 ; i=(i-1)/2 ){
if ( i%2 == 1 && H->h[i+1] <= a )
return ( AHEAP_findlow_leftmost ( H, a, i+1 ); 1
}
3
4
return ( -1 );
}
0
2
5
7 8 9 10 11 12
6
ヒープの利用例
・数列をソートする（小さい順に並べ替える）
－数列の数値を全てヒープに挿入する
－小さい順に１つずつ取り出す
・グラフ構造からクラスタリングをする
0
2
1
3
4
5
7 8 9 10 11 12
6
ヒープの利用例：ハフマン木の構築
・（単語などが） n 個あり、それぞれ頻度がある
・頻度が最小なものと、その次のものを列の数値を全てヒープに
挿入する
－頻度が小さい順に２つ取り出す
－両者を合併し、１つになるまで同様に繰り返す
・右の子、左の子に01を割当ててコード化すると、各文字を01の
コードに割当てられる。
35
最適な圧縮形式になっている
15
20
11
7
A9 B6 C5 D4 E3 F8
練習問題：ヒープ
・以下の数値でヒープを作り、そこに 7, 2, 13 を順に挿入せよ
4, 6, 8, 9, 11, 15, 17
メモリ効率を上げる
・このヒープは、値を n 個覚えるのに、メモリを 2n-1 使う
 ２倍程度使っている
・もう少し効率良くならないか
 中間セルにも値が蓄えられているようにすればいい
0
2
1
3
4
5
7 8 9 10 11 12
6
教科書にあるヒープ
・普通、教科書に出てくるヒープは、このように全てのセルに固
有の値を蓄えるタイプ
・そして、「親は子どもより値が小さい」という性質を満たすよう
に、データを更新する
 頂上の頂点が最小値になる
0
2
1
3
4
5
7 8 9 10 11 12
6
ヒープの更新
－値の変更は、小さくなったら、親と入れ替え、大きくなったら、
子と入れ替え、を再帰的に
－挿入は、一番右下にセルを追加
－削除は、一番右下をコピーし、値を更新し、サイズを１つ減少
・だいたい、先ほどのヒープと同じやり方でできる
0
2
7
9
8
3
10 11 9 10 4 4
7
数値の変更のコード
・ヒープの構造体は、前回と同じ
・ i 番目のセルの値を a に変更するルーチン
void HEAP_chg ( AHEAP *H, int i, int a ){
int aa = H->h[i];
H->h[i] = a;
if ( aa > a ) HEAP_chg_up ( H, i );
if ( aa < a ) HEAP_chg_down ( H, i );
}
typedef struct {
int *h;
// array for values
int end; // size of array
int num; // current size of heap
} HEAP;
ヒープの更新 (上り)
・ヒープを更新する際には、値を小さくしたときは上に、値を大き
くしたときは下に、親子の入れ替えをしながら進む
void HEAP_up ( AHEAP *H, int i ){
int a;
while ( i>0 ){
if ( H->h[(i-1)/2]<= H->h[i] ) break;
a = H->h[(i-1)/2];
H->h[(i-1)/2] = H->h[i];
H->h[i] = a;
i = (i-1)/2
}
}
typedef struct {
int *h;
// array for values
int end; // size of array
int num; // current size of heap
} HEAP;
・セルの値を変更すると、場所が入れ替わるので、各値の場所
を覚えておきたいときには不向き
ヒープの更新 (下り)
・値を大きくしたときは、子どもより親のほうが小さくなるかもしれない
・その際には、子どもと親を入れ替えるのだが、その際に、値の小さいほう
の子ども、と入れ替える必要がある
void HEAP_down ( AHEAP *H, int i ){
typedef struct {
int ii, a;
while ( i<H->num/2 ){
int *h;
// array for values
ii = i*2+1;
int end; // size of array
if (i*2+1 < H->num && H->h[ii]>H->h[ii+1]) ii = ii+1;
int num; // current size of heap
if ( H->h[ii] >= H->h[i] ) break;
} HEAP;
a = H->h[ii];
H->h[ii] = H->h[i];
H->h[i] = a;
i = ii;
}
}
閾値以下の値を全て見つける
・再帰呼び出しで、比較的簡単に
int HEAP_findlow ( AHEAP *H, int a , int i ){
if ( i>=H->num ) return;
if ( H->h[i] > a ) return;
printf (“%d\n”, H->h[i]
HEAP_findlow ( H, a, i*2+1)
HEAP_findlow ( H, a, i*2+2)
}
0
2
7
9
8
3
10 11 9 10 4 4
7
練習問題：ヒープ (2)
・以下の数値で、教科書ヒープを作り、そこに 7, 2, 13 を順に挿
入せよ
4, 6, 8, 9, 11, 15, 17
～余談～：実際のヒープの速度
・ヒープを検索／更新する時間は O(log n)
・しかし、実際にプログラミングしてみると、100万要素くらいあっ
ても、普通にメモリアクセスするのに比べて 4-5倍程度しか時
間がかからない（log2 100万 ≒ 20 ）
・なぜだろうか
～余談～：実際のヒープの速度 (2)
・ヒープを検索／更新するときは、葉から根までを更新する
・ 1回アクセスすると、アクセスした部分はキャッシュに入り、次
回短時間でアクセスできる
・何回も繰り返すと、根に近い部分は全部キャッシュに入ってし
まう。時間がかかるのは、下の部分だけ
・キャッシュに入らないのが、4-5レベル
ということ
このあたりで木に関する用語の定義を
・（グラフ理論では）頂点（あるいは点、ノード）、が枝で結ばれた構造をグ
ラフという（枝は、2つの頂点を結ぶ）
・グラフの中で、わっかになった構造を持たないものを木という
・頂上の頂点（根という）が指定されている木は根付き木という（アルゴリズ
ムやプログラミングでは、これを木という）
・根付き木の頂点 x に対して、
－ x に隣接し、より根に近い頂点を（上の頂点）を親という
－それ以外の隣接する頂点を子という
－頂点 x と根を結ぶ線上にある頂点を x の先祖という
－ x が先祖である頂点を x の子孫という
－ x の子孫からなる木を x の部分木という
・子どもを持たない頂点を葉という
・子どもを持つ頂点を内点という
・根から最も遠い葉までの距離を木の高さ（深さ）という
・子どもの数が2以下である木を2分木という
・子どもの数が0か2である木を完全2分木という
（ヒープは完全2分木）
任意の値を見つけたい
・ヒープはシンプルで良いのだが、やはり、任意の値を短時間
で見つけられるようにしたい
・ヒープのように、トーナメント表のような構造を使うのはいい
が、挿入の位置が固定されているので、順番を保持すること
ができない（削除もそう）
・順番を保持できるようにする
ためには、任意の場所に挿入
できないといけない
0
2
1
3
4
5
7 8 9 10 11 12
6
順番がそろっていると
・数値が順番どおりに入っていると、２分探索を、頂上から下
にたどることで実現できる
・各ノードには、その子孫の最大の値を書くようにする
 見つけたい数値がどちらにあるか、子どもを見ればわかる
・では、順番を守ったまま、
挿入＆削除をすることにしよう
・木の形はゆがんでもいいことにしよう
・前の数値があるノード（葉という）
の下に子を２つ作り、挿入
・葉を消して隣の葉の数値を
親にコピー
ゆがみをゆるすと
・検索の時間は、見つける葉までの深さ、ない場合は、隣合う
葉の深いほうの葉の深さに比例
・木の形がきれい（バランスが取れている）なうちは、検索が速
いが、やたら深いところが出てくると、遅くなる
 同じところに挿入が続いた場合
・検索の高速性を実現する
ためには、何か工夫をしないと
ゆがみを矯正
・検索の時間、最適なものは O(log n )
・では、定数 c に対して、c log n を超えないように調整しよう
・木に深いところがあるならば、必ずどこかに、浅い場所がある
 浅い場所を深くして、深い場所を浅くできればいい
その際、順番を変えないように
・浅いところを下げ、
深いところを上げ、
親を付け替えて、
バランスをとろう
バランスをとる
・左右の子どもの部分木の高さが2以上異なる頂点が親子で続い
ているところを、構造を変えて高さをそろえる
（このような局所的な変更をオレンジ色の頂点に対するローテート
という）
・ローテートすると高さがそろう（高さの差が２減る）
2以上
木の高さは抑えられるか？
・「左右の子どもの部分木の高さが2以上異なる頂点が親子で続
いているところ」がないようにする（ある限りローテートする）
・木の高さ k に関して、何かいえるか？？？
－深さ k-1 の頂点（葉）が 1つある
（根、あるいは根の子どもで分岐）
－深さ k-2 の頂点が２つある
（深さ 2,3 の頂点で分岐）
－深さ k-h の頂点が 2h-1 個ある
（深さ2h,2h+1の頂点で分岐）
 木の頂点数は、少なくとも 2k/3
・葉の数が n なら、高さは 3log2 n ＝ O(log n)
このようにバランスの取れた木構造を、バランス木とよぶ
検索の時間
・「ある数値があるか」を調べるには木を根から葉までたどる必
要がある
・計算時間は、葉までの距離に比例。最悪でも木の高さ
・葉の数が n なら、高さは 3log2 n ＝ O(log n)
つまり、検索の時間は O(log n)
このようにバランスの取れた木構造を、バランス木とよぶ
ローテートの影響
・頂点 x をローテートをした結果、ローテートする必要がなかった
のに、ローテートする必要が出てくる頂点があるか？
－ x の子孫は大丈夫。部分木の高さに変化がない
－ x の子孫でも先祖でもない頂点もそう
－ x の先祖には影響がある
・つまり、条件を満たした木の構造に局所的な変化があったら、
条件を守るようにするためには、その先祖に対してローテート
しなければいけない
頂点の挿入と削除
・木から頂点を削除／木に頂点を挿入すると、一部の頂点がロー
テートの条件を満たさなくなる
 そのような頂点は、挿入／削除した場所の先祖
・高さは高々１しか変わらないので、一回ローテートすれば条件を
満たすようになる
・先祖に対して、山登り的にローテートを、不要になるまですれば
よい（一回不要になったら、それより上は必ず不要である）
・木の高さは O(log n)、ローテートは
定数時間でできるので、挿入／削除
してバランスをとる作業は
O(log n) でできる
他の基準によるローテート
・２つ下のレベルの部分木の大きさが、元の部分木の大きさの
半分以上であるときに、ローテートする
・ローテートすると大きさが（１以上）減る
 ２つ下がると大きさが半分以下になるまでローテートする
20
30
50%
30
20
木の高さ
・２つ下がると大きさが半分以下、なので、 2log2 n 回以上下が
れない
 葉の数が n なら、高さは 4log2 n ＝ O(log n)
20
30
50%
頂点の挿入と削除
・このローテートは、先祖に対しても影響しない
（ローテートしても子孫数に変化はない）
・挿入／削除した頂点の先祖に対して、山登り的にローテートをする
ただし、不要になるまですればよい、というわけではない
・木の高さは O(log n)、ローテートは
定数時間でできるので、挿入／削除
してバランスをとる作業は
O(log n) でできる
２分木の構造体
・ヒープのようにポインタなしで実現するのは難しいので、リスト
のように隣を指すポインタを用意しよう
・バランスを取るため、高さやサイズのデータも保持しよう
・リストのように、配列で実現しても良い
typedef struct {
BTREE *p; // -> parent
BTREE *l; // -> left child
BTREE *r; // -> rigth child
int height; // height of subtree
int height; // height of subtree
int value; // (max) value
} BTREE;
2分木の利用例
・辞書のデータ、IDの管理
・文書データのキーワード検索
練習問題：２分木
・以下の2分木をローテートせよ（高さが2以上違う場合、１つ
の子どもが子孫に葉を50%より真に大きい割合持つ場合）
たくさんの子ども
・２分木の内点は、必ず子どもを2人持っていた
・２つである意味は？
－更新の速度が最速
－検索と更新が同じ速さ
－子どもの処理が簡単
・子供２人以上をあり、にするとどうなるだろう
・ 2-3木という、子どもの数が2か3である木がある
－特徴は、どの葉も深さが同じということ
－ただし、子どもに関する処理が面倒
（子どもが2人の場合、3人の場合で、
それぞれ最小がどこか、とか）
・もっと子どもを増やしたら？
B木
・子どもの数が B 以下の木データ構造をB木という
・わざわざ子どもを増やすのは、それなりの動機がある
・ハードディスクやテープのような、アクセスに時間がかかるが、
そこからある程度まとまったデータを取るのには時間がかから
ない、というような記憶装置を使う場合、計算時間のボトルネッ
クは、検索／更新する際に、何個のノードを見たか、という点に
なる
・それならば、各ノードの子どもの数を
増やせばよい
B木の更新
・ B木を、「全てのノードがB個の子どもを持つ」とすると、効率が
良いが、このようにきっちり条件を守るのは大変
・しかし、どのノードも子どもが2-3人、となると、それはそれで効
率が悪い
 B/2 以上 B 以下にする
 親子、あるいは兄弟で、子どもの数が B/2 以下であるようなも
のがあれば、それらを合併して１つにする
 ローテートすれば、木の高さが O(logB/2 n) になる
まとめ
・
・
・
・
２分探索：半分に分割して、log n 回で見つける
ヒープ：トーナメント表の構造を保持して、最小値を更新
２分木：木構造のバランスとって、高さを抑える
B木：アクセスするノード数を最小化

Download Report