트리(Tree) 자료구조를 공부하다 보면 가장 많이 듣게 되는 용어가 바로 '이진 트리(Binary Tree)'입니다. 그런데 조금 더 깊이 들어가면 '이진 탐색 트리(Binary Search Tree, BST)'라는 용어가 등장하면서 혼란이 시작됩니다. "그냥 똑같은 이진 트리 아닌가? 뭐가 다른 거지?"라고 생각하기 쉽지만, 이 둘 사이에는 데이터 검색 속도를 O(n)에서 O(log n)으로 바꿔버리는 결정적인 규칙의 차이가 존재합니다. 개발자 면접에서도 단골로 출제되는 이 두 개념의 미묘하지만 강력한 차이점을 완벽하게 정리해 드리겠습니다.
1. 이진 트리 (Binary Tree): 뼈대와 구조
이진 트리는 단순히 '구조적 형태'를 정의하는 용어입니다. 데이터가 어떻게 정렬되어 있는지, 어떤 값을 어디에 넣어야 하는지에 대한 규칙은 전혀 없습니다. 오직 모양에 대한 제약 조건만 존재합니다.
1-1. 정의와 특징
이진 트리의 정의는 간단합니다. "모든 노드가 최대 2개의 자식(왼쪽, 오른쪽)만을 가질 수 있는 트리"입니다. 자식이 없어도 되고, 하나만 있어도 되고, 둘 다 있어도 되지만, 셋 이상은 절대 불가능합니다.
- 데이터 정렬 없음: 루트 노드가 10인데, 왼쪽 자식에 100이 있든 오른쪽 자식에 1이 있든 상관없습니다. 그냥 자식이 둘 이하면 무조건 이진 트리입니다.
- 탐색 속도: 규칙 없이 데이터가 뒤죽박죽 섞여 있기 때문에, 특정 값을 찾으려면 모든 노드를 하나씩 다 방문해야 합니다. 즉, 배열과 다를 바 없는 O(n)의 느린 속도를 가집니다.
2. 이진 탐색 트리 (BST): 효율을 위한 엄격한 규칙
이진 탐색 트리(BST)는 이진 트리의 형태를 가지면서, 데이터를 효율적으로 찾기 위해 '엄격한 대소 관계 규칙'을 추가한 자료구조입니다. 이 규칙 덕분에 우리는 스무고개 하듯이 데이터를 빠르게 찾을 수 있습니다.
2-1. BST의 3가지 절대 규칙
이진 탐색 트리가 되기 위해서는 다음 조건을 반드시 만족해야 합니다.
- 왼쪽 자식 노드의 값은 부모 노드의 값보다 무조건 작아야 합니다. (Left < Parent)
- 오른쪽 자식 노드의 값은 부모 노드의 값보다 무조건 커야 합니다. (Parent < Right)
- 왼쪽과 오른쪽 서브 트리(Subtree)들도 모두 이 규칙을 만족해야 합니다.
2-2. 탐색의 마법: O(log n)
이 규칙이 왜 중요할까요? 만약 우리가 숫자 '30'을 찾는다고 가정해 봅시다. 1. 루트 노드가 '50'입니다. 2. 우리가 찾는 30은 50보다 작습니다. 3. 그렇다면 오른쪽 가지는 쳐다볼 필요도 없이, 왼쪽으로만 가면 됩니다. (탐색 범위 절반 삭제!) 이처럼 한 번 비교할 때마다 찾아야 할 데이터의 양이 절반씩 뚝뚝 떨어지기 때문에, 데이터가 아무리 많아도 매우 빠르게 원하는 값을 찾아낼 수 있습니다.
3. BST의 치명적 약점: 편향 트리 (Skewed Tree)
하지만 이진 탐색 트리에도 약점이 있습니다. 만약 데이터가 `1, 2, 3, 4, 5...` 순서대로 들어오면 어떻게 될까요? 규칙에 따라 계속 오른쪽에만 자식이 달리는 일자 모양의 막대기가 되어버립니다.
이렇게 한쪽으로만 쏠린 트리를 편향 트리라고 합니다. 이 경우 트리의 장점인 '절반 버리기'가 불가능해져서, 결국 연결 리스트처럼 하나씩 다 뒤져야 하는 O(n)의 최악의 성능을 보이게 됩니다. 이 문제를 해결하기 위해 트리의 균형을 스스로 맞추는 'AVL 트리'나 'Red-Black 트리' 같은 고급 자료구조가 등장하게 되었습니다.
4. 요약: 언제 무엇을 쓰는가?
- 이진 트리: 단순히 데이터를 계층적으로 표현하거나 구조만 필요할 때 사용합니다. (예: 수식 트리)
- 이진 탐색 트리: 데이터의 검색(Search), 삽입, 삭제가 빈번하게 일어나는 경우 사용합니다. 데이터베이스의 인덱싱 원리가 바로 이것입니다.
1. 이진 트리는 자식이 최대 2개인 구조 그 자체를 의미하며, 정렬 규칙이 없어 탐색이 느립니다.
2. 이진 탐색 트리(BST)는 "왼쪽 < 부모 < 오른쪽"이라는 규칙을 통해 O(log n)의 고속 탐색을 보장합니다.
3. 데이터가 정렬된 상태로 들어오면 편향 트리가 되어 성능이 저하될 수 있으므로 주의해야 합니다.