BST の最小値と最大値
BST の最小値と最大値
このレッスンで分かること
- BST には嬉しい性質があります
- 簡単な BST
[10, 5, 15, 3, 7, 13, 20]を考えます- 図のポイント (テキスト併記)
BST の最小値と最大値 とは
BST の最小値と最大値を返す関数を実装する。BST では最小は左端、最大は右端という性質を活かす。本レッスンでは、BST の最小値と最大値 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
BST には嬉しい性質があります。最小値は必ず一番左のノード(左の子を持たないノード)に、最大値は必ず一番右のノード(右の子を持たないノード)に存在することです。これは BST の不変条件「左の子 < 親 < 右の子」を全ノードで満たしているなら、ルートから左にひたすら進めば必ず最小値に到達するから。逆もまた然りで、ひたすら右に進めば最大値です。
本レッスンでは bstMinMax(arr) 関数を実装します。BFS 配列で表された BST を受け取り、[min, max] のような 2 要素の配列を返します。空木 ([]) の場合は空配列 [] を返すこととします。
BST における最小・最大の探索は
O(h)。hは木の高さ。バランスが取れた木ならlog n回の比較で終わる。
なぜ左端 / 右端なのか
簡単な BST [10, 5, 15, 3, 7, 13, 20] を考えます。
図のポイント (テキスト併記)
10から左に進むと53で行き止まり
10 から左に進むと 5 3 で行き止まり。3 には左の子がないので、これ以下の値は木の中に存在しません。よって最小は 3。同じ理屈で右端は 20 で、これ以上はないので最大は 20 です。
計算量と実装
左端 / 右端を求めるアルゴリズムは超シンプルです。左の子 が存在する限り左に進み、なくなったらそれが最小。最大も同様。コードに落とすと次のようになります。
Python
def findMin(node):
while node.left is not None:
node = node.left
return node.valPython
def findMax(node):
while node.right is not None:
node = node.right
return node.val2 つを組み合わせて、bstMinMax は [findMin(root), findMax(root)] を返す形になります。
反復版と再帰版
反復版は上の通り 3 行で書けます。再帰版を書くこともできます。
JavaScript
function findMin(node) {
if (node.left === null) return node.val;
return findMin(node.left);
}再帰で書くと宣言的で気持ちよく書けますが、何度も書いた通り 深い木 ではスタック溢れのリスクがあります。実務では反復版が定番です。
木が
平衡していれば再帰の深さはO(log n)。極端な偏りがあるとO(n)になり、1000を超えるあたりからスタックが危なくなる言語もある。
空木の扱い
BST が空 (ルートが null) の場合、最小も最大も存在しないので、ここでは空配列 [] を返します。実装では arr が空、または最初の要素が null のときに早期 return すれば OK です。
JavaScript での実装例
JavaScript
function bstMinMax(arr) {
const root = buildTree(arr);
if (root === null) return [];
let lo = root;
while (lo.left !== null) lo = lo.left;
let hi = root;
while (hi.right !== null) hi = hi.right;
return [lo.val, hi.val];
}buildTree は前のレッスンで作ったものを使い回します。lo hi という変数名で 小さい側 と 大きい側 を明示すると読みやすくなります。
よくある間違い
1 つ目は 空木の戻り値 を雑にしてしまうケース。null や undefined を返すとテストが落ちます。本問では空配列で明示してください。2 つ目は最小を探すときに 右 の子を見てしまうミス。左 の子だけを見て下に進みます。3 つ目は ルート自身が最小 / 最大 になるケースを見落とすこと。ルートに左の子がなければ、ルートの値そのものが最小です。
実務でどう使うか
bstMinMax のロジックは単独で出ることは少ないですが、削除 の中の in-order 後継 / 先行 を探す処理として頻繁に登場します。実際、削除 で「右部分木の最小」を探すのは、まさに本レッスンで書いた findMin 関数と同じ。TreeSet / SortedSet の first() / last() はこの考え方で実装されています。なお min-heap は根が常に最小値を保持する別アプローチであり、BST の findMin は使いません。BST の 自己平衡 版である TreeSet / SortedSet でも、first() / last() メソッドの実装はこの考え方で書かれています。
1 つのアルゴリズムが他の操作の
部品になる、というのはデータ構造の世界ではとてもよくあること。小さな知識を組み合わせて大きな問題を解く感覚を養おう。
やってみよう
[10, 5, 15, 3, 7, 13, 20]で[3, 20]が返ってくるか確認する[42]のようなルートのみの木で[42, 42]が返るか確認する- 空配列で
[]が返ることをチェックする - 木が左に偏った形
[10, 5, null, 3]の場合、最小は3、最大は10であることを確認する
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は BST 妥当性チェック で、BST の最小値と最大値を返す関数を実装する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BST min/max の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BST min/max とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- BST の最小は最左ノード、最大は最右ノードという性質を利用する
- 戻り値は
[min, max]の 2 要素配列。空木のみ空配列を返す - 両方の値を探すために木を全走査する必要はない (左右にだけ進む)
入出力例
test-cases.txt
bstMinMax([]) → []
bstMinMax([42]) → [42,42]
bstMinMax([10,5,15]) → [5,15]
bstMinMax([10,5,15,3,7,13,20]) → [3,20]
bstMinMax([10,5,null,3]) → [3,10]
bstMinMax([1,null,2,null,null,null,3]) → [1,3]