BST 妥当性チェック
親と子だけを比べる実装は、この木を通してしまう
判定を書けと言われて、まず思いつくのは次の形です。
Python
# よくある間違い — 自分の子としか比べていない
def looksOk(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 looksOk(node.left) and looksOk(node.right)各ノードで自分の子を 2 つ見て、駄目なら偽。木全体も再帰で回っているので、抜けは無さそうに見えます。ところが次の木を渡すと、この関数は真を返します。
15 から見れば 6 は左にいて小さいので、親子の比較は通ります。10 から見ても、子は 5 と 15 で問題ありません。どのノードも、自分の子とは正しい関係にあります。それでも、この木は探索木ではありません。小さい順に取り出すと 5, 10, 6, 15, 20 となって、昇順になっていないからです。
6 は誰に対して違反しているのか
6 は 10 の右側にぶら下がっています。右へ降りた以上、6 は 10 より大きくなければいけません。ところが 6 は 10 より小さい。違反の相手は親ではなく、2 つ上の祖先でした。
親だけを見る実装が見逃すのは、まさにここです。ノードが縛られているのは親からだけではなく、通ってきた祖先すべてからです。
降りるたびに、許される幅が狭くなる
そこで、各ノードに「入ってよい値の幅」を持たせて降ります。根には上も下も制限がありません。左へ降りるときは上限が親の値になり、右へ降りるときは下限が親の値になります。上限と下限は、通った祖先の数だけ入れ替わり立ち替わり更新されていきます。
| ノード | 許される幅 | 判定 |
|---|---|---|
| 10 (根) | 制限なし | OK |
| 5 (10 の左) | 10 未満 | OK |
| 15 (10 の右) | 10 より大きい | OK |
| 6 (15 の左) | 10 より大きく 15 未満 | 違反 |
6 の行だけ、上と下の両方から挟まれています。この幅を子へ引き継いでいけば、祖先との関係も自動で見られるわけです。制限が無い状態は、次のように書けます。
Python
LOW = float('-inf')
HIGH = float('inf')JavaScript なら -Infinity と Infinity です。整数の最小値と最大値を自分で決め打ちすると、その値がデータに入っていたときに判定が崩れます。
等しい値と、空の木
同じ値が 2 つある木は、今回は不正とします。幅の判定を「以上」「以下」で書くと重複を通してしまうので、上下とも等号を含めない形にしてください。
ノードが 1 つも無い木は、破っている約束が 1 つも無いので正しい木です。真を返します。ここを偽にすると、子のいない枝へ降りた瞬間に全体が偽になり、どんな木も通らなくなります。
要件
- 各ノードに対し、許される値域
[lo, hi]を引き継いで判定する - 厳密不等式
lo < val < hiで重複を不正と判定する - 空木は BST とみなして
trueを返す
入出力例
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ヒント
