이진 탐색 트리(BST): 데이터를 빠르게 찾기 위한 최적의 나무 구조

데이터베이스나 검색 엔진에서 수백만 개의 데이터 중 원하는 값을 빛의 속도로 찾아야 할 때, 우리는 딜레마에 빠집니다. '배열(Array)'에 데이터를 정렬해 두면 이진 탐색으로 $O(\log N)$만에 찾을 수는 있지만, 중간에 새로운 데이터를 삽입하거나 삭제할 때 뒤에 있는 데이터를 다 밀어내야 하므로 $O(N)$의 끔찍한 시간이 걸립니다. 반면 '연결 리스트(Linked List)'는 삽입과 삭제는 $O(1)$로 빠르지만, 탐색은 처음부터 다 뒤져야 하므로 $O(N)$이 걸립니다. "이진 탐색의 미친 검색 속도와 연결 리스트의 유연한 삽입/삭제를 하나로 합칠 수는 없을까?" 이 위대한 욕망에서 탄생한 컴퓨터 과학의 걸작이 바로 '이진 탐색 트리(Binary Search Tree, BST)'입니다.

1. BST의 절대 법칙: "왼쪽은 작게, 오른쪽은 크게"

이진 탐색 트리는 모든 노드가 최대 두 개의 자식을 가지는 나무(Tree) 구조입니다. 단, 무작위로 데이터를 매달지 않고 아주 엄격한 단 하나의 황금률을 따릅니다. "어떤 노드를 기준으로 하든, 왼쪽 서브 트리에 있는 모든 값은 나보다 작고, 오른쪽 서브 트리에 있는 모든 값은 나보다 커야 한다."

1-1. 마법 같은 탐색 시뮬레이션

루트 노드에 50이 있고, 우리가 30을 찾는다고 가정해 봅시다.

1. 루트인 50에게 묻습니다. "30은 너보다 작니, 크니?"
2. 50보다 작으므로, 오른쪽 가지는 쳐다볼 필요도 없이 버리고 왼쪽 자식으로 내려갑니다.
3. 단 한 번의 비교로 탐색 범위가 절반으로 뭉텅이로 잘려 나갑니다. 배열의 이진 탐색(Binary Search)과 완벽하게 똑같은 원리로 $O(\log N)$의 탐색 속도를 달성합니다.

2. 융통성 있는 삽입과 삭제

배열과 달리 트리는 데이터들이 물리적으로 연속해서 붙어있지 않고 포인터(선)로만 연결되어 있습니다. 따라서 새로운 숫자 35를 넣고 싶다면, 탐색 규칙에 따라 빈자리를 찾아 내려간 뒤, 그곳에 새로운 노드를 선(포인터) 하나만 연결해 주면 끝납니다. 뒤에 있는 데이터들을 뒤로 밀어낼 필요가 전혀 없어, 삽입과 삭제 역시 트리의 높이인 $O(\log N)$ 만에 깔끔하게 끝납니다.

3. 최악의 시나리오: 뼈대만 남은 트리 (Skewed Tree)

하지만 BST에도 치명적인 맹점이 있습니다. 만약 빈 트리에 10, 20, 30, 40, 50을 순서대로 넣으면 어떻게 될까요? 계속 나보다 크니까 오른쪽으로만 가지가 뻗어나가, 결국 막대기처럼 한쪽으로 치우친 트리(Skewed Tree)가 되어버립니다. 이렇게 되면 탐색 시간이 사실상 선형 탐색과 다를 바 없는 $O(N)$으로 전락합니다. 이 끔찍한 사태를 막기 위해 삽입될 때마다 스스로 균형을 맞추어 트리의 높이를 강제로 $\log N$으로 유지하는 AVL 트리, 레드-블랙 트리(Red-Black Tree) 같은 자가 균형 트리가 현대 프로그래밍 언어의 Map과 Set을 구성하는 핵심 엔진으로 활약하고 있습니다.

[핵심 요약]
1. 이진 탐색 트리(BST)는 부모 노드를 기준으로 왼쪽 자식은 더 작은 값, 오른쪽 자식은 더 큰 값을 배치하는 트리 자료구조입니다.
2. 데이터의 탐색, 삽입, 삭제가 모두 평균적으로 $O(\log N)$이라는 경이로운 밸런스를 자랑합니다.
3. 데이터가 정렬된 채로 삽입될 경우 한쪽으로 치우쳐 $O(N)$으로 성능이 저하되는 단점이 있어, 이를 보완한 레드-블랙 트리 등으로 발전되었습니다.