한양과기고 에듀테크 수업도구 대시보드

비교 한 번에 후보의 절반을 버리는 자료구조

이진 탐색 트리(BST)는 각 노드가 최대 두 자식을 갖고, 왼쪽 서브트리의 값은 모두 나보다 작고, 오른쪽 서브트리의 값은 모두 나보다 크다는 규칙을 지키는 트리다. 이 규칙 덕분에 찾는 값과 현재 노드를 한 번 비교할 때마다 남은 후보의 절반을 통째로 버릴 수 있다. 아래에서 숫자를 직접 넣고 검색해 보며 경로가 어떻게 갈라지는지 확인해 보자.

1 세 가지 규칙

왼쪽은 작게

어떤 노드의 왼쪽 서브트리에 있는 모든 값은 그 노드보다 작다.

오른쪽은 크게

오른쪽 서브트리에 있는 모든 값은 그 노드보다 크다.

재귀적으로 성립

이 규칙은 루트뿐 아니라 모든 서브트리에서도 똑같이 성립한다.

2 직접 만들어 보는 BST

트리가 비어 있다. 숫자를 넣어 루트부터 만들어 보자.

노드 수: 0 트리 높이: 0 마지막 검색 비교 횟수: - 같은 개수를 한 줄로 훑을 때 최악: -

순회 결과가 여기 표시된다.

# 삽입 — 규칙을 지키며 내려갈 자리를 찾는다 def insert(node, key): if node is None: return Node(key) # 빈 자리에 새 노드 if key < node.key: node.left = insert(node.left, key) # 작으면 왼쪽으로 elif key > node.key: node.right = insert(node.right, key) # 크면 오른쪽으로 return node # 검색 — 매 비교마다 한쪽 서브트리를 통째로 버린다 def search(node, key): while node and node.key != key: node = node.left if key < node.key else node.right return node

3 왜 빠른가 — 그리고 언제 느려지는가

O(log n)

균형 잡힌 트리에서
검색·삽입·삭제

O(n)

한쪽으로 치우친 트리
(정렬된 값을 순서대로 삽입)

O(n)

중위 순회로
전체를 정렬 출력

높이가 h인 트리에서 검색은 최대 h번만 비교한다. 트리가 균형 잡혀 있으면 h ≈ log₂ n 이라서 100만 개 중에서도 약 20번이면 찾는다. 하지만 1, 2, 3, 4, 5… 처럼 이미 정렬된 값을 순서대로 넣으면 트리가 오른쪽으로만 길게 뻗어 사실상 연결 리스트가 되고 검색이 O(n)으로 느려진다. 위 시뮬레이터에서 랜덤 7개와 오름차순 삽입의 트리 높이를 비교해 보자. 이 문제를 자동으로 막으려고 AVL 트리, 레드-블랙 트리 같은 자가 균형 트리가 나왔고, C++ std::map, 자바 TreeMap, 대부분의 DB 인덱스가 이 계열을 쓴다.

4 자주 나오는 질문

💡 해시테이블이 O(1)인데 BST는 왜 쓰나?

해시테이블은 "이 키가 있냐/없냐"는 빠르지만 순서를 잃는다. BST는 중위 순회하면 값이 정렬된 채로 나오고, "30 이상 50 이하 범위"나 "가장 작은 값", "바로 다음으로 큰 값" 같은 범위·순서 질의를 잘한다. 그래서 DB 인덱스는 해시가 아니라 트리(B-트리)를 주로 쓴다.

💡 노드를 삭제할 때 자식이 둘이면 어떻게 하나?

지울 노드 자리에 오른쪽 서브트리의 가장 작은 값(또는 왼쪽 서브트리의 가장 큰 값)을 가져와 덮어쓴다. 그 값은 정의상 지울 노드 바로 다음 순서라서, 옮겨도 BST 규칙이 그대로 유지된다. 옮겨온 자리의 원래 노드는 자식이 최대 하나뿐이라 쉽게 정리된다.

💡 "이진 탐색"과 "이진 탐색 트리"는 같은 건가?

원리는 같다(절반씩 버리기). 이진 탐색은 정렬된 배열에 인덱스로 접근해서 하고, 중간에 값을 넣고 빼기가 O(n)으로 비싸다. 이진 탐색 트리는 포인터로 연결되어 있어 삽입·삭제가 O(log n)으로 싸지만, 배열처럼 메모리가 연속이 아니라 캐시 효율은 떨어진다.

💡 같은 값을 두 번 넣으면?

구현하기 나름이다. 위 시뮬레이터는 중복을 무시한다(넣어도 트리가 안 바뀜). 어떤 구현은 중복 개수를 카운트로 저장하고, 어떤 구현은 "같으면 오른쪽" 같은 규칙을 정해 허용하기도 한다.