이진 탐색 트리

왜 배우는가: 이진 탐색 트리는 검색·삽입·삭제를 로그 시간에 처리하는 기본 자료구조이며, 데이터베이스 인덱스와 메모리 집합·맵의 바탕이 되므로 실무와 시험에서 모두 자주 다뤄진다. 정의와 삽입 과정은 1교시 용어형 문항으로 반복 출제되므로 정확한 조건을 외워야 한다.

출제 이력: 제137회 1교시 12번, 제99회 1교시 1번

1. 한 줄 정의와 핵심 키워드

이진 탐색 트리는 각 노드의 왼쪽 서브트리 키는 노드 키보다 작고 오른쪽 서브트리 키는 노드 키보다 큰 규칙을 만족하는 이진 트리다.

• 핵심 키워드: 이진 탐색 트리(BST), 이진 트리, 서브트리, 중위 순회, 탐색 시간 복잡도, 편향 트리, 자가 균형 트리
• 시간 복잡도: 평균 O(log n), 최악 O(n)
• 기본 조건: 키의 유일성(중복 키 허용 여부는 구현·문헌마다 달라 답안에서는 조건을 명시한다)

2. 개념 풀이

쉬운 말로 하면, 값이 정렬된 상태를 트리 모양으로 유지해 두고 한 번 비교할 때마다 찾는 범위를 절반 가까이 줄이는 자료구조다. 이진 탐색 원리를 노드 연결 구조에 옮긴 것이라고 이해하면 된다.

정식 정의는 다음과 같다. 이진 탐색 트리는 이진 트리 중에서 모든 노드 n에 대해 n의 왼쪽 서브트리의 모든 키가 n의 키보다 작고, 오른쪽 서브트리의 모든 키가 n의 키보다 크며, 두 서브트리도 다시 이진 탐색 트리인 트리다. 문헌에 따라 같은 키를 한쪽 서브트리에 허용하기도 하므로, 답안에는 어느 조건을 쓰는지 밝힌다.

• 이진 트리: 모든 노드의 자식이 최대 2개이고 왼쪽·오른쪽 자식이 구분되는 트리다.
• 서브트리: 어떤 노드와 그 자손 전체로 이루어진 작은 트리다. 이진 탐색 트리의 조건은 모든 서브트리에 재귀적으로 적용된다.
• 중위 순회(In-order Traversal): 왼쪽 자식, 노드, 오른쪽 자식 순으로 방문하는 순회다. 이진 탐색 트리에 적용하면 키가 오름차순으로 나온다.
• 편향 트리: 한쪽 방향으로만 자식이 이어진 트리다. 정렬된 순서로 삽입하면 연결 리스트와 같은 모양이 되며, 이때 탐색은 O(n)이다.

3. 등장 배경과 필요성

정렬된 배열은 탐색이 이진 탐색으로 O(log n)이지만, 삽입과 삭제마다 원소를 이동해야 하므로 O(n)이 든다. 연결 리스트는 삽입이 빠르지만 탐색은 O(n)이다. 이진 탐색 트리는 두 요구를 함께 만족시키려는 구조로 등장했다.

• 평균 O(log n) 탐색·삽입·삭제가 가능하다는 점이 핵심 이유다.
• 범위 질의와 근사 질의도 중위 순회나 경로 탐색으로 처리할 수 있어 정렬 배열이 하던 연산을 대부분 유지한다.
• 트리 구조는 노드 단위로 연결되므로 동적으로 크기가 바뀌는 집합·맵, 심볼 테이블 구현에 적합하다.
• 외부 저장장치에서는 한 노드를 한 블록에 맞추기 어려워 이진 탐색 트리를 다분기로 일반화한 B 트리가 주로 쓰인다. 파일 시스템과 데이터베이스 인덱스가 B 트리 계열을 쓰는 이유도 여기에 있다.
• 단점도 분명하다. 삽입 순서에 따라 한쪽으로 기울면 최악 O(n)까지 떨어지며, 그래서 AVL 트리·레드-블랙 트리 같은 자가 균형 기법이 뒤따라 등장했다. 자가 균형 기법의 상세는 다른 절에서 다룬다.