探索木とは? わかりやすく解説

探索木

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/09/01 22:06 UTC 版)

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

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

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

探索木の種類

二分探索木

二分探索木

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

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

B木

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

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

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

a-b木

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

a と b は以下の数式を満たす必要がある[2]

カテゴリ


探索木

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/05/15 07:59 UTC 版)

2-3 フィンガーツリー」の記事における「探索木」の解説

探索木を実装する場合関数measureはその部分木が含む最後キー返す。そして木にキーkを挿入する際は、木をkより小さ部分とk以上の部分分割しその間にkを入れて連結する。するとキー昇順に並ぶようになり、平衡探索木を実装できる。

※この「探索木」の解説は、「2-3 フィンガーツリー」の解説の一部です。
「探索木」を含む「2-3 フィンガーツリー」の記事については、「2-3 フィンガーツリー」の概要を参照ください。

ウィキペディア小見出し辞書の「探索木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



探索木と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「探索木」の関連用語











探索木のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



探索木のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの探索木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの2-3 フィンガーツリー (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS