コイン問題を動的計画法とC++で解く

AIZU_ONLINE_JUDGEのDPL_1_Aの問題を使用して、コイン問題を解きます。
コイン問題を以下に引用します。

問題

額面がc1, c2,..., cm　円の　m　種類のコインを使って、
n 円を支払うときの、コインの最小の枚数を求めて下さい。
各額面のコインは何度でも使用することができます。

入力

n m
C1C2・・・Cm

１行目に整数 n と整数 m が１つの空白区切りで１行に与えられます。
２行目に各コインの額面が１つの空白区切りで１行に与えられます。

出力

コインの最小枚数を1行に出力してください

制約

1 ≤ n ≤ 50,000
1 ≤ m ≤ 20
1 ≤ 額面 ≤ 10,000
額面はすべて異なり、必ず1を含む。

入力・出力例

15 6
1 2 7 8 12

2

解法

使用できるコインの額面が決まって入れば、額面が大きいものから引いていけば、
最小枚数を求めることができますが、今回の出力例でその方法を使用すると...

12 2 1
3

3となってしまい7,8を選んだ場合の最小値2となりません。
なので、貪欲法は使えません。

ここでは、以下のような配列の入れ物を定義し、
最小枚数を求めます

coin[m] : coin[i]をi番目のコインの額面とする配列
T[m][n + 1] : T[i][j]をi番目までのコインを使ってj円支払う時のコインの最小枚数とする2次元配列

コインの枚数をi,各iにおける支払う金額jを増やしていき、T[i][j]を更新していきます。
T[i][j]は、i番目のコインを使う場合と使わない場合の枚数を比べ、小さい方を選べばよいので、
次のような漸化式で求めることができます。

T[i][j] = min(T[i - 1][j],T[i][j - C[i]] + 1)

i枚目のコインを使わない場合は、ここまで計算したj円を払う最適解T[i - 1][j]となり、
使った場合は、現在の金額jからC[i]を引いた金額を払う最適解に1枚足した値になります。

配列の具体例

例題のように、支払う金額を15とし、コインの額面を1 2 7 8 12として
coin[m]とT[m][n + 1]の中身を見てみましょう

coin

1
2
7
8
12

T

0	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8
0	1	1	2	2	3	3	1	2	2	3	3	4	4	2	3
0	1	1	2	2	3	3	1	1	2	2	3	3	4	2	2
0	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2

例として、3枚目のコイン(額面8indexは０から)までのコインを使って15円を払う最適解は、
min(T[2][15],T[3][15-8] + 1)より2枚になります。
これは、先に述べたように3枚目のコインまでを使って7円払う最適解に1足したものです。

先の表からわかるように、コインの額面ごとに最適枚数を記録しておく必要はないので、
j円を支払うときのコインの最小枚数は1次元配列の要素T[j]として、次のように求めることができます。

T[j] = min[T[j],T[j - C[i]] + 1)

以上を踏まえて、c++を言語としてプログラムをみていきましょう

#include <iostream>
#include <algorithm>

using namespace std;

#define M_MAX 20
#define N_MAX 50000
#define INFTY 1 << 29

int main(){
    int n,m;
    int coin[21];
    int T[N_MAX + 1];
    
    cin >> n >> m;
    // コインに額面を代入する
    for(int i = 1;i <= m;++i){
        cin >> coin[i];
    }
    
    // 最大値で初期化
    for(int i = 0;i < N_MAX;++i){
        T[i] = INFTY;
    }
    T[0] = 0;
    for(int i = 1;i <= m;++i){
        for(int j = 0;j + coin[i] <= n;++j){
            T[j + coin[i]] = min(T[j + coin[i]],T[j] + 1);
        }
    }
    cout << T[n] << endl;
    return 0;
}

参考

べき乗の計算回数を少なくする繰り返し自乗法

べき乗の計算回数を少なくする方法をAIZU_ONLINE_JUDGEのNTL_1_B:Powerを用いて求めたいと思います。

問題

2つの整数m,nについて、m^nを1000000007で割った余りを求めてください。

単純に計算すると、時間がオーバーしてしまうので、計算方法を工夫する必要があります。
計算方法は

$x^n = (x^2)^\frac{n}{2}$

であることを利用します。

べき乗を計算する関数をpowとして、以下のように再帰関数として定義することで
計算回数を減らします。

pow(x,n) = 1(nが0の時)
pow(x,n) = $pow(x^2,n ÷ 2)$(nが偶数の時)
pow(x,n) = $pow(x^2,n ÷ 2) × x$(nが奇数の時)

例として、この関数を$2^{11}$でトレースしてみます。

$2^{11} = (2 × 2)^5 × 2$(nが奇数のケース)

$4^5 = (4 × 4)^2 × 4$(nが奇数のケース)

$16^2 = (16 * 16)^1$(nが偶数のケース)

このように計算回数を3回に減らすことができました。

Order記法

繰り返し自乗法は、再帰関数の引数が半分になっていくので、
O(logn)のアルゴリズムになります。

以上を踏まえての全体のプログラムです。

#include <iostream>
#include <cmath>

using namespace std;

long pow(long x,long n,long M){
    long res = 1;
    if(n > 0){
        res = pow(x,n / 2,M);
        if(n % 2 == 0){
            res = (res * res) % M;
        }else{
            res = (((res * res) % M) * x) % M;
        }
    }
    return res;
}

int main(){
    int m,n;
    cin >> m >> n;
    
    cout << pow(m,n,1000000007) << endl;
    return 0;
}

単一始点最短経路をダイクストラ法の隣接行列で求める

単一始点最短経路の問題をダイクストラ法と隣接行列を使って解きたいと思います。
問題はALDS1_12_Bを使います。

ダイクストラ法とは

ダイクストラ法は以下のように表される。

前提として、グラフG = (V,E)の頂点全体の集合をV、始点をs、
最短経路木に含まれる頂点の集合をSとします。

各計算のステップで、最短経路木の辺と頂点を選びSへ追加していきます。

また、各頂点iについて、S内の頂点のみを経由したsからiへの最短経路のコストをd[i]とします。

ダイクストラ法のロジック

1.初期化処理

最短経路木に含まれる頂点の集合をSを以下のように初期化します。

始点sに対して最短経路のコストを示すd[s] = 0を代入し、
始点s以外の頂点の全体集合Vに属する全ての頂点iに対してd[i] = 最大値
を代入します。

2.以下の処理をS = Vになるまで(始点sから各々の頂点の最短経路がもとまるまで)続けます。

2.1
V - Sの中から、d[u]が最小である頂点uを選択(最短経路と決定している頂点を除く)します。

2.2
頂点uをSに追加すると同時に、uに隣接しかつV - Sに属する全ての頂点vに対する
値を以下のように更新します。

if d[u] + w(u,v)(実際にかかる移動コスト) < d[v]
　　 d[v] = d[u] + w(u,v)

2.の各計算ステップ直後に,
u[v]には、sからSの頂点のみを経由したvまでの最短コストが記録されていることになります。
つまり1,2の処理が全て終了すると、u[v]に,sからvまでの最短コストが記録されます。

ダイクストラ法の図解

プロセスがわかりやすいように、ダイクストラ法を図解してみます。

下図のようなグラフがあり、始点をAをとします。 Aから各々の頂点への最短経路をダイクストラで求めてみます。

まず、始点Aを0で初期化し、各々への頂点に探索が完了していないことを示すために最大値を代入(変数d[]が対象となる)します。

出典:MIT open course ware

ここから、2.のプロセスに入ります。
最短経路木を示す頂点の集合をSとして、Sを以下のように表します。

S = {} {A B C D E }(Sから各頂点の最短経路の重さを示します。)

step1

まず、始点(s)である頂点AをSに追加します。

S = {A} {0 ∞ ∞ ∞ ∞ }

続いて、頂点Aに辺があり、最短経路未決定の頂点の最短経路を更新します。

最短経路か判定する式は、

if d[u] + w(u,v) < d[v]
　　 d[v] = d[u] + w(u,v)

なので、Aに隣接する頂点B,Cは頂点uが始点で重みが0なので、 辺への重みのみが加算され、以下のようになります。

S = {A} {0 10 3 ∞ ∞ }

step2

また、2.1のプロセスに戻ります。
2.1:V - Sの中から、d[u]が最小である頂点uを選択します。

つまり、最短距離未決定の最小頂点C(重み3)を選ぶことになりますが、
なぜ、最小コストの頂点を選んだ時点で、その地点が最短経路になるのかを、
図で考えてみます。

なぜ、最小コストの頂点が最短経路になるのか

下図のように始点から辺が3つ伸びているグラフがあるとします。
グラフより、各々の3つの頂点からその3つの頂点への辺があるとしても、
sから各々の頂点への3つの辺の中に必ず最短となる経路があることがわかります。

これは、辺が2つでも4つでも同じことです。

step2に戻ります。
Sに最短経路である頂点Cを追加します。

S = {A C} {0 10 3 ∞ ∞ }

続いて、Cにつながる頂点への最短経路更新プロセスに入り、
図を参考に以下のように更新します。

S = {A C} {0 7 3 11 5 }

step3

プロセス1に戻って、探索を開始する頂点を決定します。
最短点であるE(5)が選ばれるので、EをSに追加します。

S = {A C E} {0 7 3 11 5 }

プロセス2に移り、頂点Eにつながる頂点の最短点の更新を行います。

更新する頂点はないので、結果は前と変わりません。

S = {A C E} {0 7 3 11 5 }

step4

プロセス1に戻って、探索を開始する頂点を決定します。
最短点であるB(7)が選ばれるので、BをSに追加します。

S = {A C E B} {0 7 3 11 5 }

プロセス2に移り、頂点Bにつながる頂点の最短点の更新を行います。 頂点Dへの最短経路が9に変わります。

S = {A C E B} {0 7 3 9 5 }

step5

プロセス1に戻って、探索を開始する頂点を決定します。
ここで、全ての最短経路がもとまったので、処理を終了します。

始点sから頂点uへの最短経路はd[u]に入っていることになります。

隣接行列を用いたダイクストラ法

上記をふまえて以下のように実装します。
上記の対象の処理には番号を振っています。

#define MAX 100
#define INFTY 1<<22
// 未訪問の頂点を示す
#define WHITE 0
// 訪問済の頂点を示す
#define GRAY 1
// 未探索の頂点d[u]にはINFTYが入っている
#define BLACK 2
// 隣接行列頂点から頂点への辺の重みが入っている
// 例:gMatrix[0][1] 頂点0から1への重み INFTYの場合辺がないことを示す
int gMatrix[MAX][MAX];

void dijkstra(int n){
    // 最小の重みを記録する
    int minV;
    // u[v]に始点sからvまでの最短コストを保存する
    int u[MAX];
    // 訪問状態を記録
    int color[MAX];
    // 1.初期化
    for(int i = 0;i < n;++i){
        u[i] = INFTY;
        color[i] = WHITE;
    }
    // 0を始点とする
    u[0] = 0;
    color[0] = GRAY;
    
    while(1){
        minV = INFTY;
        // uは探索対象となる頂点を示す
        int u = -1;
        // 2.1 d[u]が最小である頂点を決定する
        for(int i = 0;i < n;++i){
            // 最短経路決定ずみの頂点は含めない
            if(minV > weight[i] && color[i] != BLACK){
                u = i;
                minV = weight[i];
            }
        }
        if(u == -1)break;
        // 選んだ頂点は最短経路決定利用はダイクストラロジック解説にて
        color[u] = BLACK;
        
        for(int v = 0;v < n;++v){
            // 辺が存在し、最短経路決定済頂点以外の経路が対象になる。
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                // 2.2最短コストを更新する
                // この処理の終了後weight[v]sからS内の頂点のみを経由したvまでの最短コストが記録される
                if(weight[v] > weight[u] + gMatrix[u][v]){
                    weight[v] = weight[u] + gMatrix[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
    // 出力
    for(int i = 0;i < n;++i){
        cout << i << " " << ( weight[i] == INFTY ? -1 : weight[i] ) << endl;
    }
}

プリム法と同様wikiに図解されているかなと思ったんですが、
残念ながらのっていませんでいした。
その代わりにアニメーション図がありました、全体の整理でないんでわかりにくい気がしますが。

それでは、ALDS1_12_Bの問題をふまえての全体のプログラムです。

#include <iostream>
using namespace std;
#define MAX 100
#define INFTY 1<<22
#define WHITE 0
#define GRAY 1
#define BLACK 2

int gMatrix[MAX][MAX];

void dijkstra(int n){
    // 最小の重みを記録する
    int minV;
    // weight[v]に始点sからvまでの最短コストを保存する
    int weight[MAX];
    // 訪問状態を記録
    int color[MAX];
    // 1.初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        color[i] = WHITE;
    }
    // 始点
    weight[0] = 0;
    color[0] = GRAY;
    
    while(1){
        minV = INFTY;
        // 頂点を示す
        int u = -1;
        // 2.1weight[u]が最小である頂点を決定する
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                u = i;
                minV = weight[i];
            }
        }
        if(u == -1)break;
        color[u] = BLACK;
        
        for(int v = 0;v < n;++v){
            // 辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                // 2.2最短コストを更新する
                // この処理の終了後weight[v]sからS内の頂点のみを経由したvまでの最短コストが記録される
                if(weight[v] > weight[u] + gMatrix[u][v]){
                    weight[v] = weight[u] + gMatrix[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
    // 出力
    for(int i = 0;i < n;++i){
        cout << i << " " << ( weight[i] == INFTY ? -1 : weight[i] ) << endl;
    }
}

int main(){
    int n;
    cin >> n;
    
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            gMatrix[i][j] = INFTY;
        }
    }
    
    int k,c,u,v;
    for(int i = 0;i < n;++i){
        cin >> u >> k;
        for(int j = 0;j < k;++j){
            cin >> v >> c;
            gMatrix[u][v] = c;
        }
    }
    dijkstra(n);
    return 0;
}

最終更新:2020/1/29

最小全域木問題をプリムのアルゴリズムと隣接行列で解く

最小全域木問題をプリムのアルゴリズムと隣接行列を使って解きたいとおもいます。 問題はALDS_1_12_A:Minimum Spanning Treeを参照してください。

プリム法

プリムのアルゴリズムを使って、最小全域木(MST)を求めるには、以下の通りに行います。

グラフG = (V,E)の頂点全体の集合をV,MSTに属する頂点の集合をTとする
1.Gから任意の頂点rを選らんで、それをMSTのルートとしてTに追加する。
2.以下の処理をT=Vになるまで繰り返す

Tに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小のものである辺(p(u),u)を選び、
それをMSTの辺とし、uをTに追加する

上を実行する過程がプリム法のwikipediaの図に詳しくまとめられていたので、そちらを見るとわかりやすいと思います。

ここで、最小の重みの辺を保持するために、以下の変数を用います。
ここで、頂点の数n = |V|とします。

gColor[n] : color[v]にvへの訪問状態を色で記録します。
WHITE:未訪問,GRAY:訪問(未確定),BLACK(最小値決定済み)

gMatrix[n][n] : gMatrix[u][v]にuからvへの辺の重みを記録した隣接行列

weight[n] : weight[v]にTに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する

parent[n] : parent[v]にMSTにおける頂点vの親を記録する

プリムのアルゴリズムのコード

では、コードを見ていきます。
実施していく過程はwikiの図を見るとわかりやすいと思います。

#define MAX 100
#define INFTY 1 << 21
// 未訪問状態
#define WHITE 0
#define GRAY 1
#define BLACK 2

// 隣接行列
int gMatrix[MAX][MAX];

int prim(int n){
    // 頂点
    int u;
    // 最小の重み
    int minV;
    // Tに属する頂点と(V - T)に属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する
    int weight[MAX];
    // MSTにおける頂点vの親を記録する
    int parent[MAX];
    // 訪問状態を記録する
    int color[MAX];
    // 初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        parent[i] = -1;
        color[i] = WHITE;
    }
    // 初回探索地点をindex0にする
    weight[0] = 0;
    
    while(1){
        minV = INFTY;
        u = -1;
        // 隣接する地点で
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                // 最小の重みを記録する
                u = i;
                minV = weight[i];
            }
        }
        // 全て訪問した
        if(u == -1)break;
        // 訪問済み
        color[u] = BLACK;
        for(int v = 0;v < n;++v){
            // uとvの間に辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                if(weight[v] > gMatrix[u][v]){
                    // 隣接する辺に重みを割り当てる
                    weight[v] = gMatrix[u][v];
                    parent[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i = 0;i < n;++i){
        if(parent[i] != -1) sum += gMatrix[i][parent[i]];
    }
    
    return sum;
}

O記法を考える

隣接行列を使ったプリムのアルゴリズムは
重みが最小である頂点を探すために、グラフの頂点数調べる必要があるので、
O(|V|^2)のアルゴリズムになります。

では、ALDS_1_12_A:Minimum Spanning Tree
を例題とした全体のコードです。

#include 
using namespace std;

#define MAX 100
#define INFTY 1 << 21
// 未訪問状態
#define WHITE 0
#define GRAY 1
#define BLACK 2

// 隣接行列
int gMatrix[MAX][MAX];

int prim(int n){
    // 頂点
    int u;
    // 最小の重み
    int minV;
    // Tに属する頂点と(V - T)に属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する
    int weight[MAX];
    // MSTにおける頂点vの親を記録する
    int parent[MAX];
    // 訪問状態を記録する
    int color[MAX];
    // 初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        parent[i] = -1;
        color[i] = WHITE;
    }
    // 初回探索地点をindex0にする
    weight[0] = 0;
    
    while(1){
        minV = INFTY;
        u = -1;
        // 隣接する地点で
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                // 最小の重みを記録する
                u = i;
                minV = weight[i];
            }
        }
        // 全て訪問した
        if(u == -1)break;
        // 訪問済み
        color[u] = BLACK;
        for(int v = 0;v < n;++v){
            // uとvの間に辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                if(weight[v] > gMatrix[u][v]){
                    // 隣接する辺に重みを割り当てる
                    weight[v] = gMatrix[u][v];
                    parent[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i = 0;i < n;++i){
        if(parent[i] != -1) sum += gMatrix[i][parent[i]];
    }
    
    return sum;
}

int main(){
    int n;
    cin >> n;
    
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            int edge;
            cin >> edge;
            gMatrix[i][j] = (edge == -1) ? INFTY : edge;
        }
    }
    
    cout << prim(n) << endl;
    return 0;
}

参考

全域木・最小全域木とは

全域木(Spanning tree)とは

グラフG = (V,E)の全域木G = (V',E')とは、
グラフの全ての頂点Vを含む部分グラフであり(V = V')、木である限りできるだけ多くの辺を持つものをいう。 グラフの全域木は、深さ優先探索や幅優先探索で求めることができますが、求める全域木は一つになるとは 限らず、探索方法により変化します。

最小全域木(Minimum Spanning Tree)とは

グラフの全域木の中で辺の重みの総和が最小のもののこと

参考

グラフの連結成分をALDS1_11_D:Connected Componentsを利用してc++で学ぶ

グラフの連結成分に関してALDS1_11_D:Connected Componentsを参考にして学びます。

問題文

連結成分分解
SNS の友達関係を入力し、
双方向の友達リンクを経由してある人からある人へたどりつけるかどうかを判定するプログラムを作成してください。

入力

１行目にSNS のユーザ数を表す整数 nn と友達関係の数 mm が空白区切りで与えられます。
SNS の各ユーザには 0 から n－1 までのID が割り当てられています。

続く mm 行に１つの友達関係が各行に与えられます。
１つの友達関係は空白で区切られた２つの整数 ss、tt で与えられ、ss と tt が友達であることを示します。

続く１行に、質問の数 qq が与えられます。続くqq 行に質問が与えられます。
各質問は空白で区切られた２つの整数 ss、tt で与えられ、「ss から tt へたどり着けますか？」という質問を意味します。

出力

各質問に対して ss から tt にたどり着ける場合は yes と、たどり着けない場合は no と１行に出力してください。

入力例

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

出力例

yes
yes
no

同じグループに属するか判定する処理

色を振り分けることにより同じグループに属するかどうかを判定します。

void assignColor(int number){
    int id = 1;
    for(int i = 0;i < number;++i){
        color[i] = NIL;
    }
    for(int i = 0;i < number;++i){
        if(color[i] == NIL)dfs(i,id++);
    }
}

続いて深さ優先探索にて、自身の友達に対し色を割り当てます。
これを元にして、探索を行います。

void dfs(int r,int c){
    stack<int>s;
    // 自身を入れる
    s.push(r);
    // colorに自信のidを入れる
    color[r] = c;
    while(!s.empty()){
        // 自身
        int u = s.top();
        s.pop();
        // 自分の友達に色を割り当てる
        for(int i = 0;i < gGraph[u].size();++i){
            int v = gGraph[u][i];
            if(color[v] == NIL){
                color[v] = c;
                s.push(v);
            }
        }
    }
}

では、 c++の解答例です。

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

#define MAX 1000000
#define NIL -1

vector<int>gGraph[MAX];
int color[MAX];

void dfs(int r,int c){
    stack<int>s;
    // 自身を入れる
    s.push(r);
    // colorに自信のidを入れる
    color[r] = c;
    while(!s.empty()){
        // 自身
        int u = s.top();
        s.pop();
        // 自分の友達に色を割り当てる
        for(int i = 0;i < gGraph[u].size();++i){
            int v = gGraph[u][i];
            if(color[v] == NIL){
                color[v] = c;
                s.push(v);
            }
        }
    }
}

void assignColor(int number){
    int id = 1;
    for(int i = 0;i < number;++i){
        color[i] = NIL;
    }
    // 同じグループに属するかの色を割り当てる
    for(int i = 0;i < number;++i){
        if(color[i] == NIL)dfs(i,id++);
    }
}

int main(){
    int s,t,m,q,n;
    
    cin >> n >> m;
    
    // 友達関係数
    for(int i = 0;i < m;++i){
        cin >> s >> t;
        // 各々のインデックスごとに友達を加算する
        gGraph[s].push_back(t);
        gGraph[t].push_back(s);
    }
    
    assignColor(n);
    
    cin >> q;
    
    for(int i = 0;i < q;++i){
        cin >> s >> t;
        if(color[s] == color[t]){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }
    return 0;
}

参考資料 https://book.mynavi.jp/ec/products/detail/id=35408

メモ化再帰方法によるフィボナッチ数列

メモ化再帰方法によるフィボナッチ数列をALDS_1_10_A:BibonacciNumberを例題に学びます

メモ化再帰方法とは

複雑な計算処理の結果を保存しておき、再度その計算が必要な際にその値を使うことで
処理の負担を減らすことです。

問題からフィボナッチ数列の計算方法を抜粋すると

             1 (n = 0)
fib(n)= 1 (n = 1)
              fib(n - 1) + fib(n- 2)

となりますが、この計算結果を配列などに保存しておき、
再帰的に計算する際に保存した計算結果を使うことで、
計算にかかる処理を短縮します。

では、ALDS_1_10_A:BibonacciNumberに合わせた全体のプログラムです。

#include <iostream>
using namespace std;

int result[45];

int fib(int n){
    if(n == 0 || n == 1)return result[n] = 1;
    if(result[n] != -1) return result[n];
    return result[n] = fib(n - 1) + fib(n - 2);
}

int main(){
    int n;
    for(int i = 0;i < 45;++i){
        result[i] = -1;
    }
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

最大値に関する優先度付きキューの実装をc++で学ぶ

最大値を返却する優先度付きキューをc++で実装して見たいと思います。
問題文はALDS1_9_C:Priority Queueを参照してください

実装方法としては、キーが大きいものを優先することから
単純にmaxヒープを使うことで実装できます。
maxヒープに関しては、こちらを参照してください。

まず、キーを挿入するinsert関数からみていきたいと思います。
ヒープのサイズを増やして、正しい位置にキーを挿入する流れになります。

void insert(int key){
    gSize++;
    gHeap[gSize] = -INFINITY;
    increaseKey(gSize, key);
}

increaseKey(int i,int key)関数は
2分ヒープの要素iのkeyを増加させる役割を担います。

void increaseKey(int i ,int key){
    if(key < gHeap[i])return;
    gHeap[i] = key;
    while(i > 1 && gHeap[i / 2] < gHeap[i]){
        swap(gHeap[i],gHeap[i / 2]);
        i = i / 2;
    }
}

キーを交換する箇所では、現在の要素のキーと親の要素のキーを比較して、
要素のキーが大きい間、親の要素との交換を繰り返すことで、正しい位置に挿入します。

例として、{20,9,10,7,6,8,5,1,2,4}に15を追加し、追加した位置にincreaseKye関数を実行して見たいと思います。

           20
      9         10
  7     6    8    5
1 2  4 

           20
      9         10
  7     6    8    5
1 2  4 15

           20
      9         10
  7    15    8    5
1 2  4 6

           20
      15         10
  7    9    8    5
1 2  4 6

優先度付きキュー最大値を取得する

つづいて、最大値を取得するプログラムを書きます。
最大ヒープになっているので、根の値を取得すればいいことになります。
取り出す関数を見ていきます

int extract(){
    int maxv;
    if(gSize < 1) return -INFINITY;
    maxv = gHeap[1];
    gHeap[1] = gHeap[gSize--];
    maxHeapify(1);
    return maxv;
}

一時変数に最大値を保持をさせ、
根にヒープの最後の値を移動し、ヒープのサイズを減らします。
最後に根からmaxHeapify関数を実施します。

例として2分ヒープ{20,9,10,7,6,8,5,1,2,4}から最大値を取り出す様子を図にしてみます。

           20
      9         10
  7     6    8    5
1 2  4 

           4
      9         10
  7     6    8    5
1 2  4 

            4
      9         10
  7     6    8    5
1 2   

           10
      9         8
  7     6    4    5
1 2   

最後にALDS1_9_C:Priority Queue
に対応した全体のソースになります。

#include <iostream>

using namespace std;
#define MAX 2000000
#define INFINITY (1<<30)

int gHeap[MAX + 1],gSize;

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

int extract(){
    int maxv;
    if(gSize < 1) return -INFINITY;
    maxv = gHeap[1];
    gHeap[1] = gHeap[gSize--];
    maxHeapify(1);
    return maxv;
}

void increaseKey(int i ,int key){
    if(key < gHeap[i])return;
    gHeap[i] = key;
    while(i > 1 && gHeap[i / 2] < gHeap[i]){
        swap(gHeap[i],gHeap[i / 2]);
        i = i / 2;
    }
}

void insert(int key){
    gSize++;
    gHeap[gSize] = -INFINITY;
    increaseKey(gSize, key);
}

int main(){
    int key;
    char com[10];
    
    while(1){
        cin >> com;
        if(com[0] == 'e' && com[1] == 'n') break;
        if(com[0] == 'i'){
            cin >> key;
            insert(key);
        }else{
            cout << extract() << endl;
        }
    }
    return 0;
}

最大ヒープを出力させるアルゴリズム

ALDS_1_9_B:MaximumHeapを例題にmaxヒープを構築するプログラムを学びます。

最大ヒープとは

以下引用

「節点のキーがその親のキー以下である」という max-ヒープ条件を満たすヒープを、
max-ヒープと呼びます。
max-ヒープでは、最大の要素が根に格納され、ある節点を根とする部分木の節点のキーは、
その部分木の根のキー以下となります。
親子間のみに大小関係があり、兄弟間に制約はないことに注意してください。

この問題でmaxヒープを構築する方法として、2つの関数を用いています。
ひとつは、maxHeapify(A,i)関数で、A[i]をmaxヒープ条件を満たすまで木の葉まで下降させます。

maxHeapify関数

maxHeapify(A,i)はiの左の子と右の子のうち、キーが大きい方を選び、
A[i]よりも大きければ交換する処理を再帰的に繰り返します。
問題に載っている疑似コードをc++に書き直すと以下のようになります。

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    // 値が大きければ交換する
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

buildMapHeap関数

もう一つの関数は、与えられた配列を最大ヒープにするbuildMapHeapです。

この関数では、
子を持つ節点の中で、添え字が最大の節点(2分ヒープの性質上HeapSize / 2となる)から逆順にmaxHeapify(A,i)を行います。

最大ヒープが構築される過程を図で確認する

例として2分ヒープA = {4,1,3,2,16,9,10}
を図にしてみてみましょう。

        4
  1         3
2  16  9  10

子を持つ中で添え字が最大の節点は7 / 2 = 3になりますので、
maxHeapify(A,3)からスタートします。

        4
  1         10
2  16  9    3

続いて、maxHeapify(A,2)関数を呼びます。

        4
  16         10
2  1  9    3

最後に、maxHeapify(A,1)関数を呼びます。

        16
    4        10
2     1   9     3

アルゴリズムに従いmaxヒープが完成しました!

最後に全体のソースコードになります。

#include <iostream>
using namespace std;
#define MAX 2000000

int gHeap[MAX + 1],gSize;

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

int main(){
    cin >> gSize;
    
    for(int i = 1;i <= gSize;++i) cin >> gHeap[i];
    // buildMaxHeap
    for(int i = gSize / 2;i >= 1;--i)maxHeapify(i);
    
    for(int i = 1;i <= gSize;++i){
        cout << " " << gHeap[i];
    }
    cout << endl;
    
    return 0;
}

完全2分木を2分ヒープを題材にしてc++で学ぶ

完全2分木を2分ヒープを題材として、解いてみたいとおもいます。
問題はAIDZU ONLINE JUDGEのALDS1_9_A問題を使いますので、
問題文などはリンクを参照してください。

完全2分木とは

以下問題文からの抜粋です。

すべての葉が同じ深さを持ち、すべての内部節点の次数が 2であるような二分木を完全二分木と呼びます。
また、二分木の最下位レベル以外のすべてのレベルは完全に埋まっており、
最下位レベルは最後の節点まで左から順に埋まっているような木も（おおよそ）完全二分木と呼びます。

完全2分木を配列に当てはめる方法としてはヒープについて書いた記事を参考にしてください。
この法則にしたがって、配列に代入し、出力していきます。
まずは、配列に代入されたキーを出力する箇所をみていきます。

int parent(int i){
    return i / 2;
}

int left(int i){
    return 2 * i;
}

int right(int i){
    return (2 * i) + 1;
}

ヒープを出力する際のルールに則って値を返しています。

あとは、入力されたキーを配列に挿入していき、
対象のキーを出力するのみです。
では、全体のプログラムになります。

#include <iostream>
using namespace std;

#define MAX 100000

int parent(int i){
    return i / 2;
}

int left(int i){
    return 2 * i;
}

int right(int i){
    return (2 * i) + 1;
}

int main(int argc, const char * argv[]) {
    int num,Heap[MAX + 1];
    
    cin >> num;
    for(int i = 1;i <= num;++i){
        cin >> Heap[i];
    }
    
    for(int i = 1;i <= num;++i){
        cout << "node " << i << ": key = " << Heap[i] << ", ";
        if(parent(i) >= 1) cout << "parent key = " << Heap[parent(i)] << ", ";
        if(left(i) <= num) cout << "left key = " << Heap[left(i)] << ", ";
        if(right(i) <= num) cout << "right key = " << Heap[right(i)] << ", ";
        cout << endl;
    }
    
    return 0;
}

二分ヒープとは図で学ぶ

二分ヒープの概念についてまとめます。

2分ヒープ(Binary Heap)は、図のように木の各接点に割り当てられたキーが
一つの配列の各要素に対応した完全二分木で表された構造のことです。
下記の図が2分ヒープを表したものです。

                   [1]
                   25

          [2]               [3]
          12                ９

    [4]        [5]    [6]          [7]
     6          8      5            4

 [8]   [9] [10]
  3     2    1

この図を配列で表すと以下のようになります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
25  12   9   6   8   5   4   3   2   1

2分ヒープを配列で表す

図では、2分ヒープを1次元配列で表しています。
2分ヒープを表す配列をA、2分ヒープのサイズをHとすると、
A[1,...,H]に2分ヒープの要素が格納されます。

木の添え字を1から、説点の添え字iが与えられた時の各々にアクセスするには

親[i] = floor(i / 2)(床関数)
左の子[i] = 2 * i
右の子[i] (2 * i ) + 1

で表すことができます。

maxヒープとminヒープ

2分ヒープの各説点のキーは、次に上げるヒープの条件を保つように格納されます。

maxヒープ条件
各節点のキーがその親のキー以下

minヒープ条件
節点のキーがその親のキー以上

図であげた2分ヒープはmaxヒープになります
親子関係のみに大小関係があり、兄弟間に制約はありません。

2分探索木の削除のやり方をc++で学ぶ

ALDS1_8_Cを参考にして2分探索木の削除方法を学んでいきます。
問題文の2分探索木の削除に関するアルゴリズムを抜粋します。

2分探索木から与えられたキーkを持つ節点zを削除するdelete kは、
以下の3つの場合を検討したアルゴリズムに従い、
2分探索木条件を保ちつつ親子のリンク(ポインタ)を更新します。

• 1.zが子を持たない場合、zの親pの子（つまりz）を削除する。
• 2.zが1つの子を持つ場合、zの親の子をzの子に変更、
  zの子の親をzの親に変更し、zを木から削除する
• 3.zが子を2つ持つ場合、zの次節点yのキーをzのキーへコピーし、yを削除する。
  yの削除では1.または2.を適用する。
  ここで、zの次節点とは、中間順巡回でzの次に得られる節点である。

問題では削除する節点としてzを引数として受け取ります。
削除する節点の候補をyとして
削除するyの子をxとして
図で各々のケースを確認してみます。

子を持たないケース(case1)

1をkeyにもつノードを削除したいとします。
ノード1は子を持たないので、繋ぎ直しをする必要がありません。
よって、そのまま消すことができます。

       0
  1(z = y)

子を1つ持つケース(case2)

12をキーにもつノードを削除したいとします。 12は左の子を持っています。

            30
  12(z = y)               88
1(x)  

12をキーにもつノードを削除したいとします。 12は右の子を持っています。

            30
  12(z = y)               88
        15(x)

子を2つ持つケース(case3)

0をキーにもつノードを削除したいとします。
0は下図のような子を持っています。

       0(z)
  1      4
2 3   5(y) 8        
           7(x)

削除する節点yを決める

case1,2の場合はyをzそのものにします。

case3の場合は、中間順巡回でzの次に訪問される節点にします。

削除する節点yの1つの子xを決める

case1の場合は右の子(NIL)
case2の場合はNILでない子
case3の場合はzの次節点の右の子(次節点は最小値なのでに左の子は存在しない)になります。

削除する節点yの親子のポインタを繋ぎ変えてyを削除する

xの親がyの親になるようにポインタを繋ぎ変えます。

yの親の子がxになるようにポインタを繋ぎ変える

yが根のケースなのか、(yの親の)左の子なのか右の子なのかを調べて
ポインタを繋ぎ変えます。

最後に、case3限定でzのキーにyのキーを設定します。

プログラムの部品

続いて、部品となるプログラムをみていきます。
まずは、次節点を返すgetSuccessor関数です。

Node* getTreeSuccessor(Node *x){
    // xに右の子が存在する場合右部分木でキーが最も小さい節点xの次節店にあんる
    if(x->right != NIL)return getMinimumTree(x->right);
    // 右の子が存在しない場合
    Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }
    return y;
}

右の子が存在しない場合、親をたどっていき、
最初に左の子になっている節点の親が次節点になります。
節点に次節点が存在しない場合(木の中でxが最大のキーを持つ場合)はNILを返します。

2分探索木の節点xを根とする場合の最小のキーを持つ節点を返す
getMinimumTree関数です

Node* getMinimumTree(Node *x){
    while(x->left != NIL) x = x->left;
    return x;
}

では、ALDS1_8_Cの問題に合わせたプログラムです。
削除するdeleteTree関数では、上記の手順で書いています。

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

Node* getMinimumTree(Node *x){
    while(x->left != NIL) x = x->left;
    return x;
}

Node* getTreeSuccessor(Node *x){
    if(x->right != NIL)return getMinimumTree(x->right);
    Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }
    return y;
}

void deleteTree(Node *z){
    Node *y;    // 削除対象Node
    Node *x;    // yの子
    
    // 子がない場合はまたは一つしか子がない場合は対象の節点をそのまま消す
    if(z->left == NIL || z->right == NIL){
        y = z;
    }
    else{
        y = getTreeSuccessor(z);
    }
    
    // yの子xを求める
    if(y->left != NIL){
        x = y->left;
    }
    else{
        x = y->right;
    }
    
    if(x != NIL){
        x->parent = y->parent;
    }
    
    if(y->parent == NIL){
        gRoot = x;
    }else{
        if(y == y->parent->left){
            y->parent->left = x;
        }else{
            y->parent->right = x;
        }
    }
    
    if(y != z){
        z->key = y->key;
    }
    free(y);
}

Node *find(Node* u,int value){
    while(u != NIL && value != u->key){
        if(value < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com[0] == 'f'){
            cin >> x;
            Node *t = find(gRoot,x);
            if(t != NIL) cout << "yes\n";
            else cout << "no\n";
        }
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
        else if(com == "delete"){
            cin >> x;
            deleteTree(find(gRoot,x));
        }
    }
    return 0;
}

参考ソース https://book.mynavi.jp/ec/products/detail/id=35408

2分探索木の探索の方法をc++で学ぶ

2分探索木の探索について学びます。
問題はALDS1_8_B:Binary Search Tree2を題材にします。

2分探索木については、こちらに説明を書いています。
また、2分探索木の挿入については、こちらに書いています。

2分探索木の探索のコード

先のリンク先で書いた2分探索木のルールとして右の木の値が左の木よりも大きい
というルールで木を構築したので、キーが小さければ左の木をそうでなければ、右の木を探索していき。
木がNILになると見つからなかったというコードを書くことになります。

ここでは、探索したキーが見つかった場合、キーを持つ対象のノードを返し、
見つからなかった場合は空のノードを返す関数を書きます。
返り値のノードが空でなければ、2分探索技の中にキーが存在するということになります。

Node *find(Node* u,int value){
    while(u != NIL && value != u->key){
        if(value < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

while文でキーが見つからない&NILではないという条件文を書きました。
では、全体のソースコードを確認してみます。

c++による全体のソースコード

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

Node *find(Node* u,int value){
    while(u != NIL && value != u->key){
        if(value < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com[0] == 'f'){
            cin >> x;
            Node *t = find(gRoot,x);
            if(t != NIL) cout << "yes\n";
            else cout << "no\n";
        }
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
    }
    return 0;
}

2分探索木挿入とはなにかをALDS 1_8_Aを題材にc++で学ぶ

2分探索木の挿入に関して、ALDS 1_8_A:Binary Search Tree1を題材にして学びます。

2分探索木の挿入

今回の問題では、右の木よりも左の木の方が値が小さいという条件のもと、
2分探索木を構築していきます。
30,88,12,1,20,17,25の値を空の木に挿入し、木が構築される例を見ていきます。

2分木の根から挿入するキーが対象のノードに対し、大きいか小さいかを判定し、
対象の根が空になった時点で空となった対象の親に左または右に挿入します。

key30を挿入

            30

木が空なので、そのまま挿入します。

key88を挿入

            30

                     88

rootのキー30を対象にして、挿入位置をチェックします。
rootのキー30よりも挿入キーが大きいので、30の右側に挿入します。

key12を挿入

            30

  12               88

12はrootの30よりも小さいので、30の左に挿入します。

key1を挿入

            30

  12               88

1  

対象を30,12と移動して1を挿入します。

key20挿入

            30

  12               88

1  20

key17挿入

            30

  12               88

1  20
 
  17

key25を挿入

            30

  12               88

1  20
 
    7  25

挿入手順として、根のキーを始点として探索します。
自身のキーが根のキーよりも小さければ左の子、
大きければ右の子を次の探索の節点として変えていき、
節点が空になったら挿入します。
また、その時に挿入する位置となる親を節点を変更するごとに保持・変更しておき、挿入位置が空になった時に、
親として代入することができるようにしておきます。

2分探索木挿入のプログラム

2分探索木を動的に実装するために以下の構造体を定義します。

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

続いて、挿入するプログラムを見ていきます。

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}

上記の図で説明したことをそのままプログラムにしています。
では、全体のソースです。

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
    }
    return 0;
}

2分探索木とはなにか？図で理解する

2分探索木は、各々の節点ごとにキーを持ち、2分探索木条件を常に満たすように構築された木です。

2分探索木条件とは、ある節点の左の木が兄弟の右の木やその節点よりも必ず低い値をもつなどの
一定の条件を満たす木のことです。
では、例を見ていきましょう

            30

  12           88

1  20
 
    7  25

この木の条件を例に見ると
キーが30の根の左部分木に該当するキーは全て30以下になっています。
右部分木に属する節点のキーは左部分木よりも大きいという条件が成り立っていることがわかります。
これが2分探索木になります。

木の巡回とは

木の操作には木の巡回と呼ばれる探索方法があります。
その探索方法を学びます。

例として以下の2分木を定義します。

       0
  1      4
2 3   5 8        
       6 7

この2分木を例として、木の巡回の出力例を見ていきましょう。

木の先行順巡回(Preorder Tree Walk)

根節点、左部分木、右部分木の順で節点の番号を出力します。

出力例
0 1 2 3 4 5 6 7 8

木の中間順巡回(Inorder Tree Walk)

左部分木、根節点、右部分木の順で節点の番号を出力します。

出力例
2 1 3 0 6 5 7 4 8

木の後行順巡回(Postorder Tree Walk)

左部分木、右部分木、根節点の順で節点の番号を出力します。

出力例
2 3 1 6 7 5 8 4 0

では、AIDU ONLINE JUDGEのALDS1_7_Cの木巡回の問題例に、
プログラムをチェックしましょう。

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

出力する位置を変えることによって、
各々の出力形式で出力しています。

では、全体のソースです。

#include <stdio.h>
#include <iostream>
using namespace std;
// node最大量
#define MAX 100000
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;
    // 初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
        // 親の設定
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

    // rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    cout << "Preorder\n";
    preParse(root);
    cout << "\n";
    cout << "Inorder\n";
    inParse(root);
    cout << "\n";
    cout << "Postorder\n";
    postParse(root);
    cout << "\n";
    
    return 0;
}

ALDS1_7_B BinaryTree(2分木)を参考にしてと2分木表現を学ぶ

AIZU ONLINE JUDGEのALDS1_7_B BinaryTree
の問題を参考に、2分木の表現方法を学びます。

問題文

与えられた根付き二分木 T の各節点 u
について、以下の情報を出力するプログラムを作成してください。

• uの節点番号
• uの親
• uの兄弟
• uの子の数
• uの深さ
• uの高さ
• 節点の種類（根、内部節点または葉）

ここでは、与えられる二分木は n 個の節点を持ち、それぞれ 0 から n－1 の番号が割り当てられているものとします。

入力例などは以下を参考にしてください。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_B&lang=jp

2分木を表現する構造体の定義

2分木を表現するための構造体の定義をします。
木を表現するためには、節点が必要になりますが、
2分木では節点は左右の子のみとルートを示す親を持てば
木全体を表現することができることがわかると思います。

struct Node {
    int parent;
    int left;
    int right;
};

2分木の深さをセットする

2分木の深さを求めるために、木のrootから子を探索し
left、right共にNILになるまで、再起的にチェックします。

// 深さを設定する
void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}

兄弟のノードを求める

兄弟のノードを求めるには、
単純に親がいるかをチェックし、親の左の子・右の子を調べます
子が自身のノードである可能性があるので、そのケースを除きます。

int getSibling(int u){
    // rootの場合
    if(gNode[u].parent == NIL)return NIL;
    // 自身が右の子だった場合
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
    // 自身が左の子だった場合
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
    // 親が一つしか子を持たない状態
    return NIL;
}

2分木の高さを求める

この場合の高さは、あるノードの末尾の子から自分との差分になります。
自分から左右の子が存在するかどうか再帰的にチェックしていき、深い方の子と自分との差分を返します。

// 高さの設定をする
int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

最後にc++で書かれた全体のソースを載せます。

#include <stdio.h>
#include <iostream>
using namespace std;
// node最大量
#define MAX 100005
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];
int gDepth[MAX],gHeight[MAX];

// 兄弟を返す
int getSibling(int u){
    // rootの場合
    if(gNode[u].parent == NIL)return NIL;
    // 自身が右の子だった場合
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
    // 自身が左の子だった場合
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
    // 親が一つしか子を持たない状態
    return NIL;
}

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "sibling = " << getSibling(node) << ", ";
    
    int deg = 0;
    if(gNode[node].left != NIL) deg++;
    if(gNode[node].right != NIL) deg++;
    cout << "degree = " << deg << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    cout << "height = " << gHeight[node] << ", ";
    
    if(gNode[node].parent == NIL){
        cout << "root\n";
    }else if(gNode[node].left == NIL && gNode[node].right == NIL){
        cout << "leaf\n";
    }else{
        cout << "internal node\n";
    }
}

// 深さを設定する
void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}

// 高さの設定をする
int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;
    // 初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
        // 親の設定
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

    // rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    // 根からはじめて深さを代入する
    setDepth(root, 0);
    setHeight(root);
    
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}

参考ソース
https://book.mynavi.jp/ec/products/detail/id=35408

ALDS1_7根付き木の解法と根付き木についてc++で学ぶ

AIZU Online judgeの根付き木の解法メモです。
サンプルのコードがわかりにくかったので、読み解いてみました。

問題は以下になります。

与えられた根付き木 T の各節点 u
について、以下の情報を出力するプログラムを作成してください。

• uの節点番号
• uの親の節点番号
• uの深さ
• uの節点の種類（根、内部節点または葉）
• uの子のリスト

ここでは、与えられる木は n 個の節点を持ち、それぞれ 0 から n－1 の番号が割り当てられているものとします。

入力

入力の最初の行に、節点の個数 n が与えられます。続く n行目に、各節点の情報が次の形式で１行に与えられます。

id
k c1 c2 ... ck

idは節点の番号、k は次数を表します。
c1 c2 ...ck は 1 番目の子の節点番号、... k 番目の子の節点番号を示します。

出力方式

次の形式で節点の情報を出力してください。節点の情報はその番号が小さい順に出力してください。

node id: parent = p , depth = d, type, [c1...ck]

pは親の番号を示します。ただし、親を持たない場合は -1 とします。
dは節点の深さを示します。

typeは根、内部節点、葉をそれぞれあらわす root、internal node、leaf の文字列のいずれかです。
ただし、根が葉や内部節点の条件に該当する場合は root とします。

c1...ck は子のリストです。
順序木とみなし入力された順に出力してください。
カンマ空白区切りに注意してください。
出力例にて出力形式を確認してください。

入力例

13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0

出力

node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

問題は以上です。

根付き木とは

根(root)を持つ木構造のことを根付き木といいます。
根は親を持たない唯一の節点のことをいいます。

では、問題を解いていきます。
まず、木の接点となるnodeの定義をします。

// node最大量
#define MAX 100005
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];
int gDepth[MAX];

構造体としてNodeを定義して
子がないことなどを示すためNILを定義しました。
NILはobjective-cなどにも定義されています。

leftは子という意味合いでrightは同じ階層の兄弟のような意味合いです。

続いて出力関数を定義します。

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    
    if(gNode[node].parent == NIL) cout << "root, ";
    else if(gNode[node].left == NIL)cout << "leaf, ";
    else cout << "internal node, ";
    
    cout << "[";
    
    for(int i = 0,left = gNode[node].left;left != NIL;++i,left = gNode[left].right){
        if(i) cout << ", ";
        cout << left;
    }
    cout << "]" << endl;
}

わかりにくいところは、left(左の木)を出力する箇所だと思います。
順番としてまず、対象のnodeのleftを出力します。
続いて、出力したleft nodeに飛び、そのleft(nodeと表現できる)のrightをのleftを出力
これを繰り返します。

続いて深さを求めて、global変数gDepthに代入する関数です。

// 再帰的に深さを求める
void rec(int node ,int parent){
    gDepth[node] = parent;
    if(gNode[node].right != NIL){
        // 右の兄弟に同じ深さを設定
        rec(gNode[node].right,parent);
    }
    if(gNode[node].left != NIL){
        // 最も左の子に自分の深さ+1を設定
        rec(gNode[node].left,parent + 1);
    }
}

道具が揃ったので、main関数を書きます。

int main(){
    int nodeNum,nodeIndex,node,left,root,n;
    cin >> n;
    // 1.初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    // 2.nodeに代入していく
    for(int i = 0;i < n;++i){
        cin >> nodeIndex >> nodeNum;
        for(int j = 0;j < nodeNum;++j){
            cin >> node;
            // 初期値はleft
            if(j == 0){
                gNode[nodeIndex].left = node;
            }
            else{
                gNode[left].right = node;
            }
            left = node;
            gNode[node].parent = nodeIndex;
        }
    }
    
    // 3.rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    // 根からはじめて深さを代入する
    rec(root,0);
    
    // 4.nodeのindexごとに出力する
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}

1.初期化
まずは、NILで初期化します。

2.gNodeに入力された情報を埋め込みます。
初期値は必ずleftに2つめ以降はrightに入れていきます。
nodeの親は変わりません。

3.で根をさがしてそのindexを代入しています。

4.最後にprint関数を使い、nodeのindex順に出力します。

以上です。

こちらを参考にしています。