二分探索木のまとめ2 - 某大学の講義録

二分探索木の性能

今、二分探索木にはN個の値が挿入されているとします。

平均時

二分探索木の構造が正しく二分出来ている時、一度の値の比較によってその後探索するべき部分木が左の木か右の木のどちらかに決まるため、残りの未探索の値の数を ${\frac{1}{2}}$ にすることができます。
この未探索の数が1になった時、最後の比較を行い値が一致したら探索成功、失敗したら探索失敗です。つまり、 $N$ → ${\frac{N}{2}}$ → ${\frac{N}{4}}$ → $\dots$ →1のように数は減っていきます。
ここで、何回 ${\frac{1}{2}}$ にする動作を行ったかが比較回数であり、この値は逆に1から2を累乗していき、 $N$ を超える値になった時の2をかけた数と同値であるから、この2をかけた回数をsとすれば
$2^s$ = $N$ となり、両辺で底2の対数をとって
$s$ = $log_{2} N$ = ${\frac{logN}{log2}}$ (底の変換公式)
計算量において、定数は無視することができるから結局 $O$ ( $logN$ )になります。
この時、探索の成功、不成功どちらも計算量 $O$ ( $logN$ )であり、挿入は不成功探索+挿入という操作であるため、同様に計算量は $O$ ( $logN$ )です。

最悪時

木構造が全く二分出来ていない、つまり以下のような構造の時、二分探索木の性能は最悪になります。
f:id:rei_624:20181109234429p:plain
N個の値が上記のような構造で挿入されている時、一番根から遠い値の探索にはN個の値全てと比較する必要があります。計算量は一番悪い場合を用いるので、この構造における計算量は $O$ ( $N$ )となります。

現状の二分探索木を実装するコードでは上記のような構造を回避することはできません。それを実現するのがランダム木やスプレイ木、最悪パターンを回避しつつさらに性能を伸ばす赤黒木などです。(後々やる気と時間があれば書きます。)

木の回転

今までの二分探索木：常に葉に挿入していた。
しかし、基本的に二分探索木に挿入した値は新しいものほど使用する確率が高いため、新しいものほど根の近くに挿入するべきです。
そこで、ある値の挿入時に根に動かす動作に必要となるものが木の回転です。

gifで回転の動きを見てみましょう。
以下の例は右回転です。左回転は反対側で行うだけなのでgifは省略します。
f:id:rei_624:20181120000554g:plain

子ノードと親ノードの関係が入れ替わっていることがわかります。この時、Lの節点で回転させると言います。(ここ重要です。)つまり、Lの周りで右回転ということになります。
上のgifではノードの持つ値毎に比較しましたが、二分探索木の定義からあるノードに対して左の部分木は常にそのノード以下、右の部分木は常にそのノード以上が約束されているので、回転により値の順番が壊れる心配はありません。

実装

回転はgifの動きをそのままコードに落とし込むことで簡単に実現できます。
ただし、右回転と左回転ではノードを付ける位置が左右真逆なので別々の関数として実装します。

//右回転
link rotationR(link h){    //hは見ているノード
    link x = h->l;    //左のノードを指すリンクxを作成
    h->l = x->r;      //hの左がxの右を指すようにして
    x->r = h;         //xの右がhを指すようにする
    return x;         //新たに根となったxを返す
}

//左回転
link rotationL(link h){    //hは見ているノード
    link x = h->r;    //右のノードを指すリンクxを作成
    h->r = x->l;      //hの右がxの左を指すようにして
    x->l = h;         //xの左がhを指すようにする
    return x;         //新たに根となったxを返す
}

//呼び出し方
例1. h = rotationR(h);
例2. h->l = rotationL(h->l);

回転関数が完成しました。

嘘です。このままではNの値がおかしくなります。(動かしてみるとわかります。)
なのでいい感じに修正しておきましょう。(修正方法は一つではないのでどんな方法でもいいです。)
今回は以下のようなfixNという関数を使います。この関数はすべてのノードの持つNは必ず"左のノードのN+右のノードのN+1(自分自身)"になることを利用して、再帰的に葉ノードからNを決めていく関数です。

void fixN(link h){
    if(h==z) return;
    fixN(h->l);
    fixN(h->r);
    h->N = h->l->N + h->r->N + 1;
}

//呼び出し方
fixN(h)   //hは見ているノード

このほかにも回転関数内で調整する方法等もあるので、一度自分で実装してみるといいと思います。

根への挿入

さて、回転によって子ノードと親ノードの関係を入れ替えることができるようになったので、次は挿入したノードが根ノードになるまで回転させることを考えます。今、回転によって変わるノードは以下のようになっています。

右回転：左の子ノードを親ノードに持ってきて、親ノードは右の子ノードになる。
左回転：右の子ノードを親ノードに持ってきて、親ノードは左の子ノードになる。

つまり、根に挿入するためには、

挿入したいノードを左の子ノードとして挿入する場合→挿入した後に右回転
挿入したいノードを右の子ノードとして挿入する場合→挿入した後に左回転

を繰り返していけばいいことがわかります。
さて、まとめ1で実装した挿入関数を見てみましょう。

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;
}

再帰呼び出しをしている部分に注目すると、見ているノードhに対してh->lまたはh->rで呼び出していることがわかります。つまり、この時点で左に挿入(または再帰)しているか右に挿入(または再帰)しているかが決定できるため、あとは同じif文の中に回転を追記すればいいだけとなります。

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);
        h = rotationR(h);  //左に挿入したのでhを親ノードとして右回転
    }else{
        h->r = insertNode(h->r, item);
        h = rotationL(h);  //右に挿入したのでhを親ノードとして左回転
    }
    fixN(h) //Nの値を修正しておく
    return h;
}

これでinsertNodeを根ノードに挿入する関数にすることができました。

木の表示

配布されたコードを簡単に説明しておきます。

void STshow(link h, int l){
    int i=0;
    if(h != NULL){
        STshow(h->r, l+1);
        for(i=0; i<l; i++) printf("\t");
        printf("(%d,%d)\n",key(h->item), h->N);
        STshow(h->l, l+1);
    }
}

void STshowAll(void){
    STshow(head, 0);
}

まず、hがNULLでない間(hがNULLとなるのはダミー節点zの子ノードを見ようとした場合のみです。)は右の子ノードで再帰呼び出しを行います。このとき、引数のlで再帰呼び出しの回数、つまり見ているノードの高さを情報として持っておきます。
そして、ダミー節点にぶつかった時にノードの高さ分だけ\t(それなりの個数の空白を出力する)をループで出力し、その後に自分の持っているキーの値とNの値を出力して、今度は左の子ノードで再帰呼び出しをします。ノードを出力したら改行することで各行の中にはノードが高々1個存在するようにできます。
これによって高さと位置(下から上に見ることで整列できている)のあった木構造全体の形を出力できるようになります。(ただし向きは左に90°回転しています。)

また、この走査は以前まとめ1の整列で述べた中央順走査のちょうど逆向きの動作であることがわかります。