BST 妥当性チェック
BST 妥当性チェック
このレッスンで分かること
in-order = 昇順は BST の最重要性質の 1 つ- どちらの解法も
O(n)時間 /O(h)メモリです- この問題は採用面接でも頻出する古典的なお題で、
一見正しく見えて間違っている罠が仕込まれています
BST 妥当性チェック とは
与えられた二分木が BST の不変条件を満たしているか判定する関数を実装する。本レッスンでは、BST 妥当性チェック の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
ここまで BST のことを「左の子は親より小さく、右の子は親より大きい」と単純化して説明してきました。しかし実は、これだけでは BST の 不変条件 を厳密には表せていません。本レッスンで作るのは、ある二分木が 本当に BST かどうか を判定する isBst(arr) 関数です。
この問題は採用面接でも頻出する古典的なお題で、一見正しく見えて間違っている 罠が仕込まれています。罠を理解すれば、BST の本質である 部分木全体の値域 が見えてきます。
BST の正しい不変条件は「左部分木の すべての 値
<親<右部分木の すべての 値」。直接の子だけを見ても不十分。
よくある間違った実装
素朴に書くと、こんなコードになりがちです。
Python
def isBstNaive(node):
if node is None:
return True
if node.left and node.left.val >= node.val:
return False
if node.right and node.right.val <= node.val:
return False
return isBstNaive(node.left) and isBstNaive(node.right)直接の子しか見ていないので、次のような木で True を返してしまいます。
図のポイント (テキスト併記)
- ルート
10の右部分木に6がぶら下がっています
ルート 10 の右部分木に 6 がぶら下がっています。6 は 15 より小さく見えますが、ルートから見れば 10 より小さい値が右部分木に紛れ込んでおり、BST 不変条件を 破っています。
正しいアプローチ
各ノードに対し、許される値の [lo, hi] レンジを伝播させていきます。
- ルートのレンジは
[-∞, +∞] - 左の子に進むときは
hiを親の値で更新 (左部分木はそれ未満) - 右の子に進むときは
loを親の値で更新 (右部分木はそれより大きい)
ノードの値がこのレンジを外れたら、その瞬間に False を返します。
Python
def isBst(node, lo=float('-inf'), hi=float('inf')):
if node is None:
return True
if not (lo < node.val < hi):
return False
return isBst(node.left, lo, node.val) and isBst(node.right, node.val, hi)レンジを引き連れて再帰するだけ。シンプルですが、これが BST 検証の 正しい 雛形です。
in-order を使った別解
もう 1 つ有名な解法があります。BST を in-order 走査すると、値が 昇順 に並ぶという性質を使うものです。手順は次の通り。
- in-order 走査でノードの値を順番に取り出す
- 直前の値より小さい (または等しい) 値が出てきたら
False - すべて昇順に並んでいたら
True
どちらの解法も O(n) 時間 / O(h) メモリです。レンジ伝播の方が処理を途中で打ち切れる分わずかに速いこともありますが、可読性重視なら in-order 解法も悪くありません。
in-order = 昇順は BST の最重要性質の 1 つ。次レッスンのk 番目でも使う。
Python での実装例 (レンジ伝播)
Python
def isBst(arr):
root = buildTree(arr)
def helper(node, lo, hi):
if node is None:
return True
if not (lo < node.val < hi):
return False
return helper(node.left, lo, node.val) and helper(node.right, node.val, hi)
return helper(root, float('-inf'), float('inf'))JavaScript での実装例 (in-order)
JavaScript
function isBst(arr) {
const root = buildTree(arr);
let prev = -Infinity;
function inorder(node) {
if (node === null) return true;
if (!inorder(node.left)) return false;
if (node.val <= prev) return false;
prev = node.val;
return inorder(node.right);
}
return inorder(root);
}prev を クロージャ で持ち回すパターン。状態を関数の外で持つと書きやすくなります。
よくある間違い
本レッスンで一番大事なのは、直接の子だけ チェックして満足してしまわないこと。これは BST 検証の 最大の落とし穴 です。レンジ伝播か in-order を使えば回避できます。次の落とし穴は 重複値 の扱い。本問では「等しい値は不正」とします (lo < val < hi の厳密不等式)。最後は 空木 をどう扱うか。空木は技術的には BST なので、True を返します。
in-order 解法は再帰呼び出し順がそのまま検証順になるため、デバッグもしやすい。本番ではどちらを選んでも OK。
やってみよう
[10, 5, 15, null, null, 6, 20](右部分木に 6 が紛れ込んでいる) でFalseが返ることを確認する[10, 5, 15, 3, 7, 12, 20]でTrueが返ることを確認する- 空配列
[]でTrueが返ることを確認する
よくある質問
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 で k 番目に小さい値 で、与えられた二分木が BST の不変条件を満たしているか判定する関数を実装する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BST validate の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BST validate とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 各ノードに対し、許される値域
[lo, hi]を引き継いで判定する - 厳密不等式
lo < val < hiで重複を不正と判定する - 空木は BST とみなして
trueを返す
入出力例
test-cases.txt
isBst([]) → true
isBst([10]) → true
isBst([10,5,15]) → true
isBst([10,5,15,3,7,12,20]) → true
isBst([10,5,15,null,null,6,20]) → false
isBst([5,10,15]) → false
isBst([10,5,5]) → false