探索木のソースを表示

'''探索木'''（たんさくぎ、{{lang-en-short|search tree}}）とは、[[計算機科学]]において特定のキーを特定するために使用される[[木構造 (データ構造)|木構造]]である。その木構造が探索木として機能するために、あるノードのキーは、そのノードの左の子ノードのキーよりは常に大きく、逆に右の子ノードのキーよりは常に小さい性質が必要である<ref>Black, Paul and Pieterse, Vreda (2005). [https://xlinux.nist.gov/dads/HTML/searchtree.html "search tree"]. [http://xlinux.nist.gov/dads// Dictionary of Algorithms and Data Structures]</ref>。

探索木はその木構造が[[平衡木|平衡]]（全ての葉ノードまでの深さがほぼ等しい状態）である場合に、効率的にそのキーを探索できるという利点を持つ。様々な種類の探索木が存在し、その幾つかは常に平衡を保つことによってキーを効率的に挿入・削除することが可能である。

探索木は、[[連想配列]]の実装によく用いられる。探索木アルゴリズムはキーと値のペア（キーバリューペア）のキーを用いて位置を特定し、アプリケーションはキーに対応する値をその位置に保管する。

== 探索木の種類 ==
[[ファイル:Binary_search_tree.svg|代替文=Binary search tree|サムネイル|[[二分探索木]]]]

=== 二分探索木 ===
二分探索木はノードベースの[[データ構造]]であり、各ノードは左右で2つの部分木を持つ。そして各ノードは「左の部分木の値 < ノードの値 < 右の部分木の値」を満たす。そして左右の部分木の親ノードも上の条件を満たすため、左右の部分木は共に二分探索木である。

二分探索木のノードの検索にかかる計算は木の深さであるため、''n ''個の要素を持つ二分探索木でノードの検索を行うと O(log ''n'')程度の時間がかかる。ただし、最悪の場合には深さは ''n'' になるため、検索時間もO(''n'')となる。このような場合を防ぐために、平衡を保つような工夫が行われる。

=== B木 ===
[[B木]]は二分探索木をより一般化した、多分岐の探索木である。それぞれの子である部分木は、「左のキー < 部分木の親ノードのキー < 右のキー」を満たすように配置される。多分岐であるため、全てのキーに値が格納されているとは限らない。そのため、B木は多少容量を無駄に消費する。B木の利点は、他の平衡木と比べて平衡を保つための処理を行う頻度が低い点である。

ノードの長さは可変であるため、B木は大きなデータを読み取るシステムに最適である。そのため、データ管理システムによく使われる。

B木の検索時間は O(log ''n'')である。

=== a-b木 ===
a-b木は全てのはノードの深さが等しい探索木である。各ノードは ''a ''個以上 ''b ''個以下の子ノードを持ち、根ノードは2個以上 ''b ''個以下の子ノードを持つ。

'''''a''''' と '''''b''''' は以下の数式を満たす必要がある<ref>Toal, Ray. [http://cs.lmu.edu/~ray/notes/abtrees/ "(a,b) Trees"]</ref>。

<math>2 \le a \le \frac{(b+1)}{2}</math>

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

=== 最大・最小要素の検索 ===
順序付きの木であれば、最小の要素は最も左のノードであり、最大の要素は最も右のノードである<ref>Gildea, Dan (2004). [http://www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf "Binary Search Tree"]</ref>。

==== 最小 ====
 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

== 関連項目 ==
* [[トライ木]]
* [[二分探索木]]
* [[深さ優先探索]]

== 参考文献 ==
{{Reflist}}
{{データ構造}}

{{Normdaten}}
{{デフォルトソート:たんさくき}}
[[Category:探索木|*]]
[[Category:検索アルゴリズム]]
[[Category:ツリー (データ構造)]]
[[Category:ソート]]