Loading article…
コンピュータサイエンスにおいて、探索木は、集合内から特定のキーを見つけるために使用される木構造のデータです。木が探索木として機能するためには、各ノードのキーは、左側のサブツリーのどのキーよりも大きく、右側のサブツリーのどのキーよりも小さくなければなりません。[1]
検索ツリーの利点は、ツリーが適度にバランスが取れている場合、つまり両端の葉の深さが同程度である場合に、検索時間が効率的になることです。検索ツリーのデータ構造にはさまざまなものがあり、そのうちのいくつかは要素の効率的な挿入と削除も可能にし、その操作によってツリーのバランスを維持する必要があります。
検索ツリーは、連想配列を実装するためによく使用されます。検索ツリー アルゴリズムは、キーと値のペアのキーを使用して場所を検索し、アプリケーションはキーと値のペア全体をその特定の場所に格納します。
木の種類
二分探索木
バイナリ検索ツリーは、各ノードにキーと 2 つのサブツリー (左と右) が含まれるノードベースのデータ構造です。すべてのノードについて、左のサブツリーのキーはノードのキーより小さく、右のサブツリーのキーはノードのキーより大きくなければなりません。これらのサブツリーはすべてバイナリ検索ツリーとして適格である必要があります。
二分探索木を検索するための最悪の時間計算量は木の高さであり、n 個の要素を持つ木の場合は O(log n) ほど小さくなることがあります。
Bツリー
B ツリーは、各ノードに可変数のサブツリーを持つことができるという点で、バイナリ検索ツリーを一般化したものです。子ノードには事前に定義された範囲がありますが、必ずしもデータで埋められるわけではありません。つまり、B ツリーはいくらかのスペースを無駄にする可能性があります。B ツリーの利点は、他の自己バランス ツリーほど頻繁に再バランス調整する必要がないことです。
B ツリーはノード長の範囲が可変であるため、大きなデータ ブロックを読み取るシステムに最適化されており、データベースでもよく使用されます。
B ツリーの検索にかかる時間の計算量は O(log n) です。
(a,b)-木
(a,b) ツリーは、すべてのリーフが同じ深さである検索ツリーです。各ノードには少なくともa 個の子と最大でb 個の子があり、ルートには少なくとも 2 個の子と最大でb個の子があります。
aとbは次の式で決定できる：[2]
(a,b)-ツリーの検索にかかる時間計算量は O(log n) です。
三項探索木
三分探索木は、下位の子、同等の子、上位の子の 3 つのノードを持つことができる木の一種です。各ノードには 1 つの文字が格納され、木自体は、3 番目のノードが存在する可能性を除いて、二分探索木と同じように順序付けられます。
三項検索ツリーを検索するには、文字列を渡して、パスに文字列が含まれているかどうかをテストする必要があります。
バランスのとれた三分探索木を検索するための時間計算量は O(log n) です。
検索アルゴリズム
特定のキーを検索する
ツリーが順序付けられていると仮定すると、キーを取得してツリー内でそのキーを見つけようとすることができます。次のアルゴリズムはバイナリ検索ツリー用に一般化されていますが、同じ考え方を他の形式のツリーに適用できます。
再帰的
search-recursive(key, node)
ノードがNULLの場合、キー < node.keyの場合はEMPTY_TREEを返す
検索再帰(キー、ノード.left)を返す
そうでない場合、キー > node.key
検索再帰(キー、ノード右)を返す
そうでなければ
ノードを
返す
反復的
searchIterative(キー、ノード)
現在のノード:=ノード
currentNode がNULLでない
場合、 currentNode.key = key の
場合はcurrentNode
を返し、そうでない場合はcurrentNode.key > keyの場合
現在のノード:=現在のノード.左
それ以外
現在のノード:=現在のノード.right
最小値と最大値の検索
ソートされた木では、最小値は最も左のノードに配置され、最大値は最も右のノードに配置されます。[3]
最小
findMinimum(node)
ノードがNULLの場合はEMPTY_TREEを返す
最小 := ノード
min.leftがNULLではない場合
最小 := 最小左
min.keyを
返す
最大
findMaximum(node)
ノードがNULLの場合はEMPTY_TREEを返す
最大 := ノード
max.right がNULLではない場合
最大 := 最大右
最大キー
を返す
参照
参考文献
- ^ Black, Paul および Pieterse, Vreda (2005)。「検索ツリー」。アルゴリズムとデータ構造の辞書
- ^ トール、レイ。「(a,b) 木」
- ^ ダン、ギルデア (2004)。 「二分探索木」