テクノロジ系 / アルゴリズムとプログラミング
2 分探索木
2分探索木は、各節点について左部分木に小さい値、右部分木に大きい値を置く二分木です。
もう少し詳しく
探索時は、現在の節点と探す値を比較し、小さければ左、大きければ右へ進みます。木が偏ると線形リストに近くなり、探索効率が悪化するため、AVL木などの平衡木が使われます。
試験での見方
例：根が50なら、30は左部分木、70は右部分木に入り、40を探すときは50→30→40のように進みます。
テクノロジ系 / アルゴリズムとプログラミング
2分探索木は、各節点について左部分木に小さい値、右部分木に大きい値を置く二分木です。
探索時は、現在の節点と探す値を比較し、小さければ左、大きければ右へ進みます。木が偏ると線形リストに近くなり、探索効率が悪化するため、AVL木などの平衡木が使われます。
例：根が50なら、30は左部分木、70は右部分木に入り、40を探すときは50→30→40のように進みます。
2分探索木では、節点の大小関係をたどって挿入・探索の経路を決めます。中間順に走査すると昇順になる点もよく確認されます。