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

Weblio 辞書 > コンピュータ > IT用語辞典 > 二分探索木の意味・解説 

2分探索木

読み方にぶんたんさくぎ
別名:二分探索木
【英】binary search tree

2分探索木とは、木構造探索木のうち、ノード子ノードそれぞれ振られた値が「左の子の値は親ノードの値よりも小さい」および「右の子の値は親ノードの値よりも大きい」という関係になっている、すなわち「左の子親ノード < 右の子」という関係が成り立っている探索木のことである。

2分探索木では、あるノードに対しての子および以下の全ての子孫ノードの値は元のノードの値よりも小さく逆に、右の子およびそれ以下全ての子孫ノードは、元のノードの値よりも大きいという関係が成り立つ。親と同じ値が含まれる場合には、左の子と右の子どちらか含めるかをあらかじめ決めておく必要がある

情報処理のほかの用語一覧
アルゴリズム:  ソート  スタック  2分木  2分探索木  2分探索法  探索法  単純挿入法

二分探索木

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/03/28 02:28 UTC 版)

二分探索木

二分探索木(にぶんたんさくぎ、: binary search tree)は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。

構造

構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。

平衡(左右のバランスがとれている状態)している状態では木の高さは log2 N となる。ただし最悪の場合は、事実上の 線形リスト になり、木の高さは N となる。木の形は挿入時のデータ出現順序に依存し、特にソート済みのデータを与えると線形リストになる点は注意を要する。データの出現順序によって大きく性能が劣化しないように、挿入・削除の際に木の平衡を取り直す処理を追加した二分探索木は平衡二分探索木と呼ばれる。

操作

探索

  1. ルートから手順を開始する。
  2. 着目しているノードと目的の値を比較する。等しいか、着目ノードが存在しなければ終了。
  3. 「目的の値 < 着目しているノード」なら左の子、「着目しているノード < 目的の値」なら右の子へ移って繰り返し。

探索の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。

挿入

同値のデータが出現した場合は右の子として登録するという前提で手順を記す。

  1. ルートから手順を開始する。
  2. 着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次の着目ノードとなる。
  3. 次の着目ノードが存在しなければ(現在の着目ノードが葉であれば)、次の着目ノードの位置にデータを挿入。存在すれば、次の着目ノードに移って繰り返し。

挿入の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。

削除

探索、挿入に比べると、削除の処理は少し複雑な手順となる。

二分探索木から根(7)を削除する例。左の子の最大値と置き換える場合は左の図のようになり、右の子の最小値と置き換える場合は右の図のようになる。
  1. ルートから手順を開始する。
  2. 着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次に着目するノードとなる。
  3. 着目ノードが削除する対象(以下、削除ノード)であり、削除ノードが子どもを持たないなら、そのノードをそのまま削除する。
  4. 削除ノードが子を一つしかもっていない場合は、削除ノードを削除してその子と置き換える。
  5. 削除ノードが子を二つ持つ場合
    1. 削除ノードの左の子から最大の値を探索する。
    2. 1 で探索してきたノード(以下、探索ノード)を削除対象のノードと置き換えて、削除対象のノードを削除する。このとき探索ノードの左の子を探索ノードの元位置に置き換える(二分探索木の性質上、探索ノードには右の子は無い)。

5-1 で行う操作は「右の子から最小の値を探索する」でも良い。この場合は 5-2 の操作は探索ノードの右の子を探索ノードの元位置に置き換えることになる。

全データの列挙

以下のように 再帰呼び出し を使うことで、二分探索木に登録された全データをソートされた順序で列挙できる。

  1. 左の子をルートとする部分木に対して、この処理を再帰的に適用する。
  2. 親を表示する。
  3. 右の子をルートとする部分木に対して、この処理を再帰的に適用する。

挿入時に、同値の値を右の子に登録しておけば、安定ソート となる。

関連項目


二分探索木

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

探索木」の記事における「二分探索木」の解説

二分探索木はノードベースのデータ構造であり、各ノード左右2つ部分木を持つ。そして各ノードは「左の部分木の値 < ノードの値 < 右の部分木の値」を満たす。そして左右部分木の親ノード上の条件を満たすため、左右部分木は共に二分探索木である。 二分探索木のノード検索にかかる計算は木の深さであるため、n 個の要素を持つ二分探索木でノード検索を行うと O(log n)程度時間がかかる。ただし、最悪場合には深さは n になるため、検索時間もO(n)となる。このような場合を防ぐために、平衡を保つような工夫が行われる。

※この「二分探索木」の解説は、「探索木」の解説の一部です。
「二分探索木」を含む「探索木」の記事については、「探索木」の概要を参照ください。

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


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

辞書ショートカット

すべての辞書の索引

「二分探索木」の関連用語

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

   

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



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

   
IT用語辞典バイナリIT用語辞典バイナリ
Copyright © 2005-2025 Weblio 辞書 IT用語辞典バイナリさくいん。 この記事は、IT用語辞典バイナリの【2分探索木】の記事を利用しております。
ウィキペディアウィキペディア
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の探索木 (改訂履歴)、二分木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS