こんにちは。KOUKIです。
とあるWeb系企業で、Goエンジニアをやっています。
今回は、Binary Treeの実装を通じて、アルゴリズムを勉強しましょう。
<目次>
Binary Tree(二分木)について
Binary TreeはTree構造体と呼ばれており、「1つの親に対して複数の子を持つ、枝分かれして広がっていく構造」です。
下記の画像を見てください。
起点である「2」の数値からTree上に形成されています。Binary TreeはこのTreeの中から検索したい値を「最短」で見つけるアルゴリズムです。
例えば、「6」という数値をこのTreeの中から検索したい場合、まず起点となる2から検索が始まります。2では「7」と「5」の2つの子を持ち、検索対象の6とどちらが大きいか判定します。
7の方が大きいので検索は7の方へ向かい、その子である「2」及び「6」を検索し、最終的に6を見つけるというロジックです。
このようなアルゴリズムを実装します。
モデルの実装
今回は、TreeとNode(子)モデルが必要です。
|
1 2 3 4 5 6 7 8 9 |
type Tree struct { node *Node } type Node struct { value int left *Node right *Node } |
Treeを構築する
Nodeを挿入する処理を実装して、Treeを構築します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
func (t *Tree) insert(value int) *Tree { if t.node == nil { t.node = &Node{value: value} } else { t.node.insert(value) } return t } func (n *Node) insert(value int) { if n.value >= value { if n.left == nil { n.left = &Node{value: value} } else { n.left.insert(value) } } else { if n.right == nil { n.right = &Node{value: value} } else { n.right.insert(value) } } } |
TreeのValueを確認する
TreeのValueを確認するprint処理を実装します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
func printNode(n *Node) { if n == nil { return } fmt.Println("value", n.value) printNode(n.left) printNode(n.right) } func main() { t := &Tree{} t.insert(2). insert(7). insert(5). insert(2). insert(6). insert(5). insert(11). insert(5). insert(9). insert(4) printNode(t.node) } |
Tree構造体のInsertメソッドの戻り値はTree構造体のため、上記のように数珠繋ぎにメソッドを連結できます。
プログラムを実装しましょう。
|
1 2 3 4 5 6 7 8 9 10 11 |
$ go run main.go value 2 value 2 value 7 value 5 value 5 value 5 value 4 value 6 value 11 value 9 |
ちょとわかりずらい(しかも小さい順に出力されてる)のですが、Treeが保持する値を全て出力しました。
検索結果の確認
検索したい値を入力し、存在するか否かをチェックするメソッドを実装します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
func (n *Node) exists(value int) bool { if n == nil { return false } if n.value == value { return true } if n.value >= value { return n.left.exists(value) } else { return n.right.exists(value) } } func main() { ... fmt.Println("Is there 0?: ", t.node.exists(0)) fmt.Println("Is there 9?", t.node.exists(9)) fmt.Println("Is there 11?", t.node.exists(11)) fmt.Println("Is there 99?", t.node.exists(99)) } |
プログラムを実行します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
$ go run binary-search/main.go value 2 value 2 value 7 value 5 value 5 value 5 value 4 value 6 value 11 value 9 Is there 0?: false Is there 9? true Is there 11? true Is there 99? false |
OKですね。
おわりに
アルゴリズムは頭の体操になります。今回のようにSearch処理を自分の頭で考えると実務の場でも冴えた実装を思いついたりもします。
また、ポインタや構造体の使い方もより深く知ることができますよね^^
シンプルで無駄のないプログラムを組めるようにがんばりましょう!
それでは、また!
Go記事まとめ
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
package main import "fmt" type Tree struct { node *Node } func (t *Tree) insert(value int) *Tree { if t.node == nil { t.node = &Node{value: value} } else { t.node.insert(value) } return t } type Node struct { value int left *Node right *Node } func (n *Node) insert(value int) { if n.value >= value { if n.left == nil { n.left = &Node{value: value} } else { n.left.insert(value) } } else { if n.right == nil { n.right = &Node{value: value} } else { n.right.insert(value) } } } func printNode(n *Node) { if n == nil { return } fmt.Println("value", n.value) printNode(n.left) printNode(n.right) } func (n *Node) exists(value int) bool { if n == nil { return false } if n.value == value { return true } if n.value >= value { return n.left.exists(value) } else { return n.right.exists(value) } } func main() { t := &Tree{} t.insert(2). insert(7). insert(5). insert(2). insert(6). insert(5). insert(11). insert(5). insert(9). insert(4) printNode(t.node) fmt.Println("Is there 0?: ", t.node.exists(0)) fmt.Println("Is there 9?", t.node.exists(9)) fmt.Println("Is there 11?", t.node.exists(11)) fmt.Println("Is there 99?", t.node.exists(99)) } |
にほんブログ村
[…] /* [Golang]アルゴリズムにチャレンジ ~Binary Tree(二分木)を作成しよう!~ */ package main import ( "fmt" ) type Tree struct { node *Node } type Node struct { value int left *Node right *Node } func (t *Tree) insert(value int) *Tree […]