探索木 - 暇つぶしWikipedia

探索木

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

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

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

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

2 ≤ a ≤ ( b + 1 ) 2 {\displaystyle 2\leq a\leq {\frac {(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
最大・最小要素の検索

順序付きの木であれば、最小の要素は最も左のノードであり、最大の要素は最も右のノードである [3]。
最小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
関連項目

 トライ木

 二分探索木

 深さ優先探索

 参考文献 ^ Black, Paul and Pieterse, Vreda (2005). "search tree". ⇒Dictionary of Algorithms and Data Structures
^ Toal, Ray. ⇒"(a,b) Trees"
^ Gildea, Dan (2004). ⇒"Binary Search Tree"