データ構造とアルゴリズム
ソートアルゴリズムやグラフ、連結リストなどがこの分野の中でよく扱われます。
今回はこの分野の中の、木構造の代表例である、バイナリツリーを扱います。
バイナリツリーとは
バイナリツリーとは、一つのノードが最大で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)
}
実際に呼び出してみると、ちゃんと最大値が出力されていることがわかります。
全てのコードはこちらに上がっているので、ご参照ください。
まとめ
今回は、バイナリツリーを実装し、木構造の概念についての理解を深めました。
時間があるときに、もっといろんな種類のデータ構造を実装してみようと思います。