탐색 트리

탐색 트리(search tree)는 컴퓨터 과학에서 집합 내에서 특정 키를 찾는 데 사용되는 트리 데이터 구조이다. 트리가 탐색 트리로 기능하려면 각 노드의 키가 왼쪽 하위 트리의 키보다 크고 오른쪽 하위 트리의 키보다 작아야 한다.^[1]

탐색 트리의 장점은 트리가 합리적으로 균형을 이루고 있는 경우 탐색 시간이 효율적이라는 것이다. 즉, 양쪽 끝에 있는 잎(leaf)의 깊이가 비슷하다는 것이다. 다양한 탐색 트리 데이터 구조가 존재하며 그 중 일부는 요소의 효율적인 삽입 및 삭제를 허용하며 이러한 작업은 트리 균형을 유지해야 한다.

탐색 트리는 연관 배열을 구현하는 데 자주 사용된다. 탐색 트리 알고리즘은 키-값 쌍의 키를 사용하여 위치를 찾은 다음 애플리케이션은 전체 키-값 쌍을 해당 특정 위치에 저장한다.