木(Tree) #1 概要

さて、アルゴリズムの第一回目ということで、今回は木構造を扱います。
木構造とは、簡単に言うと以下のようなものです。

このような階層構造を表すときに木構造は使われます。
では、上の構造をもうちょっと一般化してみましょう。

木構造では一番上のものを根(root)、それ以外を節(node)と呼びます。
また、根に近いものを親、その下にあるものを子と呼びます。
（例えば、図2の「子」(B)はさらにその下の子(D,E)から見れば親となります。


今回は、木構造の中でも比較的単純な2分探索木について簡単に実装してみましょう。
と、いきなり2分探索木について紹介したいところですが、まずはその前に二分木にて見てみます。
二分木とは、

• 親が持っている子の数が二つ以下

という条件を満たす木のことを言います。

先ほどの図1や図2がその例です。
（ちなみに子の数は三つ以上のものは多分木と呼ばれています。

それでは2分探索木とはどのようなものでしょうか。

それぞれのノードに数値などの比較出来るものが割り振られているとき、二分木の条件に加えて、

• 左側の子≦親≦右側の子

という条件を満たすのが2分探索木です。
（左側が大きくて右側が小さいという条件でも構いません。

具体的に見てみましょう。

この構造になっていれば、探索がかなり容易になります。
例えば14を探したいときには、まず根(root)である24と比較して、小さいので左の子へ行く。
10と比較すると大きいので右の子に行く。
そこで14が見つかります。
比較して小さければ左へ、大きければ右へ行くということを繰り返せばいいのです。

では、今述べたことを実際にプログラムで実装してみましょう。
一番下の節は子を持っていませんので、ダミーの値を入れておきます。
以下は図3の構造で、14を探す場合のプログラムです。

//Java

class Node {
  private Node left;
  private Node right;
  private int value;

  public Node(Node left, Node right, int value)
  {
    this.left = left;
    this.right = right;
    this.value = value;
  }

  public Node getLeft(){
    return left;
  }
  public Node getRight(){
    return right;
  }
  public int getValue(){
    return value;
  }
}

class Main {
  public static void main(String[] args) {
    Node root, left, right, leftparent, rightparent;
    left = new Node(null,null,9);
    right = new Node(null,null,14);
    leftparent = new Node(left, right, 10);

    left = new Node(null,null,27);
    right = new Node(null,null,34);
    rightparent = new Node(left, right, 31);

    root = new Node(leftparent, rightparent, 24);

    int seach_value = 14;
    Node now = root;
    while(true){
      if(now == null){
        System.out.print(seach_value + " is notfound.");
        break;
      } else if( seach_value < now.getValue() ){
        now = now.getLeft();
      } else if( seach_value > now.getValue() ){
        now = now.getRight();
      } else {
        System.out.print(seach_value + " is found.");
        break;
      }
    }
  }
}

#Ruby

class Node
  attr_reader :left,:right,:value
  def initialize(left, right, value)
    @value = value
    @left = left
    @right = right
  end
end

seach_value = 14
left = Node.new(nil,nil,9)
right = Node.new(nil,nil,14)
leftparent = Node.new(left,right,10)

left = Node.new(nil,nil,27)
right = Node.new(nil,nil,34)
rightparent = Node.new(left,right,31)

root = Node.new(leftparent,rightparent,24)
seach_value = 14
now = root
while true do
  if now == nil
    print(seach_value.to_s + "is notfound.")
    break
  end
  if seach_value < now.value
    now = now.left
  elsif seach_value > now.value
    now = now.right
  else
    print(seach_value.to_s + "is found.")
    break;
  end
end

今回は木の生成を手動でやったので、ちょっと分かりにくくなってしまいましたが。
（ソース自体もあまり綺麗ではない！

次回はこの二分（探索）木のノードの追加と削除、巡回(トラバーサル)を扱います。

[参考文献]

• 河西朝雄著『改訂C言語によるはじめてのアルゴリズム入門 』技術評論社, 2001年
• "木構造(データ構造)",フリー百科事典『ウィキペディア（Wikipedia）』