探索木

探索木とは

探索木とは、コンピュータサイエンスにおいて、特定のキーを効率的に見つけ出すために使用される木構造のデータ構造です。探索木は、各ノードがキーを持ち、そのキーに基づいてデータを整理することで、高速な検索を実現します。

探索木の基本性質

探索木として機能するためには、以下の性質を満たす必要があります。

ノードのキーの順序: あるノードのキーは、そのノードの左の子ノードのキーよりも大きく、右の子ノードのキーよりも小さい。

この性質により、目的のキーを効率的に見つけることができます。

探索木の利点

探索木は、特に木構造が平衡状態（すべての葉ノードまでの深さがほぼ等しい状態）である場合に、その性能を最大限に発揮します。平衡状態を保つことで、キーの検索、挿入、削除といった操作を効率的に行うことができます。

探索木は連想配列の実装によく利用されます。連想配列では、キーと値のペア（キーバリューペア）を管理しますが、探索木はそのキーを用いてデータの場所を特定し、対応する値を格納するために使用されます。

様々な探索木の種類

探索木には様々な種類が存在します。ここでは、代表的な探索木について解説します。

二分探索木

二分探索木は、各ノードが最大で2つの子ノード（左の子ノードと右の子ノード）を持つ木構造です。二分探索木は、以下の条件を満たします。

ノードの順序: 全てのノードにおいて、左の子ノードの値 < 親ノードの値 < 右の子ノードの値
部分木: 左の部分木も右の部分木も、それぞれ二分探索木である

二分探索木での検索時間は、木の深さに依存します。平均的にはO(log n)の時間がかかりますが、最悪の場合（木が偏っている場合）はO(n)になります。そのため、平衡を保つための工夫が重要になります。

B木

B木は、二分探索木を一般化した多分岐の探索木です。各ノードは複数の子ノードを持つことができ、以下の条件を満たします。

ノードの順序: 左のキー < 部分木の親ノードのキー < 右のキー

B木は、必ずしも全てのキーに値が格納されているわけではありません。そのため、多少の容量を消費することがありますが、平衡を保つための処理頻度が低いという利点があります。B木は、特に大きなデータを扱うシステムに適しており、データベースシステムなどで広く利用されています。

B木での検索時間はO(log n)です。

a-b木

a-b木は、全ての葉ノードの深さが等しい探索木です。各ノードはa個以上b個以下の子ノードを持ち、根ノードは2個以上b個以下の子ノードを持ちます。aとbは以下の条件を満たす必要があります。

2 ≤ a ≤ (b + 1) / 2

a-b木での検索時間はO(log n)です。2-3木や2-3-4木（2-4木）はa-b木の一種です。

三分探索木

三分探索木は、トライ木の一種で、各ノードが最大で3つの子ノード（左、中央、右）を持つ探索木です。各ノードは1文字を格納し、二分探索木と同じように、順序を保ってデータを格納します。ただし、三分探索木は3つ目のノード（中央のノード）を持つことができます。

三分探索木での検索は、全てのパスに検索したい文字列が含まれているかどうかを検査することで行われます。平衡三分探索木の検索時間はO(log n)です。

探索アルゴリズム

探索木では、特定のキーを効率的に検索するためのアルゴリズムが用いられます。

特定のキーの検索

探索木が正しく構成されていれば、木に格納されたキーの位置を特定することができます。以下は、二分探索木を例にした再帰アルゴリズムと反復アルゴリズムです。

再帰アルゴリズム

search-recursive(key, node)
if node is NULL
return EMPTY_TREE
if key < node.key
return search-recursive(key, node.left)
else if key > node.key
return search-recursive(key, node.right)
else
return node

反復アルゴリズム

searchIterative(key, node)
currentNode := node
while currentNode is not NULL
if currentNode.key = key
return currentNode
else if currentNode.key > key
currentNode := currentNode.left
else
currentNode := currentNode.right

最大・最小要素の検索

順序付けされた探索木では、最小の要素は最も左のノードに、最大の要素は最も右のノードに位置します。

最小要素の検索

findMinimum(node)
if node is NULL
return EMPTY_TREE
min := node
while min.left is not NULL
min := min.left
return min.key

最大要素の検索

findMaximum(node)
if node is NULL
return EMPTY_TREE
max := node
while max.right is not NULL
max := max.right
return max.key

まとめ

探索木は、効率的なデータ検索を実現するための重要なデータ構造です。この記事で紹介したように、様々な種類の探索木が存在し、それぞれ特徴があります。これらの知識を理解することで、より効果的なデータ構造の選択と、アルゴリズムの設計に役立つでしょう。

関連項目

トライ木
二分探索木
深さ優先探索

参考文献

(参考文献に関する情報は、必要に応じて追記します)

もう一度検索