탐색 트리

탐색 트리(search tree)는 컴퓨터 과학에서 집합 내에서 특정 키를 찾는 데 사용되는 트리 데이터 구조이다. 트리가 탐색 트리로 기능하려면 각 노드의 키가 왼쪽 하위 트리의 키보다 크고 오른쪽 하위 트리의 키보다 작아야 한다.Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures

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

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

 트리의 유형 
 이진 탐색 트리 

 B 트리 

 (a,b)-트리 

 삼항 탐색 트리 

 같이 보기 
 트라이 (컴퓨팅)
 이진 트리
 깊이 우선 탐색

 각주 


분류:검색 알고리즘