정의
탐색 트리(검색 트리)는 자료 구조의 일종으로, 데이터를 계층적인 트리 구조로 저장하여 효율적인 탐색(검색), 삽입, 삭제 연산을 가능하게 하는 구조를 의미한다. 일반적으로 이진 탐색 트리(Binary Search Tree)가 가장 널리 알려진 형태로, 각 노드의 왼쪽 하위 트리에는 해당 노드보다 작은 값을, 오른쪽 하위 트리에는 큰 값을 가지도록 구성된다.
개요
탐색 트리는 컴퓨터 과학에서 데이터의 동적 관리를 위한 핵심 자료 구조 중 하나로, 정렬된 상태를 유지하면서 데이터를 저장하므로 이진 탐색과 유사한 방식으로 원소를 빠르게 찾을 수 있다. 이 구조는 삽입 및 삭제가 빈번히 일어나는 환경에서 배열 기반의 정렬된 자료 구조보다 효율적일 수 있다. 특히, 이진 탐색 트리는 균형을 유지할 경우 평균적으로 O(log n)의 시간 복잡도로 연산이 수행된다. 그러나 극단적인 경우(예: 정렬된 순서로 데이터를 삽입할 경우) 트리가 편향되어 O(n)의 성능을 보일 수 있으므로, 이를 보완하기 위해 균형 잡힌 트리 구조(예: AVL 트리, 레드-블랙 트리 등)가 개발되었다.
어원/유래
"탐색"은 주어진 데이터 집합에서 특정 값을 찾는 행위를 의미하며, "트리"는 계층 구조를 나타내는 자료 구조를 지칭한다. "탐색 트리"라는 용어는 20세기 중반, 컴퓨터 과학이 발전하면서 자료 구조와 알고리즘 연구가 활발해지면서 자연스럽게 형성된 합성어로 추정된다. 특히, 이진 트리를 이용한 검색 방법이 체계적으로 정립되면서 널리 사용되기 시작하였다. 정확한 최초 사용 시기나 사용자는 공개된 자료에서 확인되지 않는다.
특징
- 계층적 구조: 트리는 루트 노드를 시작으로 자식 노드들이 분기되는 계층적 형태를 가진다.
- 순서 기반 저장: 이진 탐색 트리의 경우, 중위 순회(in-order traversal)를 통해 데이터를 정렬된 순서로 출력할 수 있다.
- 동적 연산 효율성: 삽입, 삭제, 탐색 연산이 비교적 빠르게 이루어지며, 균형 유지 조건이 추가된 변형 구조는 안정적인 성능을 보장한다.
- 메모리 오버헤드: 포인터(링크)를 통해 노드를 연결하므로, 배열에 비해 메모리 사용량이 다소 증가할 수 있다.
관련 항목
- 이진 트리 (Binary Tree)
- 이진 탐색 트리 (Binary Search Tree, BST)
- 균형 이진 탐색 트리 (Balanced BST)
- AVL 트리
- 레드-블랙 트리
- B-트리
- 트라이 (자료 구조)