Kth Smallest Element in a BST
ヒープ順序の配列 root として二分探索木が与えられます。ルートはインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあり、-1 は空の位置を示します。配列の末尾には余分な -1 が含まれる場合があります。各ノードで、左部分木にはより小さい値のみが含まれ、右部分木にはより大きい値のみが含まれます。
木の中で 1 から数えて k 番目に小さい値を返してください。
関数
- rootinteger-array
- 二分探索木をレベル順に並べ、空の位置には -1 を指定
- kinteger
- 昇順で検索する位置（1から数える）
- 戻り値integer
- 木の中でk番目に小さい値
制約
1 ≤ root.length ≤ 32767- 各
root[i]は-1、または0 ≤ root[i] ≤ 105を満たす値です。 root[0]は決して-1ではないため、木には少なくとも1つのノードがあります。- 配列は、最後のノードの後に余分な
-1のエントリが続く場合があります。 - 空の場所の子は両方とも空であり、深さは最大でも
14です。 - 順序規則はすべてのノードで成り立つため、同じ値が二度現れることはありません。
1 ≤ k ≤木のノード数。
例
- 入力
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- 出力
- 29
- 説明
- 値を小さい順に並べると
6, 17, 22, 29, 41, 65, 90となり、4番目の値は29です。これはルートの左部分木にある4つの値の中で最大です。
- 入力
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- 出力
- 2
- 説明
- 最小値は、左へ進み続ける経路の終点です：
12、5、2。9の下にある7と-1のパディングは、それを変えません。
発展問題
木が頻繁に変化し、k 番目に小さい値を何度も求める場合、すべてのクエリが O(h) で済むように、各ノードに何を格納するとよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
二分探索木をどの順序で走査すると、値が小さいものから大きいものへと並びますか？
左部分木、次にノード、最後に右部分木を訪問すると、ソート順になります。その探索で得られる
k番目の値が答えなので、そこで終了できます。スタックを使います。現在のノードから左の子へ移動しながら、ノードをプッシュします。先頭をポップして数え、
k回目のポップで停止します。それ以外の場合は、ポップしたノードの右の子である2*i+2へ移動し、繰り返します。
解説
中間順走査（左部分木、ノード、右部分木）は二分探索木の値を昇順に読み取るため、到達した k 番目の値が答えです。自分でスタックを使って走査し、その時点で停止します。ソートは必要ありません。
すべての値を集めて並べ替える
考え方
形状は無視します。-1ではない要素をすべて残してソートし、位置k-1の要素を返します。最初の例では、ソート後のリストは6, 17, 22, 29, 41, 65, 90となり、位置3には29があります。
これは、順序のある木でも順序のない木でも正しく動作します。それがコストでもあります。木がすでに持っている順序を無視し、ソートにO(n log n)、コピーにO(n)のメモリを使います。
アルゴリズム
-1ではないrootのすべての要素を集めます。- 集めた値を昇順に並べ替えます。
- 位置
k-1の値を返します。
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]リストへの中順走査
考え方
どのノードでも、左部分木にはより小さい値だけが入り、右部分木にはより大きい値だけが入ります。左部分木、ノード、右部分木の順に訪問し、各部分木でも同じことを行います。こうすると、各ノードはすべての小さい値の後、すべての大きい値の前に置かれるため、出力はソート済みになります。最初の例では、この走査によって 6, 17, 22, 29, 41, 65, 90 が得られます。
1回の走査でソートを置き換えられます。時間計算量は O(n)、リストに必要な空間計算量は O(n) です。答えが最も左の経路の終点となる k = 1 の場合でも、木全体を訪問します。
アルゴリズム
inorder(i)を記述します。空の位置（末尾を過ぎた位置または-1）で戻ります。- それ以外の場合は、
inorder(2*i+1)を呼び出し、root[i]をリストに追加してから、inorder(2*i+2)を呼び出します。 inorder(0)を呼び出します。k-1の位置にあるリストの要素を返します。
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedk で停止する反復的な中順走査
考え方
明示的なスタックを使うと、途中で探索を止められます。左に行けるところまで進み、各ノードをスタックに積みます。一番上のノードは、まだ数えていない値のうち最小のものです。より小さい値はすべて左部分木にあり、その部分木は空か、すでに数えられているからです。ポップして数え、その右部分木がソート順で次に来ます。
最初の例で k = 4 の場合、41、17、6 を積みます。6、次に 17 をポップし、その右の子へ移動します。29 と 22 を積みます。22、次に4番目の 29 をポップします。この探索では 65 にも 90 にも触れません。
スタックが保持するノードは各レベルにつき最大1つなので、空間計算量は O(h) です。探索は一度下りてから k 回ポップするため、時間計算量は O(h + k) です。
アルゴリズム
- 空のスタックと
i = 0から始めます。 iが実ノードである間、これをプッシュし、2*i+1に移動します。- スタックの先頭を
iにポップし、kから1を引きます。 kが0になったら、root[i]を返します。- そうでなければ
2*i+2に移動し、ステップ 2 に戻ります。
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
落とし穴と境界ケース
- 配列をインデックス順に読み取ること。レベル順はソート順ではありません。最初の例は
41, 17, 65から始まります。 kのオフバイワンに注意してください。カウントは1から始まります。リストの位置k-1を返し、カウントがkに達したら探索を終了します。- 取り出した後に右部分木を飛ばしてしまうこと。2つ目の例では、
9と7は5の右部分木にあり、探索ではそれらをカウントできません。 - 存在しない子を実在するものとして扱うこと。インデックスが末尾を超えているか、値が
-1の場合、子は空です。22はインデックス9にあるため、その子である19と20は末尾を超えています。 - LuaとRの配列は1から始まります。
2*i+1のためにノードのインデックスは0ベースのままにし、root[i + 1]を読み取ります。
よくある質問3
BSTでk番目に小さい要素を見つける時間計算量は何ですか？
深さが h の木に対する反復的な中順走査は、時間計算量が O(h + k)、追加の空間計算量が O(h) です。最悪の場合、k = n となる場合、または木がパス状の場合は、O(n) です。
BSTでk番目に大きい要素を見つけるにはどうすればよいですか？
走査を逆にします。右部分木、次にノード、最後に左部分木の順です。これにより、値が降順に並びます。ノードをスタックに積みながら、行けるところまで右へ進み、ポップして数を数え、ポップするたびに左の子へ移動します。k回目にポップした値が、k番目に大きい値です。
再帰的な中順走査を k 番目の値で停止するには、どうすればよいですか？
再帰の外側にカウンターを用意し、初期値をkにします。ノードの左部分木から戻った後に1を引き、カウンターが0になったらノードの値を記録します。各呼び出しの後、答えが記録されていたらすぐに戻ります。これで再帰版はスタック版と同じになり、時間計算量はO(h + k)、空間計算量はO(h)です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def kthSmallest(root, k):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
期待される出力
29