이진탐색트리 (Binary Search Tree)

한 줄 정의: 각 노드마다 왼쪽엔 더 작은 값, 오른쪽엔 더 큰 값만 두어 빠르게 찾고 정렬할 수 있게 만든 나무 모양의 자료구조입니다.

쉽게 풀면

영어사전에서 단어를 찾을 때를 생각해봅시다. 처음부터 한 장씩 넘기지 않고, 중간을 펼쳐서 찾는 단어가 그보다 앞인지 뒤인지 판단한 뒤 범위를 절반씩 줄여가며 찾습니다. 이진탐색트리는 이 방식을 데이터 구조로 만든 것입니다. 트리의 맨 위(루트)에 값 하나를 두고, 그보다 작은 값은 모두 왼쪽 가지로, 큰 값은 모두 오른쪽 가지로 내려보냅니다. 이렇게 정렬된 구조 덕분에 값을 찾을 때마다 후보를 절반씩 줄여나갈 수 있어, 데이터가 아무리 많아도 비교적 적은 횟수만에 원하는 값을 찾을 수 있습니다.

왜 중요한가

이진탐색트리는 정렬된 데이터를 빠르게 검색·삽입·삭제할 수 있게 해주는 가장 기본적인 자료구조 중 하나로, 데이터베이스 인덱스, 파일 시스템, 메모리 할당기, 검색 엔진 등 대량의 데이터를 다루는 시스템 전반의 근간이 됩니다. 그래서 알고리즘·자료구조 논문뿐 아니라 데이터베이스, 컴퓨터 구조, 네트워킹 분야 논문에서도 성능 비교의 기준선(baseline)으로 자주 등장합니다. 균형을 유지하는 변형 구조들이 계속 연구되는 이유도, 이 트리가 다른 여러 고성능 자료구조의 설계 출발점 역할을 하기 때문입니다.

논문에서는 이렇게 쓰입니다

"제안한 인덱싱 기법은 균형 이진탐색트리(balanced BST)를 기반으로 하여 평균 O(log n)의 검색 시간을 보장한다."

이 문장은 데이터가 많아져도 트리가 한쪽으로 치우치지 않게 균형을 유지하면, 검색에 걸리는 시간이 데이터 양의 로그(log)에 비례할 정도로 빠르다는 뜻입니다.

"본 연구에서는 공간 데이터를 효율적으로 질의하기 위해 이진탐색트리 기반의 인메모리 인덱스를 설계하고, 기존 해시 인덱스 대비 범위 질의(range query) 성능을 비교하였다."

정렬된 순서를 그대로 유지하는 이진탐색트리의 특성 덕분에, 특정 값 하나가 아니라 일정 범위에 속하는 데이터를 한꺼번에 찾아야 하는 상황에서 유리하다는 점을 활용한 연구입니다.

"임베디드 시스템의 제한된 메모리 환경에서는 균형 이진탐색트리의 삽입·삭제 시 발생하는 재조정(rebalancing) 비용이 전체 응답 시간에 미치는 영향을 무시할 수 없다."

자원이 넉넉하지 않은 시스템을 다루는 논문에서는 트리의 검색 속도뿐 아니라, 균형을 맞추는 과정 자체가 소모하는 연산 비용까지 함께 고려한다는 것을 보여주는 예문입니다.

조금 더 깊게 보면

일반적인 이진탐색트리는 최악의 경우(예: 이미 정렬된 데이터를 순서대로 삽입하는 경우) 한쪽으로 치우쳐 선형 구조에 가까워지므로, 논문에서는 대체로 균형을 자동으로 유지하는 변형을 다룹니다. AVL 트리는 삽입·삭제마다 각 노드의 좌우 서브트리 높이 차이를 확인해 회전(rotation) 연산으로 균형을 맞추고, 레드-블랙 트리는 노드에 색을 부여하는 규칙을 이용해 상대적으로 느슨하지만 더 적은 재조정으로 균형에 가까운 상태를 유지합니다. 이 외에도 삽입·검색 패턴에 따라 스스로 구조를 조정하는 스플레이 트리(splay tree)처럼, 자료 접근 패턴에 특화된 변형들도 함께 언급되는 경우가 많습니다.

주의할 점

이진탐색트리는 데이터를 넣는 순서에 따라 한쪽으로 길게 치우칠 수 있는데, 이 경우 트리가 아니라 사실상 일렬로 늘어선 목록처럼 동작해 검색 속도가 크게 느려집니다. 이런 문제를 막으려면 삽입할 때마다 균형을 맞추는 알고리즘(AVL 트리, 레드-블랙 트리 등)을 함께 쓰는 경우가 많으며, 이때의 성능은 시간복잡도와 빅오 표기법으로 표현합니다.