アルゴリズム入門講座: 木構造

ラベル 木構造 の投稿を表示しています。すべての投稿を表示

2018年2月19日月曜日

全域木・最小全域木とは

全域木(Spanning tree)とは

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

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

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

参考

2018年2月12日月曜日

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

2018年2月11日日曜日

二分ヒープとは図で学ぶ

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

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ヒープになります
親子関係のみに大小関係があり、兄弟間に制約はありません。

2018年2月10日土曜日

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

2018年2月9日金曜日

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

2018年2月6日火曜日

木の巡回とは

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

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

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

2018年2月2日金曜日

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 は子のリストです。
順序木とみなし入力された順に出力してください。
カンマ空白区切りに注意してください。
出力例にて出力形式を確認してください。

入力例

出力

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順に出力します。

以上です。

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

2017年11月16日木曜日

木構造の解説

枝分かれしながら、データが増えていくデータ構造を木構造といいます。

木構造を図で示すと以下のようになります。

木は節点(node)とそれらを結んでいる枝(branch)によって構成されます。
節点はデータを表し、枝はその節点との関係にあたります。

分岐元の節点を親といい、枝をたどった先の節点を子といいます。

また、一番先頭の接点を根(root)と呼び、子を持たない接点のことを葉(reef)といいます。

深さと高さ

根からある節点に至るまでに通る枝の数をその頂点の深さ(depth)といい、
根から最も深い節点までの深さを木の高さ(height)>といいます。

図でいうと、木の高さは2になります。

2分木と2分探索木

木のうちで、各々の節点から出る枝の数が2本以下であるものを2分木といいます。

また、各々の節点のデータが比較可能で、
親と子の関係に規則がある(親と子に大小の関係あるなど)木のことを2分探索木(binary search tree)といいます。

この規則を元にし、アルゴリズムでは木が利用されます。

登録: 投稿 (Atom)