プログラミング原人の進化ログ

プログラミング原人の進化論

オレ　プログラミング　ベンキョウ　スル。マナンダ　コト　カク。

トップ > アルゴリズム > 木構造の初歩を理解する

木構造の初歩を理解する

アルゴリズム アルゴリズム-データ構造

木というデータ構造があります。プロコンやグラフ理論の勉強をしていると出てくると思います。木ってなに？という方や、だいたいどんなものかは知っているけど実装したことはないという方に向けて、まず基本的なところをざっくり説明して、それから問題を解くことを通して実装を行います。具体的には、根付き木と二分木までをやろうと思います。

木とは

木（tree）はグラフの一種です。グラフといっても棒グラフや円グラフのことではなくて、グラフ理論でいうところのグラフです。すなわち、ノードとそれらをつなぐエッジから成る構造です。言葉で説明するより図を見てもらったほうが早いでしょう。一般的なグラフというのはこんな感じのやつです。

f:id:programgenjin:20190222150907p:plain

丸がノード、線がエッジを表現します。ところで、ノード1, 2, 3に注目してもらうと、輪っかのような構造になっていることがわかります。これを閉路と言いますが、木にはこれがありません。つまり、木とは閉路のないグラフであるということができます。次のようなイメージを持ってもらえばいいと思います。

f:id:programgenjin:20190222152207p:plain

木構造は色々な場面に出てきます。例えば、MacなどのUNIX系OSを使っている方はよくわかると思いますが、ディレクトリ構造はルートディレクトリを頂点とした木構造になっています。生物の種の分類なんかもこうした構造になっています。

根付き木

ある一つの（任意の）ノードを選んで、それを特別に根（root）と呼ぶことがあります。それを頂点とした木のことを、根付き木と言います。根付き木は階層構造を持っています。あるノードとエッジで結ばれている一つ下の階層のノードを子といい、逆にエッジで結ばれている一つ上の階層のノードを親と言います。根は親を持たないノードであるということができます。

f:id:programgenjin:20190224083523p:plain

子の数を次数と言います。上の図でいうと、ノード１の子はノード３、４で、次数は２ですね。ノード３、４の親はノード１となります。
また、子を持たないノードを葉（leaf）と言い、親と子を持つノードを内部ノード（internal node）と言います。

f:id:programgenjin:20190222154059p:plain


ノードの根からの距離（エッジの本数で数えます）を深さと言います。逆に、葉からの距離の最大値を高さと言います。

f:id:programgenjin:20190222152207p:plain

上の図で言えば、ノード１の深さは１、ノード３の深さは２です。また、ノード０の高さは２です。

二分木

二分木は根付き木の一種です。次数が２以下の根付き木を、二分木と言います。二分木には、左の子と右の子を区別するという特徴があります。つまり、
f:id:programgenjin:20190222155015p:plain
この二分木と、
f:id:programgenjin:20190222155028p:plain
この二分木は、別物ということになります。
ここで、二分木を以下の１または２を満たす木として再帰的に定義することができます。

  1. ただ一つのノードからなる木である
  2. 根および、左部文木・右部分木という２つの二分木からなる

どういうことかというと、下の図を見ればわかりやすいかと思います。

f:id:programgenjin:20190222160847p:plain


上の定義に従って、次々と二分木を構成していけることがわかります。

問題を解いてみよう

木構造の基本を理解したところで、今度は木構造を扱ったプロコンの問題を解いて、実装してみましょう。問題はAizu Online Judgeから取っています。

根付き木の問題

根付き木 | アルゴリズムとデータ構造 | Aizu Online Judge

各ノードがどのノードと繋がっているかという情報を保持するために、左子右兄弟表現を用います。この表現においては、各ノードはそのノードの親、そのノードの最も左の子、そのノードのすぐ右の兄弟という３つの情報を持っています。これを実現するために次のような構造体を定義しました。

struct Node {
  int parent;
  int left;     // 最も左の子
  int right;  // すぐ右の兄弟
};

Node型の配列Tを用いて各ノードの情報を管理することにします。
次に、各ノードの深さと、種類が知りたいので、それらを調べる関数を定義します。

void set_depth(Node T[], int id, int depth) {
  T[id].depth = depth;
  if (T[id].right != NIL) set_depth(T, T[id].right, depth);
  if (T[id].left != NIL) set_depth(T, T[id].left, depth + 1);
}

void set_type(Node T[], int id) {
  if (T[id].parent == NIL) T[id].type = "root";
  else if (T[id].left == NIL) T[id].type = "leaf";
  else T[id].type = "internal node";
}

注意して欲しいのがset_depth関数で、これは自分自身を再帰的に呼び出すことで、根から順に木をたどって各ノードの深さを記録していきます。こういうイメージです。
f:id:programgenjin:20190222172114j:plain
NILというのは、ノードが存在しないことを表す値で、今回は-1にしておきます（ノードの番号と被らなければOKです）。
これを用いた解答例が次です。なんとなく出力するときに形式を揃えたかったのでノードの深さや子などの情報を保持するメンバ変数を構造体Nodeに加えていることに注意してください。

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

#define NIL -1

struct Node {
  int parent;
  int left;
  int right;
  int depth;
  vector<int> child;
  string type;  
};

void set_depth(Node T[], int id, int depth) {
  T[id].depth = depth;
  if (T[id].right != NIL) set_depth(T, T[id].right, depth);
  if (T[id].left != NIL) set_depth(T, T[id].left, depth + 1);
}

void set_type(Node T[], int id) {
  if (T[id].parent == NIL) T[id].type = "root";
  else if (T[id].left == NIL) T[id].type = "leaf";
  else T[id].type = "internal node";
}

int main() {
  int i, j, n, root;
  struct Node T[100000];

  cin >> n;
  // initialize
  for (i = 0; i < n; i++) {
    T[i].parent = NIL;
    T[i].left = NIL;
    T[i].right = NIL;
  }

  int id, k, c;
  for (i = 0; i < n; i++) {
    cin >> id >> k;
    for (j = 0; j < k; j++) {
      cin >> c;
      T[id].child.push_back(c);
      T[c].parent = id;
      if (j == 0) T[id].left = c;
      else T[T[id].child[j-1]].right = c;
    }
  }

  for (i = 0; i < n; i++) {
    if (T[i].parent == NIL) root = i;
  }
    
  set_depth(T, root, 0);
  for (i = 0; i < n; i++) set_type(T, i);

  for (i = 0; i < n; i++) {
    cout << "node " << i << ": parent = " << T[i].parent << ", depth = " << T[i].depth << ", " << T[i].type << ", [";
    for (vector<int>::iterator it = T[i].child.begin(); it != T[i].child.end(); it++) {
      if (it != T[i].child.begin()) cout << ", ";
      cout << *it;
    }
    cout << "]" << endl;
  }

  return 0;
}

二分木の問題

二分木 | アルゴリズムとデータ構造 | Aizu Online Judge

先ほどと似た問題です。Nodeのメンバのleft, rightが先ほどと違い、それぞれ左の子と右の子を指すことにしています。
今回は高さを計算する必要があるので、次のような関数を定義しておきます。根から次々と木をたどって各ノードの高さを記録していく再帰関数です。

int set_height(Node T[], int id) {
  int h1 = 0, h2 = 0;
  if (T[id].right != NIL) h1 = set_height(T, T[id].right) + 1;    // 右の子
  if (T[id].left != NIL) h2 = set_height(T, T[id].left) + 1;  // 左の子
  
  T[id].height = max(h1, h2);
  return T[id].height;
}

深さを計算する関数やノードの種類を調べる関数は先ほど作ったものを少し変えるだけでOKです。次が解答例です。

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;

#define NIL -1

struct Node {
  int parent;
  int left;   // 左の子
  int right;  // 右の子
  int depth;
  int height;
  int degree;
  int sibling;
  string type;  
};

void set_depth(Node T[], int id, int depth) {
  T[id].depth = depth;
  if (T[id].right != NIL) set_depth(T, T[id].right, depth + 1);  // 右の子
  if (T[id].left != NIL) set_depth(T, T[id].left, depth + 1);  // 左の子
}

void set_type(Node T[], int id) {
  if (T[id].parent == NIL) T[id].type = "root";
  else if (T[id].degree == 0) T[id].type = "leaf";
  else T[id].type = "internal node";
}

int set_height(Node T[], int id) {
  int h1 = 0, h2 = 0;
  if (T[id].right != NIL) h1 = set_height(T, T[id].right) + 1;    // 右の子
  if (T[id].left != NIL) h2 = set_height(T, T[id].left) + 1;  // 左の子
  
  T[id].height = max(h1, h2);
  return T[id].height;
}

int main() {
  int i, n;
  Node T[25];

  cin >> n;

  // initialize
  for (i = 0; i < n; i++) {
    T[i].parent = NIL;
    T[i].sibling = NIL;      
  }

  int id, left, right, degree;
  for (i = 0; i < n; i++) {
    cin >> id >> left >> right;

    degree = 2;

    T[id].left = left;
    T[id].right = right;

    if (left != NIL) {
      T[left].parent = id;
      T[left].sibling = right;
    } else {
      degree--;
    }

    if (right != NIL) {
      T[right].parent = id;
      T[right].sibling = left;
    } else {
      degree--;
    }
     
    T[id].degree = degree;
  }

  // 根を探す
  int root;
  for (i = 0; i < n; i++) {
    if (T[i].parent == NIL) root = i;
  }

  set_depth(T, root, 0);
  for (i = 0; i < n; i++) set_type(T, i);
  set_height(T, root);

  for (i = 0; i < n; i++) {
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n", i, T[i].parent, T[i].sibling, T[i].degree, T[i].depth, T[i].height, T[i].type.c_str());
  }

  return 0;
}

まとめ

木について勉強しました。問題を解くことで理解が深まったんじゃないかなぁと思います。木は再帰関数と相性が良いみたいで実装する際にはどんどん出てくると思うのですが、まだ再帰関数には苦手意識があるので精進せねばと思う次第であります。
解答例などのコードはあんまり綺麗でないと思います。ご容赦を。

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.