검색트리(Search Tree)

검색트리(Search Tree)

검색(search)는 컴퓨터가 가장 많이 하는 작업 중의 하나이다. 검색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업이다. 검색을 위하여 사용되는 자료 구조는 배열, 연결리스트, 트리, 그래프 등 매우 다양할 수 있다.

 

레코드(record)

• 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위
• EX) 사람의 레코드 : 주민번호, 이름, 집주조, 집 전화번호, 휴대폰 번호, 최종 학력, 연소득 등의 정보

필드(field)

• 레코드에서 각각의 정보를 나타내는 부분
• EX) 위 사람의 레코드에서 각각의 정보를 나타내는 부분

검색키(search key 또는 key)

• 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드
• 키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다.

검색 트리( search tree)

• 각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다
• 이를 통해 해당 레코드가 저장된 위치를 알 수 있다