[자료구조 11] 이진 탐색 트리(BST)

트리는 위에서 아래로 뻗는 계층 구조입니다. 여기에 "빠르게 찾기" 위한 규칙을 하나 더한 특별한 트리가 있습니다. 이진 탐색 트리(binary search tree, 줄여서 BST)는 각 노드가 자식을 최대 둘, 즉 왼쪽과 오른쪽만 가지며, 왼쪽에는 자기보다 작은 값, 오른쪽에는 자기보다 큰 값을 두는 규칙을 지키는 트리입니다. 이 규칙 하나 덕분에 값을 찾을 때 절반씩 후보를 버릴 수 있어 매우 빠릅니다. 직접 만들어 삽입하고 탐색해 보겠습니다.

11.1 이진 탐색 트리의 규칙

보통의 트리는 자식을 몇 개든 가질 수 있었지만, 이진 탐색 트리는 왼쪽 자식과 오른쪽 자식 딱 둘까지만 가집니다. 그리고 값을 넣을 때 규칙이 있습니다. 새 값이 지금 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 내려갑니다. 이 규칙을 모든 노드가 지키기 때문에, 트리 전체가 "왼쪽은 작고 오른쪽은 큰" 정렬된 모양을 이루게 됩니다. 이 성질이 빠른 탐색의 비밀입니다.

왜 이 규칙이 탐색을 빠르게 할까요. 찾는 값이 지금 노드보다 작다면 오른쪽 자식과 그 아래 전부는 볼 필요가 없습니다. 규칙상 그쪽은 모두 더 큰 값뿐이기 때문입니다. 그래서 한 번 비교할 때마다 남은 후보의 절반을 통째로 버릴 수 있습니다. 정렬된 리스트를 반씩 좁혀 가며 찾는 이진 탐색과 똑같은 원리이며, 트리 모양이 그 과정을 자연스럽게 담고 있는 셈입니다.

11.2 값을 넣고 중위순회하기

먼저 노드 하나를 표현할 클래스와, 값을 규칙대로 넣어 주는 클래스를 만듭니다. insert는 루트부터 시작해 값이 작으면 왼쪽, 크면 오른쪽으로 내려가다가 빈자리를 만나면 그 자리에 새 노드를 답니다.

class TNode:
def __init__(self, v):
self.v = v; self.left = None; self.right = None

class BST:
def __init__(self):
self.root = None
def insert(self, v):
if self.root is None:
self.root = TNode(v); return
cur = self.root
while True:
if v < cur.v:
if cur.left is None:
cur.left = TNode(v); return
cur = cur.left
else:
if cur.right is None:
cur.right = TNode(v); return
cur = cur.right
def inorder(self):
out = []
def go(n):
if n:
go(n.left); out.append(n.v); go(n.right)
go(self.root)
return out

bst = BST()
for x in [5, 3, 8, 1, 4, 7, 9]:
bst.insert(x)
print(bst.inorder())

[1, 3, 4, 5, 7, 8, 9]

5를 처음 넣어 루트가 되고, 3은 5보다 작으니 왼쪽, 8은 크니 오른쪽으로 자리를 잡는 식으로 트리가 만들어집니다. 여기서 inorder(중위순회)는 각 노드에서 "왼쪽 먼저, 그다음 자기 자신, 마지막으로 오른쪽" 순서로 방문하는 방법입니다. 왼쪽은 항상 작고 오른쪽은 항상 크다는 규칙 덕분에, 이 순서로 훑으면 넣은 순서가 뒤죽박죽이었어도 저절로 오름차순으로 나옵니다. 삽입은 트리가 균형 잡혀 있으면 평균 O(log n), 전체 순회는 O(n)입니다.

11.3 값이 있는지 탐색하기

이제 이 트리에서 어떤 값이 있는지 찾아보겠습니다. 앞의 BST 클래스에 contains 메서드를 더합니다. 찾는 값이 지금 노드보다 작으면 왼쪽만, 크면 오른쪽만 내려가면 됩니다. 나머지 절반은 볼 필요조차 없습니다.

def contains(self, v):
cur = self.root
while cur:
if v == cur.v:
return True
cur = cur.left if v < cur.v else cur.right
return False

print(bst.contains(7))
print(bst.contains(6))

True
False

7을 찾을 때는 루트 5보다 크니 오른쪽으로, 8보다 작으니 다시 왼쪽으로 내려가 7을 만나 참(True)입니다. 6은 같은 길을 따라가다 빈자리(None)에 닿아 없다는 뜻인 거짓(False)이 나옵니다. 핵심은 매 단계마다 남은 후보가 절반으로 줄어든다는 점입니다. 그래서 트리가 균형 잡혀 있으면 탐색이 O(log n)으로, 백만 개 중에서도 스무 번 남짓이면 답을 냅니다. 다만 값을 이미 정렬된 순서로만 넣으면 트리가 한쪽으로 길게 치우쳐, 최악의 경우 리스트처럼 O(n)까지 느려질 수 있다는 점도 알아 두면 좋습니다.

11.4 절반씩 줄이면 왜 빠른가

탐색이 한 단계마다 후보를 절반으로 줄인다는 말이 얼마나 큰 이득인지 숫자로 확인해 보겠습니다. 어떤 수를 1이 될 때까지 계속 반으로 나누면 몇 번 만에 끝나는지 세어 봅니다. 이것이 곧 균형 잡힌 이진 탐색 트리에서 값을 찾는 최대 단계 수와 같은 계산입니다.

def halving(n):
steps = 0
while n > 1:
n //= 2
steps += 1
return steps
print(halving(1000))
print(halving(1000000))

9
19

천 개는 9번, 백만 개는 겨우 19번이면 1까지 줄어듭니다. 데이터가 천 배로 늘었는데도 단계 수는 두 배 남짓밖에 늘지 않았습니다. 이렇게 "절반씩 줄이기"가 만들어 내는 완만한 증가가 바로 O(log n)이며, 균형 잡힌 이진 탐색 트리의 탐색이 이토록 빠른 이유입니다. 리스트에서 하나씩 뒤지면 백만 개는 최악의 경우 백만 번을 봐야 하는 것과 견주면 그 차이가 실감 납니다.

11.5 정리

이진 탐색 트리는 "왼쪽은 작고 오른쪽은 크다"는 규칙을 지키는 트리입니다. 이 규칙 덕분에 삽입도 탐색도 매 단계 후보를 절반으로 줄여 균형 잡힌 경우 O(log n)의 빠른 속도를 냅니다. 또한 중위순회로 훑으면 별도의 정렬 없이도 값이 오름차순으로 나옵니다. 값이 한쪽으로 치우치면 느려질 수 있다는 약점도 함께 기억하면, 언제 이 구조가 유리한지 판단할 수 있습니다. 오늘 코드를 직접 쳐 보고, 값을 넣는 순서를 바꾸면 트리 모양과 중위순회 결과가 어떻게 달라지는지 확인해 보시기 바랍니다.