Help us understand the problem. What is going on with this article?

Go言語で学ぶコンピュータサイエンス (データ構造とアルゴリズム編①)

More than 3 years have passed since last update.

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

ソートアルゴリズムやグラフ、連結リストなどがこの分野の中でよく扱われます。
今回はこの分野の中の、木構造の代表例である、バイナリツリーを扱います。

バイナリツリーとは

バイナリツリーとは、一つのノードが最大で2つのノードを持ち、それらが連鎖的に組み合わさってできるデータ構造です。
実際にコードを使いながら説明していきます。今回は、node型とtree型を定義します。

binary_tree.go
type node struct{
    value int
    left_node *node
    right_node *node
}

一つのノードは、ノード本体の値と、保有しているノードのポインタを持つという構造です。

binary_tree.go
type tree struct{
    top_node *node
}

treeは、一番上のノードのみを持つ構造です。このtreeに、最大値を求める関数や、値を挿入する関数をインターフェースとして実装していきます。

実装

挿入

binary_tree.go
func (t *tree) _insert(current_node *node, num int) (*node){
    if current_node == nil {
        n := &node{num, nil, nil}
        return n
    }

    if current_node.value < num {
        current_node.right_node = t._insert(current_node.right_node, num)
    }
    if current_node.value > num {
        current_node.left_node = t._insert(current_node.left_node, num)
    }
    return current_node
}

func (t *tree) insert(num int) (){
    t._insert(t.top_node, num)
}

今回は、バイナリサーチツリーという、探索を容易にするためのデータ構造を実装します。
ルールとしては、ある値をいれたいときに、既存のノードより大きい場合は右側に、小さい場合は左側に挿入するというものです。
データを挿入するためには、再帰呼び出しを使って効率よく挿入先を探索し、そこに&を使って挿入します。

最大値

binary_tree.go
func(t *tree) _max(current_node *node) (int) {
    if (current_node.right_node == nil){
        return current_node.value
    }
    t_max := t._max(current_node.right_node)
    return t_max;
}
func(t *tree) max() (int){
    return t._max(t.top_node)
}

こちらも再帰呼び出しを使って探索をします。挿入の時点で、探索を容易にするように実装しているので、簡単に最大値を呼び出すことができます。

実験

binary_tree.go
func main(){
    top_node := &node{10, nil, nil}
    t := &tree{top_node}
    t.insert(11)
    t.insert(9)
    t.insert(13)
    t.insert(8)
    t_max := t.max()
    fmt.Println(t_max)
}

実際に呼び出してみると、ちゃんと最大値が出力されていることがわかります。
全てのコードはこちらに上がっているので、ご参照ください。

まとめ

今回は、バイナリツリーを実装し、木構造の概念についての理解を深めました。
時間があるときに、もっといろんな種類のデータ構造を実装してみようと思います。

yamad07
機械学習の研究をしています。
http://yamad07.net
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away