알고리즘...28

검색 트리

저장된 데이터를 빠른 시간에 검색하기 위해 트리를 사용하는 검색 알고리즘이다.

 

- 검색 트리의 요소

• 레코드 여러 개의 필드로 구성되는 개체의 모든 정보가 저장된 구조
  
  • ex) 사람의 레코드: 주민 번호, 이름, 집 주소, 직장 주소, 집 전화번호 등이 포함될 수 있다.
• 필드 레코드의 각 정보를 나타내는 부분
• 검색 키(또는 키) 다른 레코드와 중복되지 않고 레코드를 대표할 수 있는 필드

 

- 검색 트리의 종류

• 자식의 수에 따른 분류
  • 이진 검색 트리 최대 두 개의 자식 노드를 가지는 트리
  • 다진 검색 트리 세 개 이상의 자식 노드를 가지는 트리
• 저장되는 장소에 따른 분류
  • 내부 검색 트리 메인 메모리 내에 모든 데이터가 존재하는 트리
  • 외부 검색 트리 디스크에 저장된 상태로 검색을 진행하는 트리
• 검색 키가 포함하는 필드 수에 따른 분류
  • 일차원 검색 트리 필드 하나를 검색 키로 사용하는 트리
  • 다차원 검색 트리 두 개 이상의 필드를 검색 키로 사용하는 트리

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘