二分探索木とは
にぶんたんさくぎ
各節について、左の部分木の値はすべてその節より小さく、右の部分木の値はすべて大きくなるように値を置いた二分木。探索・挿入・削除は木の高さに比例する手間で済み、中間順(通りがけ順)にたどると値が昇順に並ぶ。
「二分探索木」は、1分野の4問の練習問題に出てきます(データ構造とアルゴリズムなど)。
この用語の分野: データ構造とアルゴリズム
探索・挿入・削除
探索は根から始め、探す値が節より小さければ左、大きければ右の子へ進み、一致するか子がなくなるまで繰り返します。挿入は、探索して子がなくなった位置に新しい節を付けます。削除は、子が0個か1個ならその節を取り除いて子をつなぎ直し、子が2個なら、右の部分木の最小値(または左の部分木の最大値)で置き換えてから、その節を削除します。どの操作も、根から葉までの段の数(木の高さ)に比例する手間です。
偏った木と平衡二分探索木
n 個の節を持つ二分探索木の高さは、つり合いがとれていれば約 log₂ n ですが、1, 2, 3, … のように整列済みの順に挿入すると、片側にだけ伸びた1本の列になり、高さは n−1 になります。こうなると探索は連結リストと同じ O(n) です。AVL木や赤黒木は、挿入や削除のたびに回転という操作で形を整え、高さを O(log n) に保つ平衡二分探索木で、多くのプログラミング言語の順序付きの辞書やセットに使われています。
たどり方の種類
木のすべての節を訪れる方法には、節を先に訪れる先行順(行きがけ順)、左の部分木、節、右の部分木の順の中間順(通りがけ順)、子を先に訪れる後行順(帰りがけ順)があり、段ごとに訪れる幅優先(レベル順)もあります。二分探索木を中間順でたどると値が昇順に並ぶので、整列した一覧を得られます。式を表す木を後行順でたどると逆ポーランド記法になります。
二分探索木の練習問題に挑戦
二分探索木を中間順(通りがけ順。左の部分木、その節、右の部分木の順に訪れる)でたどったとき、訪れた節の値はどのように並ぶか。値はすべて異なるものとする。
- A昇順(小さい順)に並ぶ
- B木に挿入した順に並ぶ
- C根から近い順(浅い順)に並ぶ
答えと解説を見る
正解：A. 昇順(小さい順)に並ぶ
二分探索木では、どの節についても、左の部分木の値はすべてその節より小さく、右の部分木の値はすべて大きくなっています。そのため、左の部分木、節、右の部分木の順にたどると、小さい値から順に訪れることになり、結果は昇順になります。根から近い順に並ぶのは、段ごとに左から訪れる幅優先(レベル順)のたどり方です。挿入した順は木の形には残りますが、たどり方の順序とは一致しません。
空の二分探索木に、50, 30, 70, 20, 40, 60, 80 の順に値を挿入した。この木を後行順(帰りがけ順。左の部分木、右の部分木、その節の順に訪れる)でたどったときの順はどれか。
- A50, 30, 20, 40, 70, 60, 80
- B20, 40, 30, 60, 80, 70, 50
- C20, 30, 40, 50, 60, 70, 80
答えと解説を見る
正解：B. 20, 40, 30, 60, 80, 70, 50
根は50で、左の子は30(その子が20と40)、右の子は70(その子が60と80)になります。後行順では、左の部分木の 20, 40, 30、右の部分木の 60, 80, 70 を訪れてから、最後に根の50を訪れます。50, 30, 20, 40, 70, 60, 80 は節を先に訪れる先行順(行きがけ順)、20, 30, 40, … は中間順(通りがけ順)の結果です。後行順は、子を先に処理する必要がある木の削除や、式の木から後置記法を作るときに使われます。
よくある質問
二分探索木とヒープはどう違いますか?
二分探索木は「左は小さく右は大きい」という条件で、任意の値の探索や順番どおりの列挙ができます。二分ヒープは「親が子より大きい(または小さい)」という条件だけで、最大値(最小値)をすぐ取り出せますが、任意の値の探索には向きません。
二分探索木とB木はどう使い分けますか?
メモリ上で使うなら平衡二分探索木、ディスクやSSDのようにブロック単位で読む記憶装置では、1つの節に多数のキーを持たせて木を低くしたB木(B+木)が使われます。
解説の中の「二分探索木」
二分探索木では、どの節についても、左の部分木の値はすべてその節より小さく、右の部分木の値はすべて大きくなっています。
二分探索木を中間順(通りがけ順。左の部分木、その節、右の部分木の順に訪れる)でたどったとき、訪れた節の値はどのように並…つり合いのとれた木なら段の数は約 log₂ 1000 ≈ 10 なので、AVL木や赤黒木のように挿入や削除のたびに形を整える平衡二分探索木を使えば、最悪でも O(log n) を保てます。
空の二分探索木に、1, 2, 3, …, 1000 の順に値を挿入した(つり合いをとる操作はしない)。この木で1000…二分探索木では1億件なら少なくとも27段ほどになり、段ごとに別のブロックを読むと遅くなります。
データベースやファイルシステムの索引に、二分探索木ではなくB木(B+木を含む)がよく使われる主な理由はどれか。
「二分探索木」が出てくる問題(4問)
- 二分探索木を中間順(通りがけ順。左の部分木、その節、右の部分木の順に訪れる)でたどったとき、訪れた節の値はどのように並ぶか。値はすべて異なるものとする。
- 空の二分探索木に、50, 30, 70, 20, 40, 60, 80 の順に値を挿入した。この木を後行順(帰りがけ順。左の部分木、右の部分木、その節の順に訪れる)でたどったときの順はどれか。
- 空の二分探索木に、1, 2, 3, …, 1000 の順に値を挿入した(つり合いをとる操作はしない)。この木で1000を探すとき、根から比べ始めて、見つかるまでに比べる節の数はいくつか。
- データベースやファイルシステムの索引に、二分探索木ではなくB木(B+木を含む)がよく使われる主な理由はどれか。
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。