IT用語辞典バイナリ

2分探索木

読み方：にぶんたんさくき
【英】binary search tree

2分探索木とは、木構造の一種で、各節点において常に左の子より右の子が大きい（または小さい）という関係が成り立っている2分木のことである。

2分探索木は、データを高速に検索するための木構造であるが、作成データの並びによっては素朴な方法で2分検索木を作ると、線形リストとほとんど変わらなくなり効果が出ないことがある。これを回避するためには、バランスが取れたと木構造なるように2分探索木を作成する必要がある。

例えば、赤黒木は2分探索木の中でも木の作成が平均的に速く行え、検索にも適していることが知られている。

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

アルゴリズム：

ソート  スタック  2分木  2分探索木  2分探索法  探索法  ド・モルガンの法則

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