探索木

探索木とは、計算機科学において特定のキーを特定するために使用される木構造である。その木構造が探索木として機能するために、あるノードのキーは、そのノードの左の子ノードのキーよりは常に大きく、逆に右の子ノードのキーよりは常に小さい性質が必要である。

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

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

探索木の種類

二分探索木 
二分探索木はノードベースのデータ構造であり、各ノードは左右で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 は以下の数式を満たす必要がある。

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

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

参考文献 

検索アルゴリズム
ツリー (データ構造)
ソート