[Golang]アルゴリズムにチャレンジ ~Binary Tree(二分木)を作成しよう!~

こんにちは。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(子)モデルが必要です。

Treeを構築する

Nodeを挿入する処理を実装して、Treeを構築します。

TreeのValueを確認する

TreeのValueを確認するprint処理を実装します。

Tree構造体のInsertメソッドの戻り値はTree構造体のため、上記のように数珠繋ぎにメソッドを連結できます。

プログラムを実装しましょう。

ちょとわかりずらい(しかも小さい順に出力されてる)のですが、Treeが保持する値を全て出力しました。

検索結果の確認

検索したい値を入力し、存在するか否かをチェックするメソッドを実装します。

プログラムを実行します。

OKですね。

おわりに

アルゴリズムは頭の体操になります。今回のようにSearch処理を自分の頭で考えると実務の場でも冴えた実装を思いついたりもします。

また、ポインタや構造体の使い方もより深く知ることができますよね^^

シンプルで無駄のないプログラムを組めるようにがんばりましょう!

それでは、また!

Go記事まとめ

アルゴリズムまとめ

Go記事をまとめます。

ソースコード

コメントを残す