I-14-10. アルゴリズム

用途に応じたデータ構造の使い方を説明し、それぞれのデータ構造を使用した代表的なアルゴリズムや効果的な利用方法を紹介する。

【学習の要点】

* データ構造は、用途によって使い分けることで、効率的なアルゴリズムを実行することができる。

図I-14-10. 二分探索木のデータ構造

【解説】

1) 用途に応じたデータ構造の使い方

* テスト結果のリストを点数順にして作りたい時など、リストに挿入、削除を頻繁に行いたい場合

線形リストが使える。もしこのリストに配列を使ったとしたら、リストの途中に挿入を行うと、その挿入を行った場所より後のデータも並びなおさなければならないが、線形リストだとポインタのつながり方を直すだけで済み、挿入した場所よりも後ろのデータの並び替えをする必要がない。これにより、データを作る時点で点数順に並べたリストを作ることができる。

* 辞書を作ってそれを活用したい時など、データの検索を頻繁に行いたい場合

二分探索木が使える。各ノードに一つ単語を割り当て、ノードを追加する際に後述する規則を守ることで、検索する際にその規則を利用して検索することができるので、線形検索よりも早く検索することができる。

2) 代表的なアルゴリズム

ここでは、例として二分探索木を用いて辞書を作るアルゴリズムを紹介する。

* 二分探索木とは

二分探索木とは、ツリー状のデータ構造の一種である。ツリー状のデータ構造では、ルートノードから枝分かれしていく構造をとり、あるノードから枝分かれした先のノードをそのノードの子ノードと呼び、そのノードは子ノードからみた親ノードという。ツリー構造では、ルートを除く各ノードにおいて親ノードは1つのみ存在する。二分木では、各ノードが最大2つまで子ノードを持つことができる。その2つの子は、右の子、左の子と呼ぶ。この二分探索木では、「左の子ノード≦自ノード<右の子ノード」という条件を満たしている必要がある。

* 二分探索木にデータを追加するアルゴリズム

二分探索木にデータを追加する場合は、まず対象ノードをルートノードに位置づけ、以下の処理を繰り返す。

- 対象ノードが存在しなければ、そこにノードを追加し、そのノードに追加すべき値を設定して終了する。

- 対象ノードの値と追加する値とを比較する。追加する値のほうが大きければ、対象ノードを右の子ノードに変更し、そうでなければ、対象ノードを左の子ノードに変更する。

* 二分探索木からデータを検索するアルゴリズム

二分探索木からデータを検索する場合は、まず対象ノードをルートノードに位置づけ、以下の処理を繰り返す。

- 対象ノードが存在しなければ、検索されなかったものとして終了する。

- 対象ノードの値と検索する値とを比較する。検索する値と一致すれば、検索されたものとして終了し、検索する値のほうが大きければ、対象ノードを右の子ノードに変更し、そうでなければ、対象ノードを左の子ノードに変更する。

OSS Course Naviのコンテンツは IPA OSS モデルカリキュラムを基としています。