アルゴリBにおける二分探索木のまとめ1

二分探索木

使う木構造：二分木
それぞれの内部節点(葉ノードでないノード)がキーを持っている二分木で以下の二つの性質を持つ。

あるノードの左部分木に属するノードの持つキーは全てそのノード以下のキーを持つ。
あるノードの右部分木に属するノードの持つキーは全てそのノード以上のキーを持つ。

二分探索木の例
f:id:rei_624:20181019232442p:plain

各ノードの持つキー(ここではアルファベット)に注目してみると、きちんと上記の性質を満たしていることがわかります。

さて、ここで四角で囲まれたzをダミー節点zとし、これを外部節点(葉ノード)とします。ダミー節点zは以下のような構造体を指すリンク(構造体へのポインタ)であるとします。

Item NULLitem = {-1, "NULL"};
link z;
z->item = NULLitem; z->l = 0; z->r = 0; z->N = 0;

f:id:rei_624:20181022002556p:plain
(↑ダミー節点zのイメージ)
ここでダミー節点zの中身はキーが-1、情報が"NULL"です。また、ダミー節点zの右にも左にも子はいません(外部節点の定義)。逆に、ダミー節点z以外の全てのノードはあるノードかダミー節点zを指すこととします。そのため、ダミー節点z以外の全てのノードは内部節点ということになります。(あくまでこの講義における二分探索木で、の話であることに注意してください。)

また、ここから先の画像では簡易のために矢印の先を省略することがあります。

[重要]深さと高さ

まとめ0での木構造では書かなかった深さと高さですが、この講義における高さはおそらく一般的な定義とは少し違うと思います。これは、(おそらく)ダミー節点を外部節点として作っているせいです。
まずは深さの定義からです。
・あるノードから根ノードまでに通るブランチの本数
この定義から根ノードの深さは0です。また上記の二分木構造ではそれぞれの深さに対応したノードは
深さ0：L
深さ1：G, P
深さ2：C, I, M, X
深さ3：A, F, H, N, R
となります。また深さのことをレベルとも言います。

次に高さの定義です。一般的には以下のようなものが多いです。
・根ノードから一番遠いノード(＝外部節点)までの深さ
今、ダミー節点を外部節点(葉ノード)としてるためこの定義に従うと上記の図の二分探索木の高さは4と言いたくなります。しかし、この講義では上記の二分探索木の高さは3です。

(直接聞きに行ったところ、ダミー節点はあくまで木構造実現のために仮置きしているだけであって、実在はしてないものとして考える。とのことです。)
ダミー節点はノードではないと思えば理解できなくはないですね・・・

理解しやすいように定義しなおすなら以下のようになるかと思います。
・根ノードから一番遠い内部節点までの深さ

内部道長と外部道長

内部道長：ある木構造におけるすべての内部節点のレベルの総和
外部道長：ある木構造におけるすべての外部節点のレベルの総和
ちなみにここでの外部節点はダミー節点として考えるそうです。

ダミー節点は外部節点であるけどノードではない。みたいなスタンスなのでしょうか・・・

木の高さを求める関数や、内部道長・外部道長を求める関数は課題として出ていたので割愛します。

二分探索木の実装

初期化(木の作成)

講義スライドに従ってある二分探索木の根を指すリンクをheadとします。(headはグローバル変数とする。)一番最初はダミー節点を含めノードが一つもないため、キーを木に挿入していく前にとりあえずheadがダミー節点を指すようにします。(initはinitialize:初期化の略です)

void BSTinit(){
    head = z;
}

さて、これで木を作成していくことができます。木に対して行いたい操作は

・新しいキーの挿入
・あるキーの探索
・木構造の回転
・木全体の表示

などたくさんあります。なのでこの記事では一番の基本となる挿入と探索について書いていき、残りはまとめ2で書きたいと思います。

挿入

二分探索木の性質を思い出してみると、あるノードから見て左は小さいキーの集まり、右は大きいキーの集まりとなっていました。では新しいキーを挿入する場合はどう判別すればいいでしょう？

この実装は簡単で、根のキーから順に比較していき、そのノードのキーより小さい場合は次に左のノードと、大きい場合は次に右のノードと比較していけばよいだけです。
そして、訪れたノードがダミー節点であった時、その位置が自然と挿入すべき位置となります。
実際の動き方をgifで見てみたいと思います。(見ているノードと書いていますが、厳密にいえばダミー節点以外は見ているノードのキーです。)
f:id:rei_624:20181029145806g:plain

これをC言語で実装していきます。(今回は再帰関数を用いて実装します。)実装したい内容は

キー同士の比較
ダミー節点を新しいノードへ変える
比較結果に応じた再帰
節点を増やしたことによるNの値の調整

の4つです。ここから先では、新しく挿入したい構造体をitem、今見ているノードをhとします。(本当であれば一文字の変数は使うべきではないのですが、ここであえて変えると混乱を生むためスライドに沿っていきます。)

キー同士の比較

今、まとめ0で定義したようにノードの持つキーはint型なので、キー同士の比較は通常の比較演算子を用いればいいことがわかります。(ノードの持つ"情報"については使わないので忘れて大丈夫です。)

int v = item.key;
if(v < h->item.key){
    //vのキーの方が小さい時の処理
}else{
    //vのキーの方が大きい時の処理
}

講義で用いているless(A, B)はどちらが小さいほうなのかわかりづらいという欠点があると個人的に思うので、使いません。逆にkey(A)は見やすくなると感じる場合アリだと思います。その場合は以下のようになります。

#define key(A) (A.key) //どこかに書いておく
//以下は挿入する関数内に書く
int v = key(item);
if(v < key(h->item)){
    //vのキーの方が小さい時の処理
}else{
    //vのキーの方が大きい時の処理
}

ダミー節点を新しいノードへ変える

上記におけるvが小さい(大きい)時の処理の部分を考える前に、新しい節点はどうやって挿入するのかを実装していきます。(こちらの方が再帰を理解しやすくなると思います。）
今、新しく追加するノードはダミー節点の位置に挿入するので、必然的に今見ているノードhがダミー節点ということになります。つまり、

if(h==z){ 　　　　　　　　　　　　  　　　         　//今見ているノードがダミー節点なら
    link x; 　　　　　　　　　　　　　　　　         //新しい節点をxとして
    x->item = item; x->r = z; x->l = z; x->N = 1; //xはitemを持ち、ダミー節点を指して
    return x;                                     //xを返す。
}

さて、まとめ0でも少し書きましたが、上記のように毎回xをおき、xがそれぞれを指すように書くのは悪いコードです。これを関数でできるようにしましょう。
新しいノードに必要な引数は

そのノードの持つitem
左に接続するノードl
右に接続するノードr
そのノードを根とした部分木内の内部節点の数N

の4つなので、関数は

link NEW(Item item, link l, link r, int N){
    link x;
    x->item = item; x->l = l; x->r = r; x->N = N;
    return x;
}

//使用例(ダミー節点)
z = NEW(NULLitem, 0, 0, 0);

と書くことができます。これを先のコードにも適用すれば

if(h==z) return NEW(item, z, z, 1);

のように1行で書くことができます。
さて、ここでNEWをreturnしているということは、再帰関数の戻り値はlinkにする必要があります。また、再帰をしていくにあたって今見ているノードhと挿入したいitemは常に何らかの形で関数内に持っている必要があります。なので、この二つは引数として渡すことにしましょう。

つまり、挿入する関数は

link insertNode(link h, Item item){
//処理
}

という形になっていることがわかります。今まで作ってきた部分的な内容を盛り込めば、

link insertNode(link h, Item item){
    if(h==z) return NEW(item, z, z, 1);
    int v = key(item);
    if(v < key(h->item)){
        //vのキーの方が小さい時の処理
    }else{
        //vのキーの方が大きい時の処理
    }
}

という形になります。では、残っているif文の比較結果に応じた再帰とNの値の調整を書いていきましょう。

比較結果に応じた再帰

既に関数の戻り値、引数が判明しているので、二分探索木の定義に従って実装していきましょう。先に述べた通り、

"そのノードのキーより小さい場合は次に左のノードと、大きい場合は次に右のノードと比較していけばよい"

ので、これを素直に実装すれば

link insertNode(link h, Item item){
    if(h==z) return NEW(item, z, z, 1);
    int v = key(item);
    if(v < key(h->item)){
        h->l = insertNode(h->l, item); //左のノードを根とした部分木で再帰
    }else{
        h->r = insertNode(h->r, item); //右のノードを根とした部分木で再帰
    }
}

という関数ができました。

節点を増やしたことによるNの値の調整

今のままでは新しいノードを挿入してもあるノードの持つNの数は変更されません。(そもそも変更するような式を書いていないため。)ここで、
・挿入するノードは一回につき一つであること。
・挿入するまでに通った(見てきた)ノードは全て新しいノードを子孫に持つ
事に注目すると、見ているノードのNを一つ増やすようにすればいいことがわかります。

link insertNode(link h, Item item){
    if(h==z) return NEW(item, z, z, 1);
    int v = key(item);
    if(v < key(h->item)){
        h->l = insertNode(h->l, item);
    }else{
        h->r = insertNode(h->r, item);
    }
    ++(h->N);
}

さて、これで挿入の関数は完成でしょうか。

答えはいいえです。

再帰関数では再帰場所(つまり同じ関数名の書かれた行)で呼び出した関数の処理が終わった後、そのまま残りの処理を行います。しかし、今のままではreturn文が(hがダミー節点であった場合の新しいノードの作成を除いて)書かれていないため、何も返さないまま終了してしまいます。(厳密な話をすると未定義になっているだけで何も返さないわけではないのですが、その辺の話は僕自身よくわかっていないのでここでは割愛します。)
再帰関数で実装した時の挿入関数の動き方をgifで見たいと思います。
f:id:rei_624:20181029223901g:plain

今、関数を呼び出した場所では何らかのlinkに代入する形で呼び出しているため、「よくわからないもの」が代入されるのは危険です。なので、呼び出し元に適切な値を返す必要があります。ここで、再帰場所における左辺のlinkは、右辺の関数の引数にも同じものを渡していることから次に見るノードです。であれば、その再帰場所で呼び出されたinsertNode関数がreturn文で返すべき値は左辺と同じlink、つまり(再帰場所では次に見るノードだった)今見ているノード、となります。

link insertNode(link h, Item item){
    if(h==z) return NEW(item, z, z, 1);
    int v = key(item);
    if(v < key(h->item){
        h->l = insertNode(h->l, item);
    }else{
        h->r = insertNode(h->r, item);
    }
    ++(h->N);
    return h;
}

また、実際に挿入する場合は一番最初の再帰でない関数呼び出しが必要であることにも注意してください。main関数に直接書くか、以下のような呼び出し用の関数を作れば良いです。

void insertNodeBase(Item item){
    head = insertNode(head, item);
}

これで挿入する関数が定義できました。再帰関数は再帰関数がわかるとわかる。ともいわれるように理解しづらいところがあるかもしれません。頑張ってください。

探索

次にある任意のキーを探索する関数を作ります。とはいえ、挿入と比べてこちらは今ある二分探索木のキーと比較していくだけなのでわかりづらいところは少ないように思います。ここで、探索関数の動作を以下のように規定します。

探索関数ではある任意のキーに対して、そのキーが二分探索木の中に存在した場合はそのノードの持つitemを、二分探索木の中に存在しなかった場合はそのNULLitemを返すものとする。

先の挿入関数で、あるキーの挿入すべき位置の求め方を書きましたが、探索も基本的には同じ動作です。ただ一つ違う点は、挿入関数では見ているノードがダミー節点になるまで再帰を繰り返しましたが、探索関数では見ているノードの持つキーが一致したタイミングか、一致しないままダミー節点になったタイミングで探索を終えるという点です。

以下が探索関数の中身です。(引数のvは探索したいキーの値です。)

Item searchNode(link h, int v){
    if(h==z) return NULLitem;
    if(v==key(h->item)) return h->item;
    if(v < key(h->item)){
        return searchNode(h->l, v);
    }else{
        return searchNode(h->r, v);
    }
}

見ているノードがダミー節点の時(h==z)はNULLitemを返し、見ているノードのキーが探索したい値であった時(v==key(h->item))はhの持つitemを返し、それ以外の場合は探索したいキーが所属している(かもしれない)部分木で再度探索をします。

探索関数は挿入関数とは異なり、再帰がreturn文で行われています。これにより、再帰していった結果求めるキーがあった場合(つまりコードの3行目でitemを返した場合)でも、求めるキーがなかった場合(つまりコードの2行目でNULLitemを返した場合)でもその値を一番最初の呼び出し元まで返すことができます。イメージとしては以下のような図になります。
f:id:rei_624:20181028181106p:plain
探索関数も挿入関数と同様に呼び出し用の関数を用いる場合は以下のように定義するとよいでしょう。

Item searchNodeBase(int v){
    return searchNode(head, v);
}

成功探索と不成功探索

探索していった結果、探したいキーが見つかった場合を成功探索、見つからなかった場合(そもそも二分探索木の中に存在しなかった場合)を不成功探索と呼びます。

逆に、挿入関数では不成功になるまで探索を繰り返し、不成功になった場所で新しいノードを挿入していると考えることもできます。とはいえ、あらかじめ挿入するキーが二分探索木の中に存在しているかどうか判定していない場合は探索は成功するのに挿入してしまう可能性がある(つまり同じキーを持ったノードが二つ以上になる)ため、あえて挿入関数→探索関数の順に書きました。(それ以外にも挿入関数が理解できれば探索関数はすぐ理解できるという理由もありますが・・・)

整列

二分探索木はその木の性質上、常に整列された状態を維持しています。木構造を見た時に左から右に向かって値を見ていけば整列されているのです。以下に与えられた数値を二分探索木として作成した後、整列した値として出力する関数を書いておきます。

void sortKeys(link h){
    if(h==z) return;
    sortKeys(h->l);
    printf("%d ", key(h->item));
    sortKeys(h->r);
}

あるノードに対して、左の部分木に属しているキーを出力し終えたら自分の持つキーを出力し、右の部分木に属しているキーを出力することで整列された値として出力できます。このようにある部分木の根から見て左の部分木、根自身、右の部分木という順序で見ることを中央順走査といいます。(または中間順)

まとめ

外部節点としてダミー節点を用いる
この講義における木構造の高さは混乱を招きやすいため注意。
二分探索木の実装はそこまで難しくない。(今後と比較して)
挿入関数は再帰を用いて実装することができる。
探索関数も再帰を用いて実装することができる。
再帰は再帰がわかるとわかる。(らしい)

書くなら(後々の自分のためにも)なるべく優しくわかりやすく書こうとしていたら、だいぶ文字数が増えて長い記事になってしまったので次回以降はもう少し雑に、備忘録としての書き方で作ろうと思います・・・さすがに疲れてきたので・・・

某大学の講義録

個人用備忘録です。間違いの可能性あり。