Range Sum of BST
二分探索木は、レベル順で配列 tree に格納されています。ルートはインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあり、-1 は空の位置を示します。二分探索木では、ノードの左部分木にあるすべての値はそのノードの値より小さく、右部分木にあるすべての値はそのノードの値より大きくなります。
low ≤ v ≤ high を満たすすべてのノード値 v の合計を返します。該当する値がない場合は 0 を返します。
関数
- treeinteger-array
- 二分探索木をレベル順で表したもので、空の位置には -1 を使用します
- lowinteger
- 数える最小の値
- highinteger
- 数える最大の値
- 戻り値integer
- low と high の間（両端を含む）のノード値の合計
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1、または0 ≤ tree[i] ≤ 105を満たす値です。 tree[0]は決して-1ではないため、ツリーには少なくとも1つのノードがあります。- 配列の末尾には、最後のノードの後に余分な
-1のエントリが含まれる場合があります。 - 空の位置の子は両方とも空であり、深さは最大でも
14です。 - この木は有効な二分探索木なので、すべての値は異なります。
0 ≤ low ≤ high ≤ 105- 答えは32ビット符号付き整数に収まります。
例
- 入力
- tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
- 出力
- 88
- 説明
9から31までの値は、10、12、15、20、31で、合計は88です。3、8、40は範囲外です。
- 入力
- tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
- 出力
- 0
- 説明
- 木には
25、50、75が含まれており、そのどれも60から70の間にないため、合計は0です。4つの-1のエントリーは、25と75の空の子ノード位置です。
- 入力
- tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
- 出力
- 4
- 説明
lowとhighがどちらも4の場合、値が4のノードだけが該当します。インデックス4の4は2の右の子なので、答えは4です。
発展問題
同じ木に対する何千もの異なる (low, high) クエリに答える必要がある場合、それぞれのクエリに O(log n) 時間で答えるにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべてのノードを訪れて範囲内の値を加算すると、正しい答えが得られます。探索木の順序から、あるノードの下にある値について何がわかりますか？
ノードの左部分木にあるものはすべてそのノードより小さく、右部分木にあるものはすべて大きくなります。ノードの値が
low以下の場合、その左側に範囲内のものはあるでしょうか？ルートからインデックスのスタックを使って木をたどります。ノードの値が範囲内にある場合はその値を加え、値が
lowより大きい場合にのみ左の子を2*i+1に追加し、値がhighより小さい場合にのみ右の子を2*i+2に追加します。
解説
すべてのノードをたどり、範囲内の値を加算する方法でも正しく求められます。探索木の順序を利用すれば、処理を減らせます。ノードの値から、小さい値と大きい値のどちらがどちら側にあるかがわかるため、範囲内の値にたどり着けない部分木を開くことはありません。
すべてのノードを訪問する
考え方
子は、そのインデックスが配列の範囲内にあり、そこにある値が -1 でない場合にのみ実在します。最初の例では、インデックス 4 の 12 にはインデックス 9 と 10 に 10 と 15 があり、インデックス 2 の 31 にはインデックス 5 に左側の空き位置があります。
範囲内のすべての値は何らかのノードにあるため、すべてのノードを訪れて low ≤ v ≤ high の値を加算するスタック走査を行えば、正しい合計が得られます。探索木の順序を無視するため、範囲内の値が少数しかなくても、n 個すべてのノードにアクセスします。
アルゴリズム
- 根のインデックス
0をスタックにプッシュし、total = 0に設定します。 - インデックス
iをポップします。low ≤ tree[i] ≤ highの場合、tree[i]をtotalに加算します。 - 配列の範囲内にあり、
-1ではない場合、2*i+1と2*i+2をプッシュします。 - スタックが空になったら、
totalを返します。
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append(left)
if right < n and tree[right] != -1:
stack.append(right)
return total探索木の順序で枝刈りする
考え方
vを保持するノードの左部分木には、vより小さい値しかありません。v ≤ lowなら、その中に範囲内の値はないため、その部分木はスキップします。v ≥ highなら、右部分木にはhighより大きい値しかないため、右部分木をスキップします。最初の例では、31はhighと等しいので、その右の子である40はプッシュされません。8はlowより小さいため、その左の子である3はスキップされますが、右の子である12は訪問されます。8と20の間の値は範囲内に入り得るからです。
範囲内のk個の値と、ルートからの最大2本の経路上にあるノードを訪問します。深さがhの場合、時間計算量はO(h + k)です。範囲が木全体を含む場合でも、計算量はO(n)です。
アルゴリズム
- ルートのインデックス
0をスタックにプッシュし、total = 0を設定します。 - インデックス
iをポップし、v = tree[i]を読み取ります。low ≤ v ≤ highの場合、vをtotalに加算します。 v > lowの場合、左の子2*i+1が実在すればプッシュします。v < highの場合、右の子2*i+2が実在すればプッシュします。- スタックが空になったら、
totalを返します。
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
# Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
if value > low and left < n and tree[left] != -1:
stack.append(left)
if value < high and right < n and tree[right] != -1:
stack.append(right)
return total
落とし穴と境界ケース
- 厳密な比較を使う。両端を含むため、
low = high = 4の第3の例では、4を数える必要があります。 - 枝刈りを1ステップ早く行う。
v = lowでは左部分木を除外できますが、v = low + 1では左部分木にlow自体が含まれている可能性があります。 - 範囲外のノードの両側を除外する。最初の例の
8はlowより小さいですが、その右部分木には10、12、15が含まれています。 - 配列の末尾を越えて子ノードを読み取る。読み取る前に
2*i+1 < tree.lengthを確認し、-1は子ノードがないことを示すものとして扱います。 - LuaとRでは配列が1から始まります。
2*i+1の計算ではノードのインデックスを0始まりのままにし、tree[i + 1]を読み取ります。
よくある質問3
BST の範囲合計の時間計算量は何ですか？
枝刈りされた走査では、範囲内のk個のノードと、ルートからの最大2つの経路上にあるノードを訪問します。深さがhの木では時間計算量はO(h + k)で、すべての値が範囲内にある場合はO(n)です。スタックまたは再帰に必要な空間はO(h)です。
BST の範囲合計は、中順走査で解けますか？
はい。中順走査では値が昇順に並ぶため、lowに達した値から追加し、highを初めて超えた値で停止します。早期停止によって木の右側での処理を省けますが、枝刈りなら両側で処理を省けます。
Range Sum of BST には再帰とスタックのどちらを使うべきですか？
どちらも動作します。ここでは深さは最大14なので、再帰の深さは浅いままです。明示的なスタックを使えば、数千レベルに及ぶ高い木で再帰制限に達するのを避けられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def rangeSumBST(tree, low, high):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] low = 9 high = 31
期待される出力
88