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

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

バイナリツリーとは

バイナリツリーとは、一つのノードが最大で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)
}

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

まとめ

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