BSTの削除：3つのケース
in-order successorを使い、葉の削除、子が1つの場合の削除、子が2つの場合の削除を扱うアルゴリズムをゼロから実装します。
「BSTの削除：3つのケース」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
BSTの削除が難しい理由
BSTの削除は、基本操作3種類の中で最も複雑です。ノードを削除する際に、木全体のBSTの性質を維持しなければならないためです。ノードの子の状態に応じて、3つの異なるケースがあります。子がない（葉）、子が1つ、子が2つのケースです。それぞれ異なる方法で処理する必要があります。面接官がこの問題を好むのは、ポインタ操作、エッジケースを考える力、中順後継ノードの概念に関する知識を評価できるからです。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
# then delete the in-order successor
print('BST delete: 3 cases based on number of children')ケース1：葉ノードの削除
葉ノードには子がありません。削除は単純です。再帰呼び出しからNoneを返すと、親がそのポインタ（左または右）をnullに設定します。これは、すべてのBST削除実装で最初に処理する必要がある基本ケースです。木にノードが1つしかない特殊なケース（根が葉）でも正しく動作することを確認してください。
def find_min(node):
while node.left:
node = node.left
return node
# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1) # leaf
root.left.right = TreeNode(4) # leaf
# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left) # None -- deleted
print(root.left.val) # 3 still intactケース2：子を1つ持つノード
ノードが子をちょうど1つ持つ場合は、そのノードを子で置き換えます。再帰呼び出しから null ではない子を返すことで、親のポインターが更新され、削除したノードを飛ばせます。左の子だけがある場合でも右の子だけがある場合でも同じように機能し、存在する方の子を返すだけで済みます。
# Demonstrating one-child deletion:
# Tree: 5
# / \
# 3 7
# \
# 4
# Delete node 3 (has only right child 4):
# Result: 5
# / \
# 4 7
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.right = TreeNode(4)
# In the recursive implementation:
# When we reach node 3 and it has no left child,
# we return root.right (node 4) to the parent.
# Parent sets its left pointer to 4, skipping 3.
print('One-child case: return the surviving child')ケース3：子を2つ持つノード
ノードが子を2つ持つ場合は、単純に削除することはできません。代わりに、ノードの中順後継ノード（右部分木にある最小の値）を見つけ、その値を現在のノードにコピーしてから、右部分木から中順後継ノードを削除します。後継ノードが持つ子は最大でも1つ（左の子はありません）なので、その削除はケース1またはケース2に該当します。これらの処理方法はすでに分かっています。
# Demonstrating two-child deletion:
# Tree: 5
# / \
# 3 7
# / \
# 6 9
# Delete node 5 (two children 3 and 7):
# In-order successor = 6 (smallest in right subtree)
# Step 1: replace 5's value with 6
# Step 2: delete 6 from right subtree
# Result: 6
# / \
# 3 7
# \
# 9
print('Two-child case: replace with in-order successor')BSTの削除処理の完全な実装
完全な再帰的削除処理では、3つのケースをすべて組み合わせます。値を比較して削除対象のノードを見つけ、該当するケースを処理します。各レベルで（変更されている可能性のある）ルートを返し、それを root.left または root.right に代入するパターンにより、親を明示的に追跡しなくても、すべてのポインター更新を簡潔に処理できます。時間計算量は O(h) です。
def delete_node(root, key):
if not root:
return None # key not found
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else: # found the node to delete
if not root.left: # Case 1 or 2: no left child
return root.right
if not root.right: # Case 2: no right child
return root.left
# Case 3: two children -> find in-order successor
successor = find_min(root.right)
root.val = successor.val # copy successor value up
root.right = delete_node(root.right, successor.val) # delete successor
return root
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root = delete_node(root, 5)
print(root.val) # 6 (successor replaced 5)中順後継ノードを使う理由
右部分木の最小値である中順後継ノードを使うのは、左部分木の最大値を使う方法も有効であり、どちらを使ってもBSTの性質を維持できるためです。中順前駆ノード（左部分木の最大値）を使う方法も同様に機能します。実装によっては、木のバランスを保つために両方の方法を交互に使います。面接では中順後継ノードを使う実装がより一般的に求められるため、前駆ノードでも同じように処理できることを説明できるようにしておきましょう。
# Both approaches are valid for two-child deletion:
# Option A: Replace with in-order SUCCESSOR (min of right subtree)
# - Successor goes to current position
# - Delete successor from right subtree
# Option B: Replace with in-order PREDECESSOR (max of left subtree)
# - Predecessor goes to current position
# - Delete predecessor from left subtree
def find_max(node):
while node.right:
node = node.right
return node
# Using predecessor:
def delete_node_pred(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node_pred(root.left, key)
elif key > root.val:
root.right = delete_node_pred(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
pred = find_max(root.left)
root.val = pred.val
root.left = delete_node_pred(root.left, pred.val)
return root
print('Both successor and predecessor deletion are correct')ある値を持つすべてのノードの削除
値が範囲内にある、または条件に一致するすべてのノードを削除するバリエーションもあります。BSTでは、この処理を効率的に行えます。比較結果に基づいて適切な部分木を再帰的に探索し、条件に一致するノードごとに削除処理を適用します。BSTの削除処理が持つ再帰構造は、このようなケースにも自然に拡張でき、別途走査を行う必要はありません。
# Delete all nodes with values outside [low, high]
def trim_bst(root, low, high):
if not root:
return None
if root.val < low:
# Entire left subtree is also < low, skip to right
return trim_bst(root.right, low, high)
if root.val > high:
# Entire right subtree is also > high, skip to left
return trim_bst(root.left, low, high)
# Current node is within range
root.left = trim_bst(root.left, low, high)
root.right = trim_bst(root.right, low, high)
return root
root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)
root = trim_bst(root, 1, 3)
print(root.val, root.left.val) # 3 2BSTイテレータのパターン
BSTイテレータ（LeetCode #173）は、要素をソート順に1つずつ返します。平均時間計算量は O(1)、空間計算量は O(h) です。反復的な中順走査をシミュレートするスタックを使って実装します。構築時には、ルートから左側のノードをすべてスタックに積みます。next() ではスタックの先頭を取り出し、右部分木の左側にあるノードをすべて積みます。これは、反復的な中順走査アルゴリズムを制御しながら展開したものです。
class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
if node.right:
self._push_left(node.right)
return node.val
def has_next(self):
return bool(self.stack)
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
it = BSTIterator(root)
while it.has_next():
print(it.next(), end=' ') # 3 7 9 15ノード削除：計算量の分析
BSTの削除は、木の高さを h とすると O(h) 時間で実行されます。バランスの取れたBSTでは O(log n) です。偏った木では O(n) まで悪化します。中順後継ノードを見つけるために、右部分木を最大で1回追加走査しますが、これも O(h) であり、全体の計算量は変わりません。再帰実装の空間計算量は、呼び出しスタックの分として O(h) です。
# Complexity summary for BST operations:
# Operation | Balanced | Skewed
# ----------|-----------|-------
# Search | O(log n) | O(n)
# Insert | O(log n) | O(n)
# Delete | O(log n) | O(n)
# Min/Max | O(log n) | O(n)
# In-order | O(n) | O(n) (visits all nodes)
# The key: BST guarantees these complexities only when balanced.
# Python standard library has no balanced BST.
# Use sortedcontainers.SortedList for O(log n) ops in practice.
print('All BST core ops are O(h): O(log n) balanced, O(n) skewed')BSTでのTwo Sum
BSTにおけるTwo Sum IVでは、合計が指定された値になる2つのノードが存在するかどうかを判定します。1つの方法では集合を使います。中順走査を行いながら値を集め、target - current がそれまでの集合に存在するかを確認します。より洗練された方法では、BSTイテレータを順方向と逆方向に同時に使い、2ポインターのように処理します。これにより、各イテレータのスタックに必要な O(h) を超える追加の空間を避けられます。
def find_target_bst(root, k):
seen = set()
def inorder(node):
if not node:
return False
if inorder(node.left):
return True
if k - node.val in seen:
return True
seen.add(node.val)
return inorder(node.right)
return inorder(root)
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(find_target_bst(root, 9)) # True (2+7)
print(find_target_bst(root, 28)) # FalseBSTをGreater Sum Treeに変換
Greater Sum Tree（LeetCode #538）では、BST内でそのノード以上の値をすべて合計した値で、各ノードの値を置き換えます。重要なポイントは、逆中順走査（右 → ルート → 左）を行い、ノードを降順に訪問しながら累積合計を計算することです。時間計算量は O(n)、空間計算量は O(h) です。
def bst_to_gst(root):
acc = [0] # running accumulated sum
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right) # visit larger values first
acc[0] += node.val
node.val = acc[0] # replace with cumulative sum
reverse_inorder(node.left)
reverse_inorder(root)
return root
root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
bst_to_gst(root)
print(root.val) # 4+5+6+7 = 22
print(root.right.val) # 5+6+7 = 18理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、BSTの削除における3つのケース（葉、子が1つ、子が2つ）、子を2つ持つノードを削除するための中順後継ノードの手法、さらにBSTイテレータやBSTからGreater Sum Treeへの変換で使われる、簡潔な再帰パターンを学びました。次は、BSTが正しいかを検証し、中順走査の性質を活用します。
よくある質問
「BSTの削除：3つのケース」レッスンは無料ですか？
はい。「BSTの削除：3つのケース」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「BSTの削除：3つのケース」で何を学びますか？
in-order successorを使い、葉の削除、子が1つの場合の削除、子が2つの場合の削除を扱うアルゴリズムをゼロから実装します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「BSTの削除：3つのケース」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。