binary search treeとは? わかりやすく解説

Weblio 辞書 > コンピュータ > IT用語辞典 > binary search treeの意味・解説 

2分探索木

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

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

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

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

二分探索木

(binary search tree から転送)

出典: フリー百科事典『ウィキペディア(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. 右の子をルートとする部分木に対して、この処理を再帰的に適用する。

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

関連項目


「binary search tree」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「binary search tree」の関連用語

binary search treeのお隣キーワード
検索ランキング

   

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



binary search treeのページの著作権
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の元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS