【Ruby】木構造を定義してみる

2016年3月25日Ruby

こんにちは、しきゆらです

 

今回は、Rubyで木構造を作ってみたので書いておきます

 

 

 

 

木構造とは

データ構造の一つで、データの階層構造を表したりデータを探しやすくするために用いられる

詳しくは、Wikipediaを参照　=>　木構造 (データ構造)

卒研でデータの階層構造を定義したかったので作ってみました

 

想定しているデータ

想定していたデータは、「value,parent」というデータがたくさんあるCSV形式のファイルを読み込んで木構造を作るというもので

  • 子ノードが複数存在する場合がある
  • 最上位ノードが複数存在する場合がある

という感じでした

ファイルの中には、Aというデータの木構造とBという木構造、Cという木構造・・・というように

複数の木構造が1つのファイルの中に入っている状態です

例として以下のようなデータがあった場合は・・・

A,root
B,root
a1,A
b1,B
C,root
a2,A
b2,B
c1,C

・A

—-a1

—-a2

・B

—-b1

—-b2

・C

—-c1

こんな感じにして欲しかったんです

上記の「最上位ノード」とは、例で言うところの「・A」のような「・」から始まっているノードのことです

 

作ったコード

木構造ということで調べてみると、出てくるのは2分木ばかり

ということで作ったものが以下のものです

 

# coding: utf-8

class Node
  attr_accessor :parent, :child, :value
  def initialize(value = 'root', parent = nil)
    @value = value
    @child = []
    @parent = parent
  end

  def ==(node)
    @value == node.value
  end

  # 兄弟要素を返す
  def brothers
    unless @parent.nil? then
      @parent.child
    else
      nil
    end
  end

  # 子要素を追加
  def add_child!(node)
    if self == node.parent then
      @child.push(node)
    else
      @child.each do |n|
        n.add_child!(node)
      end
    end
  end

  def to_s
    unless @parent.nil? then
      'value: ' + @value 
    else
      'root'
    end
  end

  def search(value)
    # valueが一致するものを探す
    if @value == value then
      return self
    else
      @child.each do |n|
        node = n.search(value)
        if node then
          return node
        end
      end
      return nil
    end
  end
end

 

各ノードには、そのノードがもつ値を表す「value」、親ノードを表す「parent」、子ノードを表す「child」を持っています

childに関しては、配列で管理しています

これは、子ノードに関する操作をeachなどの操作をしたかったから(自分で作ったクラスでもRubyっぽく振る舞って欲しかった)

 

ノードの持っているデータへのアクセサとして、parent、value、childを作成しました

また、そのノードの兄弟要素を取得したり(brothers)、特定の値を持ったノードを探すメソッド(search)を作りました

 

ファイルから木構造を作る

また、ファイルからデータを読み込んで木構造を返す関数(？)も作ってみました

def make_tree(file_path)
  node = Node.new
  childs = []
  File.open(file_path).each_line do |lines|
    lines = lines.chomp.split(',')
    value = lines.first
    next if lines[0] == 'value'
    if lines.last == 'root' then
      t = Node.new(value, node)
      node.add_child!(t)
      childs.push(t)
    else
      childs.each do |n|
        if n.value == lines.last then
          tmp = Node.new(value, n)
          node.add_child!(tmp)
          childs.push(tmp)
          break
        end
      end
    end
  end
  return node
end

 

この関数にファイルのパスを渡すと、ファイルの内容を取得して木構造をつくって返すようにしました

(各ノードにこの機能を持たせる必要はないので、Nodeクラス内で定義せず関数としてあります)

 

想定しているデータので書いたように、最上位ノードが複数存在する場合があるので

最上位ノードの親としてrootノードを作り、データを読み込んで木構造を作り、rootノードを返します

つまり、この関数で帰ってきたrootノードの子要素には最上位ノードが入っているので操作しやすくなっています

 

こんな感じで、必要としていたものは出来ました

自分でほしいと思っていたものができたのでかなり満足です

 

ここはこう書いたほうが見やすいよ、とか

ここの書き方危ないよ！などありましたら教えてください

 

おわり

Posted by しきゆら