問題
二分探索木において、最も小さい要素を取り出すための走査方向として、正しいものはどれか。
選択肢
- 1根から右へ右へとたどる
- 2根から左へ左へとたどる
- 3幅優先探索
- 4深さ優先で全探索
正解
2. 根から左へ左へとたどる
詳しい解説を見る解説を閉じる
解説
二分探索木は「左部分木の全ノード<自ノード<右部分木の全ノード」という性質を持ちます。したがって最小値は根から左の子へ左へと辿った末端（左端の葉）に存在します。逆に最大値は右端にあります。この性質によりin-order（中順）走査でソート済みの要素列が得られます。平衡が崩れると最悪O(n)になるため、AVL木や赤黒木で平衡を保つ手法が利用されます。
一問一答
全400問を繰り返し学習