트리 자료구조를 공부하다 보면 가장 많이 마주치는 단어가 '이진 트리(Binary Tree)'입니다. 그런데 곧이어 '이진 탐색 트리(Binary Search Tree, BST)'라는, 이름이 묘하게 비슷한 개념이 등장합니다. 많은 초보자가 "그냥 둘 다 똑같은 트리 아니야?"라고 생각하고 넘어가지만, 이 둘은 '단순한 저장'과 '효율적 검색'이라는 목적의 차이만큼이나 큰 성능 차이를 보입니다. 오늘은 이진 트리의 형태에 '규칙'을 하나 더해 탐색 속도를 빛의 속도로 만든 BST의 비밀을 파헤쳐 보겠습니다.
1. 이진 트리 (Binary Tree): 형태의 제약
이진 트리는 트리의 '모양(Shape)'을 정의하는 용어입니다. 규칙은 아주 간단합니다. "모든 부모 노드는 최대 2개의 자식(왼쪽, 오른쪽)만 가질 수 있다." 자식이 3개 이상인 노드가 단 하나라도 있으면 이진 트리가 아닙니다. 하지만 데이터가 어떤 순서로 들어있는지는 신경 쓰지 않습니다. 루트 노드가 10인데 왼쪽에 100이 있든, 오른쪽에 1이 있든, 형태만 맞으면 모두 이진 트리입니다.
- 한계: 규칙 없이 데이터가 뒤죽박죽 섞여 있으므로, 원하는 데이터를 찾으려면 전체를 다 뒤져야 합니다(O(n)). 즉, 검색 용도로는 배열과 다를 바가 없습니다.
2. 이진 탐색 트리 (BST): 효율을 위한 규칙
이진 탐색 트리는 이진 트리의 형태를 가지면서, 데이터를 빨리 찾기 위해 '엄격한 대소 관계 규칙'을 적용한 자료구조입니다.
2-1. BST의 3가지 절대 규칙
- 왼쪽 자식 노드의 값은 무조건 부모보다 작아야 합니다.
- 오른쪽 자식 노드의 값은 무조건 부모보다 커야 합니다.
- 모든 하위 서브 트리(Subtree)도 이 규칙을 만족해야 합니다.
2-2. 탐색의 마법: 업다운(Up-Down) 게임
이 규칙이 적용되면 데이터 검색은 '스무고개' 게임이 됩니다. 예를 들어 숫자 `50`이 루트인 트리에서 `30`을 찾는다고 해봅시다. 1. `30`은 `50`보다 작습니다. -> 오른쪽은 쳐다볼 필요도 없습니다. 왼쪽으로 갑니다. 2. 왼쪽 자식이 `25`입니다. `30`은 `25`보다 큽니다. -> 왼쪽은 버립니다. 오른쪽으로 갑니다. 3. 이렇게 한 번 비교할 때마다 탐색 범위가 절반씩 뚝뚝 떨어져 나갑니다. 결과적으로 데이터가 10억 개가 있어도 약 30번의 비교만으로 값을 찾을 수 있습니다. 시간 복잡도는 O(log n)입니다.
3. BST의 치명적 약점: 편향 트리 (Skewed Tree)
"그럼 무조건 BST가 최고네?"라고 할 수 있지만, 약점이 있습니다. 만약 데이터가 `1, 2, 3, 4, 5` 순서대로 들어오면 어떻게 될까요? 규칙에 따라 계속 오른쪽 자식으로만 연결되어, 나무가 아니라 오른쪽으로 기울어진 막대기 모양이 됩니다. 이렇게 한쪽으로 쏠린 트리를 편향 트리라고 합니다. 이 경우 탐색 범위를 절반으로 줄일 수 없게 되어, 결국 연결 리스트처럼 하나씩 다 확인해야 하는 O(n)의 최악의 성능을 보입니다.
3-1. 해결책: 균형 이진 탐색 트리
이 문제를 해결하기 위해 데이터가 추가/삭제될 때마다 트리의 균형을 자동으로 다시 맞추는 AVL 트리나 Red-Black 트리 같은 고급 자료구조가 개발되었습니다. (자바의 HashMap이나 C++의 Map이 내부적으로 이 방식을 사용합니다.)
1. 이진 트리는 자식이 최대 2개인 구조를 말하며, 정렬 규칙이 없어 탐색에는 비효율적입니다.
2. 이진 탐색 트리(BST)는 "왼쪽 < 부모 < 오른쪽" 규칙을 통해 O(log n)의 빠른 검색을 보장합니다.
3. 데이터가 정렬된 채로 입력되면 편향 트리가 되어 성능이 저하될 수 있으니 주의해야 합니다.