二分探索木で範囲内のノード数を数える

解説

二分探索木では、あるノードの右部分木にはそのノードの値より大きい値だけが格納される。したがって、右部分木を探索すべきかどうかは「右部分木に high 以下の値が存在しうるか」で判断する。 node.value < high のとき、右部分木の値は node.value より大きいが high 以下の値が含まれる可能性があるため、探索が必要である。一方、node.value ≧ high のとき、右部分木の全ノードは node.value より大きい、すなわち high より大きいので探索は不要である。 【トレース: countInRange(root, 12, 28)、空欄に node.value < high を入れた場合】 (1) node=20: 20≧12 and 20≦28 → count=1 20>12 → 左探索する、20<28 → 右探索する (2) 左: node=10: 10≧12? No → count=0 10>12? No → 左探索しない（5は範囲外なので正しい枝刈り） 10<28? Yes → 右探索する (3) 左の右: node=15: 15≧12 and 15≦28 → count=1 15>12 → 左:null→0、15<28 → 右:null→0 → return 1 node=10 の count = 0+1 = 1 → return 1 (4) 右: node=30: 30≧12 and 30≦28? No → count=0 30>12 → 左探索する、30<28? No → 右探索しない（35は範囲外なので正しい枝刈り） (5) 右の左: node=25: 25≧12 and 25≦28 → count=1 25>12 → 左:null→0、25<28 → 右:null→0 → return 1 node=30 の count = 0+1 = 1 → return 1 (6) node=20 の count = 1+1+1 = 3 → return 3 範囲内のノード 15, 20, 25 の3個が正しく数えられた。

選択肢ごとの解説

ア

この条件では「ノードの値が low より小さいときだけ右を探索する」という意味になる。例えば node.value が 20 で low が 12 のとき、20 < 12 は false となり右部分木を探索しない。しかし右部分木に範囲内の値 25 が存在するため、正しい結果が得られない。

イ

正しい。ノードの値が high より小さいとき、右部分木には node.value より大きい値が格納されており、high 以下の値が存在する可能性がある。逆に node.value ≧ high であれば、右部分木の全ノードは high より大きいので探索不要である。二分探索木の性質を活用した正しい枝刈り条件である。

ウ

この条件は左部分木を探索するかどうかの判定条件と同じである。これを右部分木にも適用すると、例えば countInRange(root, 25, 28) のように low が大きい場合、node.value が 20 のとき 20 > 25 は false となり右部分木を探索しない。しかし右部分木に範囲内の値 25 や 30 内の値が存在するため、正しい結果が得られない。

エ

この条件では「ノードの値が high より大きいときだけ右を探索する」という意味になる。しかし node.value > high のとき、右部分木の全ノードは node.value よりさらに大きく、範囲内の値は存在しない。逆に node.value ≦ high のとき右部分木に範囲内の値がある可能性があるのに探索しないため、正しい結果が得られない。

登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。