問題
二分探索木のroot と、key をkey の
- 二分探索木では、
どの 節でも、 左の 部分木の 値は すべて その 節より 小さく、 右の 部分木の 値は すべて その 節より 大きくなっています - 各節は
val、left、rightを持ちます。 Go の 節は TreeNodeで、Val、Left、Rightです - 消し方は
次の 通りに 決めます。 子が 無ければ、 その節を ただ外します。 子が 1 つだけなら、 その子を 節の 位置へ 上げます。 子が 2 つなら、 右の 部分木で いちばん 小さい 値の 節を、 消す節の 位置に 置き換えます keyが木に 無い ときは、 木を そのまま 返します。 消した 結果、 木が 空に なったら 空の 木 (Python は None、JavaScript は null、Go は nil) を返します- 節の
数は 0 以上 500 以下、 値は どれも 違い、 -100000 以上 100000 以下です
例では、null で、null は
入力と出力の例
例 1
根の 50 を
入力
root = [50, 30, 70, 20, 40,
60, 80]
key = 50出力
[60, 30, 70, 20, 40, null, 80]例 2
9 を
入力
root = [15, 9, 21, null, 12,
18]
key = 9出力
[15, 12, 21, null, null, 18]例 3
節が 1 つだけの
入力
root = [42]
key = 42出力
[]面接での聞かれ方
面接では、
- 「二分探索木から、
指定の 値を 消す関数を 書いてください。 返すのは 新しい根です」 - 「消す節に
子が 2 つある ときは、 どの 節を 持ってきますか？」と、 置き換えの 決め方を 口で 説明させられます - 書き終えた
あとに 「根を 消すときも 動きますか？」 「計算量は 木の 形で どう 変わりますか？」と 聞かれます
消す節を
アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。
まず
段 1
まず、key が
段 2
見つけた
段 3
子が 2 つの
段 4
親のroot.left に
解答
Python
Python
def delete_bst(root, key):
if root is None:
return None
if key < root.val:
root.left = delete_bst(
root.left, key)
elif key > root.val:
root.right = delete_bst(
root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
nxt = root.right
while nxt.left:
nxt = nxt.left
root.val = nxt.val
root.right = delete_bst(
root.right, nxt.val)
return rootJavaScript
JavaScript
function deleteBst(root, key) {
if (root === null) {
return null;
}
if (key < root.val) {
root.left = deleteBst(
root.left, key,
);
} else if (key > root.val) {
root.right = deleteBst(
root.right, key,
);
} else {
if (root.left === null) {
return root.right;
}
if (root.right === null) {
return root.left;
}
let next = root.right;
while (next.left !== null) {
next = next.left;
}
root.val = next.val;
root.right = deleteBst(
root.right, next.val,
);
}
return root;
}Go
Go
func deleteBst(
root *TreeNode, key int,
) *TreeNode {
if root == nil {
return nil
}
if key < root.Val {
root.Left = deleteBst(
root.Left, key,
)
} else if key > root.Val {
root.Right = deleteBst(
root.Right, key,
)
} else {
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
next := root.Right
for next.Left != nil {
next = next.Left
}
root.Val = next.Val
root.Right = deleteBst(
root.Right, next.Val,
)
}
return root
}左の
計算量
- 時間は O(h) です。
h は 木の 高さです。 消す節まで 1 本道で 下り、 子が 2 つなら 右の 部分木の 中を もう 1 本下るだけです。 木が 片側に 伸びきると h は n に なり、 O(n) です - 使う
記憶は O(h) です。 再帰の 呼び出しが、 たどった 道の 長さだけ積み重なります。 節の 数は 500 以下なので、 Python の 再帰の 上限には かかりません
よく
- 子が 2 つの
とき、 左の 子を 上げてしまう。 左の 子を 消す節の 位置へ 上げると、 右の 部分木を どこへつな ぐかが 決まらず、 決まりが 崩れたり節が 消えたりします。 右の 部分木の いちばん 小さい 値で 置き換えます - 置き換えた
あと、 元の 節を 消し忘れる。 値を 写しただけでは、 同じ 値が 2 つ 残ります。 右の 部分木から、 その値を もう 一度消します - 戻り値を
親に つなぎ直さない。 再帰の 戻り値を root.leftやroot.rightに入れ直さないと、 子を 上げた つもりでも 木が 変わりません。 根を 消した ときに 古い根を 返してしまうのも 同じ 間違いです keyが無い 場合を 考えない。 探して 空の 節まで 来たら、 何も せずに 空を 返せば 済みます。 ここで 止まる 書き方に しておかないと、 無い値を 渡された ときに 空の 節の valを読んで 止まります
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「二分探索木なので、
keyより小さければ 左、 大きければ 右へ 進んで、 消す節を 1 本道で 探します。 見つけたら子の 数で 分けて、 子が 無いか 1 つなら、 残った 子を そのまま 上げます。 子が 2 つなら、 右の 部分木で いちばん 小さい 値を 写して、 その値を 右から 消し直します。 関数は 部分木の 新しい 根を 返す形に して、 親に 入れ直します。 時間も 記憶も 木の 高さ分で O(h) です。」
書き終えたら、
「例 1 で
たどります。 50 が 根で 見つかり、 子が 2 つあります。 右の 70 から 左へ 進むと 60 で 止まるので、 根の 値を 60 にします。 次に、 70 の 部分木から 60 を 消します。 60 は 子が 無いので 外して 終わりです。 根が 60、 右の 70 には 80 だけが 残ります。」