BSTへの挿入と探索
挿入と探索を再帰版・反復版で実装し、さまざまなキーについて木を通る経路を追跡し、非平衡木の最悪時計算量を分析します。
「BSTへの挿入と探索」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
BSTの性質の定義
二分探索木は、1つの不変条件を満たします。すべてのノードについて、左部分木のすべての値はノードの値より厳密に小さく、右部分木のすべての値はノードの値より厳密に大きいという条件です。この順序付けの性質は、直下の子だけでなく部分木全体で維持されます。そのため、平衡した木では検索、挿入、削除をO(log n)で行うことができ、BSTは一般的な二分木と区別されます。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Valid BST:
# 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
# For node 4: left subtree {1,2,3} < 4 < right subtree {5,6,7}
# This holds recursively for EVERY node in the tree.
print('BST property: left < node < right at every level')BSTの再帰的な検索
BSTの検索は二分探索と同じように機能します。目標値と現在のノードの値を比較し、適切な部分木へ再帰します。目標値が現在の値と等しければ、そのノードを返します。目標値が小さければ左へ、大きければ右へ進みます。空のノードに到達したらnullを返します。計算量はO(h)で、平衡した木ではO(log n)、偏った木ではO(n)です。
def search_bst(root, val):
if not root:
return None # not found
if root.val == val:
return root # found
if val < root.val:
return search_bst(root.left, val)
else:
return search_bst(root.right, val)
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
result = search_bst(root, 2)
print(result.val if result else 'Not found') # 2
result = search_bst(root, 5)
print(result.val if result else 'Not found') # Not foundBSTの反復的な検索
反復的な検索では呼び出しスタックのオーバーヘッドを避けられるため、実運用のコードで推奨されます。currポインタを使い、比較結果に応じて左または右へ木を下っていきます。これは、null（見つからない）、一致（見つかった）、方向の調整という3つのケースを処理する単純なwhileループです。反復的な検索もO(h)ですが、再帰版のO(h)空間に対して、空間計算量はO(1)です。
def search_bst_iterative(root, val):
curr = root
while curr:
if val == curr.val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None # not found
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
node = search_bst_iterative(root, 3)
print(node.val if node else 'Not found') # 3
print(search_bst_iterative(root, 9)) # NoneBSTの再帰的な挿入
BSTへの挿入では、検索と同じ左または右の判断をたどって正しい位置を見つけ、最初に到達したnullの位置に新しいノードを取り付けます。再帰的な方法では、各部分木の（新しくなった可能性のある）根を返します。現在のノードがnullなら新しいTreeNodeを返し、それ以外の場合は再帰呼び出しの結果でroot.leftまたはroot.rightを更新します。このパターンは分かりやすく、面接の解答でよく使われます。
def insert_bst(root, val):
if not root:
return TreeNode(val) # create new node here
if val < root.val:
root.left = insert_bst(root.left, val)
elif val > root.val:
root.right = insert_bst(root.right, val)
# val == root.val: duplicate, do nothing (or handle as needed)
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst(root, 1)
root = insert_bst(root, 5)
# Tree is now: 4, left=2(left=1), right=7(left=5)
print(root.right.left.val) # 5BSTの反復的な挿入
反復的な挿入では、挿入位置に到達する前の最後のnullでないノードを追跡するために、parentポインタを使います。検索と同じように木を下りながら、親と最後に進んだ方向を記録します。nullに到達したら、親の適切な側に新しいノードを取り付けます。空の木の場合（rootがnullの場合）は、必ず別に処理してください。
def insert_bst_iterative(root, val):
new_node = TreeNode(val)
if not root:
return new_node
curr = root
while True:
if val < curr.val:
if curr.left is None:
curr.left = new_node
break
curr = curr.left
else: # val > curr.val
if curr.right is None:
curr.right = new_node
break
curr = curr.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst_iterative(root, 3)
print(root.left.right.val) # 3最悪の場合のBST：偏った木
BSTにソート済みのシーケンスを挿入すると、偏った木になり、連結リストのような構造に変化します。検索、挿入、削除はすべてO(n)になります。これが平衡したBST（AVL木やRed-Black木）が存在する理由です。面接でBSTの計算量を聞かれたら、必ずこの最悪ケースにも言及してください。「平衡していない木では平均O(log n)、最悪O(n)」と答えれば、深い理解を示せます。
# Inserting 1, 2, 3, 4, 5 into a BST:
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
# This is a right-skewed tree: search is O(n) not O(log n)
root = None
for val in [1, 2, 3, 4, 5]:
root = insert_bst(root, val)
# Verify the skew
node = root
depth = 0
while node:
depth += 1
node = node.right
print(f'Height: {depth}') # 5 = O(n), not O(log n)最小値と最大値の検索
BSTでは、最小値は必ず左端のノードにあります（nullに到達するまで左へ進み続けます）。同様に、最大値は右端のノードにあります。これらのO(h)の操作は、BSTの削除（中順後継ノードの検索）や範囲クエリのサブルーチンとして頻繁に使われます。これらのヘルパー関数を覚えておくと、面接で時間を節約できます。
def find_min(root):
while root.left:
root = root.left
return root
def find_max(root):
while root.right:
root = root.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(9)
print(find_min(root).val) # 1
print(find_max(root).val) # 9中順後継ノードと前任ノード
ノードの中順後継ノードとは、そのノードより大きい値の中で最小の値を持つノードです。そのノードに右部分木がある場合、後継ノードはfind_min(node.right)です。右部分木がない場合、後継ノードは、対象のノードが左部分木に含まれる最も近い祖先です。これはBSTの削除やBSTイテレータの問題を理解するうえで重要です。
def inorder_successor(root, p):
successor = None
while root:
if p.val < root.val:
successor = root # possible successor
root = root.left
else:
root = root.right
return successor
def inorder_predecessor(root, p):
predecessor = None
while root:
if p.val > root.val:
predecessor = root # possible predecessor
root = root.right
else:
root = root.left
return predecessor
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
p = root.left # node with val=2
print(inorder_successor(root, p).val) # 3
print(inorder_predecessor(root, p).val) # 1BSTの検索計算量の分析
BSTの性能は木の高さに完全に依存します。n個のノードを持つ平衡したBSTでは、高さがO(log n)になるため、検索、挿入、削除はいずれもO(log n)です。偏ったBSTでは高さがO(n)になり、すべての操作がO(n)になります。Pythonには、JavaのTreeMapのような組み込みの平衡BSTがありません。そのため、自分でAVL木やRed-Black木を実装するか、sortedcontainers.SortedListを使うか、優先度付きキューの用途ではヒープを利用します。
# Python's BST alternatives:
# 1. heapq - min/max heap, O(log n) push/pop
# 2. sortedcontainers.SortedList (third-party, often allowed)
# 3. Manual AVL or Red-Black (rarely required in interviews)
# When interviews say 'use a BST':
# - LeetCode: implement TreeNode-based solution
# - Real interview: mention sortedcontainers or Java TreeMap equivalent
# - O(log n) operations matter when you need ordered access
# For pure insert/lookup without ordering: use dict (O(1) average)
print('Use heap for priority, dict for lookup, BST for ordered range')BSTへの挿入：エッジケース
挿入処理では、空の木（新しいノードを根として返す）、重複値（無視するのか、左に挿入するのか、右に挿入するのかを定義し、一貫させる）、非常に大きい値や小さい値を必ず確認してください。面接では、コーディングの前に重複値についての前提を述べます。LeetCodeの問題で最も一般的な規約は、特に指定がない限り、すべての値が異なるというものです。
def insert_bst_no_duplicates(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst_no_duplicates(root.left, val)
elif val > root.val:
root.right = insert_bst_no_duplicates(root.right, val)
# else: val == root.val -> duplicate, skip
return root
# Test all edge cases:
root = None
root = insert_bst_no_duplicates(root, 5) # empty tree
root = insert_bst_no_duplicates(root, 5) # duplicate
root = insert_bst_no_duplicates(root, 3)
root = insert_bst_no_duplicates(root, 7)
print(root.val, root.left.val, root.right.val) # 5 3 7ソート済み配列からBSTを構築する
ソート済み配列から高さが平衡したBSTを構築する（LeetCode #108）には、分割統治法を使います。中央の要素を根にし、左半分を左部分木に、右半分を右部分木にします。これにより、高さO(log n)の平衡した木が保証されます。各要素を1回ずつ処理するため、時間計算量はO(n)です。
def sorted_array_to_bst(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sorted_array_to_bst(nums[:mid])
root.right = sorted_array_to_bst(nums[mid+1:])
return root
nums = [-10, -3, 0, 5, 9]
root = sorted_array_to_bst(nums)
print(root.val) # 0 (middle element)
print(root.left.val) # -3
print(root.right.val) # 9確認テスト
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、BSTの性質（左部分木は厳密に小さく、右部分木は厳密に大きい）、O(h)時間で行う検索と挿入の再帰版および反復版、高さがnに等しくなる最悪ケースの偏った木を学びました。次はBSTの削除と、その3つのケースに取り組みます。
よくある質問
「BSTへの挿入と探索」レッスンは無料ですか？
はい。「BSTへの挿入と探索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「BSTへの挿入と探索」で何を学びますか？
挿入と探索を再帰版・反復版で実装し、さまざまなキーについて木を通る経路を追跡し、非平衡木の最悪時計算量を分析します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「BSTへの挿入と探索」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。