BST 삭제: 세 가지 경우
중위 후속자를 사용해 리프 삭제, 자식 하나 삭제, 자식 둘 삭제를 처리하고 알고리즘을 처음부터 구현합니다.
BST 삭제: 세 가지 경우은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
BST 삭제가 까다로운 이유
BST 삭제는 노드를 제거하면서 전체 트리의 BST 규칙을 유지해야 하므로 세 가지 핵심 작업 중 가장 복잡합니다. 노드의 자식에 따라 서로 다른 세 가지 경우가 있습니다. 자식이 없는 경우(리프), 자식이 하나인 경우, 자식이 둘인 경우입니다. 각 경우에는 서로 다른 전략이 필요합니다. 이 문제는 포인터 조작, 예외 상황에 대한 사고, 중위 후속자 개념에 대한 이해를 확인할 수 있어 면접관들이 좋아합니다.
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을 반환하면 부모가 자신의 포인터(왼쪽 또는 오른쪽)를 널로 설정하게 됩니다. 이는 모든 BST 삭제 구현이 먼저 처리해야 하는 기본 사례입니다. 트리에 노드가 하나뿐인 특수한 경우에도 이 방식이 작동하는지 확인하십시오(루트가 리프인 경우).
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: 자식이 하나인 노드
노드에 정확히 하나의 자식 노드가 있으면 해당 노드를 자식 노드로 대체합니다. 부모의 포인터가 삭제된 노드를 건너뛰도록 갱신되게 하려면 재귀 호출에서 널이 아닌 자식 노드를 반환합니다. 하나의 자식 노드가 왼쪽에 있든 오른쪽에 있든 자연스럽게 작동하므로, 존재하는 자식 노드를 반환하기만 하면 됩니다.
# 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: 자식이 둘인 노드
노드에 두 자식 노드가 있으면 해당 노드를 단순히 제거할 수 없습니다. 대신 노드의 중위 후계자(오른쪽 부분 트리에서 가장 작은 값)를 찾아 그 값을 현재 노드에 복사한 다음, 오른쪽 부분 트리에서 중위 후계자를 삭제합니다. 후계자에게는 왼쪽 자식이 없으므로 자식이 최대 하나입니다. 따라서 후계자를 삭제하는 작업은 사례 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 삭제 구현
전체 재귀 삭제는 세 가지 사례를 모두 결합합니다. 값을 비교하여 삭제할 노드를 찾은 다음 적절한 사례를 처리합니다. 각 단계에서 (수정되었을 수도 있는) 루트를 반환하고 이를 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)는 정렬된 순서로 원소를 한 번에 하나씩 반환하며, 평균 시간 복잡도는 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)으로 악화됩니다. 중위 후계자를 찾는 데 오른쪽 부분 트리를 최대 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에서 두 수의 합
두 수의 합 IV는 BST에서 어떤 두 노드의 합이 목표값이 되는지 묻는 문제입니다. 한 가지 방법은 집합을 사용하는 것입니다. 중위 순회 중 값을 집합에 수집하면서 지금까지의 집합에 target - current가 존재하는지 확인합니다. 더 우아한 방법은 순방향 BST 반복자와 역방향 BST 반복자를 동시에 사용하는 것입니다(두 포인터처럼 작동합니다). 이렇게 하면 각 반복자의 스택에 필요한 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를 더 큰 값의 합 트리로 변환
더 큰 값의 합 트리(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빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해를 확인해 보십시오.
단원 요약
이 단원에서는 BST 삭제의 세 가지 사례(리프, 자식 하나, 자식 둘), 자식이 둘인 노드를 삭제하는 중위 후계자 기법, 그리고 BST 반복자와 BST 더 큰 값의 합 트리 같은 깔끔한 재귀 패턴을 배웠습니다. 다음으로 BST의 정확성을 검증하고 중위 순회의 특성을 활용합니다.
자주 묻는 질문
“BST 삭제: 세 가지 경우” 강의는 무료인가요?
네 — “BST 삭제: 세 가지 경우” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“BST 삭제: 세 가지 경우”에서 뭘 배우나요?
중위 후속자를 사용해 리프 삭제, 자식 하나 삭제, 자식 둘 삭제를 처리하고 알고리즘을 처음부터 구현합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“BST 삭제: 세 가지 경우” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- BST 삽입과 검색
- BST 삭제: 세 가지 경우
- BST 검증과 중위 순회 속성
- k번째 최솟값, 구간 합, BST를 정렬 배열로 변환