データ構造を工夫する

より速く結果を求めるには、元のデータの並びを変更する必要があります。人間が普通の生活で考えることはまずありませんが、コンピュータで効率的な処理を行わせるには、探索対象となるデータのありかた――データ構造を組み直します。

より速い探索処理の仕掛け

最もシンプルな逐次探索では最低1回、最大で要素数分（上の例では7回）の比較で値を見つけ出せます。一見合理的なようですが、比較先の値が何千～何万となったら、場合によっては非常に時間がかかってしまいます。

「比較対象が多くなれば、それは仕方がないのじゃないか」と、考えることもできます。しかし、比較対象が極端に多くなった場合でも、処理をできる限り短くすることができます。

そのためには、比較対象を単純な配列としないで、少し仕掛けを施す必要が生じます。先ほどと同じ7個の整数で、その仕掛けを作ってみましょう。

TOP

元のデータを組み替える

まず、先頭の値を取り出します。この場合は「3」です。

次に、2番目の値を取り出して先頭の値と比較し、先頭の値より小さければ左、大きければ右に配置します（図2）。

続いて3番目の値を取り出し、先頭の値より先頭の値より小さければ左、大きければ右に配置します（図3）。

4番目の値を取り出し、先頭の値より小さければ左、大きければ右に配置します。すると、この場合は値7が3の右にある6と出合います。ここで、同じように出合った値より小さければその左、大きければその右に配置します（図4）。

以降、同じようにして値を順番に取り出しては先頭と比較して左右どちらかに割り振り、そこに値が存在すれば、また同じように大小関係に従ってその左右に割り振る……という動作を、比較先の値がなくなるまで繰り返します。すると、図5のような構造が出来上がります。

図2：手順1

図3：手順2

図4：手順3

図5：最終的な構造

TOP

データ構造を工夫する

こうして出来上がった、一見モービルのような形を「二分探索木」と呼びます。ぶら下がっている各要素を「ノード(node)」と言い、先頭のノード（値は3）から左へ左へとたどっていけばより小さい値へと進み、逆に右へ右へとたどっていけばより大きい値へと進むようになっています。

ここから「4」を見付けるには、以下のような処理を行います。

先頭の値「3」と探索する値「4」とを比較する
→　「4」の方が大きいので右へ進む
右の値「6」と探索する値「4」とを比較する
→　「4」の方が小さいので左へ進む
「4」が見付かる

このように二分探索木では、先頭のノードから大小関係に従って右または左に構造をたどっていけば、目指す値を見付けることができます。先頭の値にもよりますが、探索対象の値が左右に分かれるため、単純な逐次探索に比べて比較する回数がおよそ半分になります。

TOP

NEXT PAGE >>

【質問１】コラムをどれくらい読みましたか？

熟読した途中でやめたさっと目を通した印刷してこれから読む

【質問２】役に立つ内容でしたか？

参考になった参考にならなかった

ご自由にコメントを記入してください