2分探索木

IT用語辞典バイナリ

2分探索木

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

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

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

情報処理のほかの用語一覧

アルゴリズム：

ソート  スタック  2分木  2分探索木  2分探索法  探索法  単純挿入法

>>アルゴリズムカテゴリの他の用語

ウィキペディア

二分探索木

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

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