BST 삽입과 검색
재귀 및 반복 방식으로 삽입과 검색을 구현하고 여러 키가 트리를 통과하는 경로를 추적하며, 균형이 맞지 않는 트리의 최악 시간 복잡도를 분석합니다.
BST 삽입과 검색은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
BST 규칙의 정의
이진 탐색 트리는 하나의 불변 조건을 만족합니다. 모든 노드에서 왼쪽 하위 트리의 모든 값은 해당 노드의 값보다 엄격히 작고, 오른쪽 하위 트리의 모든 값은 엄격히 큽니다. 이 순서 규칙은 바로 아래 자식뿐 아니라 전체 하위 트리에서 유지되며, 균형 트리에서 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 검색은 이진 탐색처럼 작동합니다. 대상값을 현재 노드의 값과 비교한 뒤 알맞은 하위 트리를 재귀적으로 탐색합니다. 대상값이 현재 값과 같으면 해당 노드를 반환합니다. 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동합니다. 빈 노드에 도달하면 널을 반환합니다. 시간 복잡도는 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 found반복적 BST 검색
반복적 검색은 호출 스택 오버헤드를 피하므로 운영 코드에서 선호됩니다. 비교 결과에 따라 왼쪽 또는 오른쪽으로 이동하는 포인터 curr를 사용하십시오. 이는 널(찾지 못함), 일치(찾음), 방향 조정이라는 세 가지 경우로 구성된 간단한 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)) # None재귀적 BST 삽입
BST 삽입은 검색과 동일한 왼쪽 또는 오른쪽 판단을 따라 올바른 위치를 찾은 다음, 도달한 첫 번째 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) # 5반복적 BST 삽입
반복적 삽입은 삽입 위치에 도달하기 직전의 마지막 널이 아닌 노드를 추적하기 위해 parent 포인터를 사용합니다. 검색과 같은 방식으로 트리를 내려가면서 부모와 마지막으로 이동한 방향을 기록합니다. 널에 도달하면 부모의 알맞은 쪽에 새 노드를 연결합니다. 빈 트리인 경우(루트가 널인 경우)는 항상 별도로 처리해야 합니다.
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 트리, 레드-블랙 트리)가 존재하는 이유입니다. 면접에서 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에서 최솟값은 항상 가장 왼쪽 노드에 있습니다(널에 도달할 때까지 계속 왼쪽으로 이동). 최댓값은 가장 오른쪽 노드에 있습니다. 이 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 또는 레드-블랙 트리를 직접 구현하거나, 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)인 균형 잡힌 트리를 보장합니다. 각 원소를 한 번씩만 처리하므로 시간 복잡도는 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빠른 확인
이 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
수업 요약
이 수업에서는 BST 규칙(왼쪽 하위 트리는 엄격히 작고 오른쪽 하위 트리는 엄격히 큼), O(h) 시간에 재귀적 및 반복적으로 수행하는 검색과 삽입, 그리고 높이가 n과 같아지는 최악의 경우의 편향된 트리를 배웠습니다. 다음에는 세 가지 경우로 나뉘는 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개 중 1번째 강의입니다.
“BST 삽입과 검색” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.