탐색 트리(영어: search tree)는 컴퓨터 과학 분야에서 사용되는 트리(tree) 데이터 구조의 일종으로, 특정 집합(set) 내에서 원하는 키(key)를 효율적으로 찾기 위해 설계된 자료구조이다. 탐색 트리는 데이터의 저장과 검색, 삽입, 삭제 등의 연산을 지원하며, 각 노드(node) 간의 정렬 규칙을 통해 탐색 효율을 확보한다는 점에서 일반적인 트리 구조와 구별된다.
기본 개념
탐색 트리가 탐색 트리로서 기능하기 위해서는 각 노드의 키가 왼쪽 하위 트리(subtree)에 있는 모든 키보다 크고, 오른쪽 하위 트리에 있는 모든 키보다 작아야 한다는 정렬 규칙을 만족해야 한다. 이러한 규칙 덕분에, 탐색 시 트리의 루트(root)에서 시작하여 값을 비교하면서 왼쪽 또는 오른쪽 자식 노드로 이동하는 방식으로 원하는 키를 찾을 수 있다.
탐색 트리의 주요 장점은 트리가 적절히 균형을 유지하는 경우 탐색 시간이 효율적이라는 점이다. 균형 잡힌 트리에서는 양쪽 끝에 위치한 잎(leaf) 노드들의 깊이가 서로 비슷하게 유지되며, 이 경우 검색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)이 된다. 반면 트리의 균형이 무너진 경우 최악의 상황에서는 O(n)의 시간 복잡도를 보일 수 있다.
주요 유형
탐색 트리의 개념을 구현하는 대표적인 데이터 구조로는 다음과 같은 것들이 있다.
이진 탐색 트리(Binary Search Tree, BST): 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드는 부모 노드보다 작은 키, 오른쪽 자식 노드는 부모 노드보다 큰 키를 가지는 가장 기본적인 형태의 탐색 트리이다.
B-트리(B-tree): 각 노드가 가변적인 수의 하위 트리를 가질 수 있도록 일반화한 탐색 트리이다. 대량의 데이터 블록을 읽는 시스템에 최적화되어 있으며, 데이터베이스 시스템에서 널리 사용된다.
(a,b)-트리: 모든 잎 노드의 깊이가 동일한 탐색 트리로, 각 노드는 최소 a개에서 최대 b개의 자식을 가지는 형태의 트리이다.
삼항 탐색 트리(Ternary Search Tree): 각 노드가 낮은(low), 같은(equal), 높은(high)의 세 가지 자식 노드를 가질 수 있는 탐색 트리로, 문자열 검색에 주로 활용된다.
활용 분야
탐색 트리는 연관 배열(associative array)을 구현하는 데 자주 사용된다. 탐색 트리 알고리즘은 키-값(key-value) 쌍에서 키를 이용하여 저장 위치를 찾아내고, 해당 위치에 전체 키-값 쌍을 저장하는 방식으로 동작한다. 이 외에도 데이터베이스 인덱스, 사전(dictionary) 구현, 정렬된 데이터 관리 등 다양한 분야에서 활용된다.
관련 개념
탐색 트리와 밀접하게 관련된 개념으로는 트라이(trie), 이진 트리(binary tree), 깊이 우선 탐색(depth-first search) 등이 있으며, 트리 균형을 자동으로 유지하는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로는 AVL 트리, 레드-블랙 트리(red-black tree), 스플레이 트리(splay tree) 등이 존재한다.
출처
- 한국어 위키백과 "탐색 트리"
- 영어 위키백과 "Search tree"
- NIST Dictionary of Algorithms and Data Structures, "search tree"
