前回の記事でアルゴリズムってどんなものなのか、という基本的な部分をまとめました。
今回は実際にどんなアルゴリズムやデータ構造があるのかを見ていこうとおもいます。
前回の記事はこちらになります。
探索アルゴリズム
線形探索
代表的な検索アルゴリズムに線形探索があります。
このアルゴリズムはどんなときに使われるかというと、例えばこんな例を考えてみましょう。
7, 4, 9, 10 , 2, 3, 8, 5, 11
上記の数字から一番小さい数字を見つけてください、という探索アルゴリズムを考えるとしましょう。
線形探索というのは左から1個1個みていく、という至って超シンプルなアルゴリズムです。
つまり、7と4を比較して4のほうが小さい。4と9を比較して4の方が小さい。…というふうにやっていくのが線形探索です。
ですが、このデータ数が増えていくとかなり処理に時間がかかってしまいますよね。
そこで登場するのが二分探索(バイナリーサーチ)なんです。
二分探索(バイナリーサーチ)
7, 4, 9, 10 , 2, 3, 8, 5, 11
先ほどの数字を使って考えてみましょう。今度は5より大きい数字を見つけてください、というアルゴリズムを作成しようと考えます。
そのときに使えるのが、二分探索(バイナリーサーチ)です。
二分探索(バイナリーサーチ)とは、名前の通り、2つに分けて探索することを言います。
今回の例でいえば、まず数字を昇順もしくは降順で並び替えます。そして、ちょうど真ん中で区切るようにするんです。
例と数字は違いますが、イメージは以下の画像のような感じです。
※https://ufcpp.net/study/dotnet/bcl_collection_algorithm.html から引用しています。
このように中央の値から考えて探したい値が大きいか小さいかを考えるんです。今回の例でいえば、
2, 3, 4, 5, 7, 8, 9, 10, 11
このように昇順で並び替え、中央値である7を基準にして解決したい内容を考えるんです。
5より大きい数字が欲しければ、中央値の7の隣にいるのが５ですから、それ以降を抽出してあげればいいということになります。
ですが、この探索方法はソートされてないデータを扱うことができないのが、この探索方法のデメリットです。
データ構造
これまで探索アルゴリズムを見てきましたが、より効率よいアルゴリズムを組むためにはデータをどう格納するべきか、という観点も大事になってきます。データをどう格納するべきかというのをデータ構造といいます。
このデータ構造の基本が木構造というものです。
木構造
木構造とは以下の画像のことを言います。
※https://e-words.jp/w/%E6%9C%A8%E6%A7%8B%E9%80%A0.html より引用
丸の部分をノードといい、頂点にあるノードをルートノード、子ノードを持たないノードをリーフノードといいます。
木構造には多くの種類があって、子ノードの数が2つに制限されているものを二分木といい、それ以上の数に制限されているものを、N分木といいます。
二分木探索
二分木のうち、左側のノードの値が必ず親よりも小さく、右側のノードの値が必ず親よりも大きくなっているものを二分木探索といいます。
具体的にいうと、以下の画像のようなものです。
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8 参照
二分木探索で例えば、7をみつけたいとします。まず初めに、8から始めて、7の方が8よりも小さいので、左側である3に行きます。その次に、3と7を比較して、7の方が大きいので右に行って...というふうにしていくことで欲しいデータが取れるようになるんです。
これのメリットは今回でいえば、最大処理回数が4回で済むということです。つまり、効率よくデータを探すことができるようになるんです。
AVL木
木構造を考えるときに注意すべきポイントは、木の高さを一定にすることが大事です。
例えば以下の木構造のような場合を考えてみましょう。
※https://www.google.com/url?sa=i&url=https%3A%2F%2Fatmarkit.itmedia.co.jp%2Ffcoding%2Farticles%2Fdelphi%2F03%2Fdelphi03a.html&psig=AOvVaw28G28jEJIFsYHppqdcuRuK&ust=1648953247275000&source=images&cd=vfe&ved=2ahUKEwiv7drVq_T2AhVAwIsBHXt9BrkQr4kDegUIARCzAQ より引用
こうすると、最大処理回数が、欲しい値によって変わってしまうということがあります。
そこ
B木
B木とは1つのノードが3つ以上のノードを持っていて、木の高さが一定である木のことを言います。
図解するのがむずかしかったので、こちらの記事が参考になりますので、こちらを参考にしてみてください。
ちなみにぼくらが何気なく使っているドメインも実は木構造のデータ構造をしています。
以上です。何か間違いがございましたら、ご教示いただけますと幸いです。