알고리즘 - 11 이진 검색 트리

레코드

- 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위

 

ex 사람의 레코드

- 주민번호, 이름, 집주소, 집 전화번호 ,직장전화번호, 휴대전화번호, 연소득 등

 

ex 학생의 레코드

- 이름, 학번, 주소, 연락처 등의 정보 포함

 

 

필드

- 레코드에서 각가의 정보를 나타내는 부분

 

ex 학생의 레코드

- 필드 : 이름, 학번, 주소, 연락처

 

키, 검색키

- 다른 레코드와 중복되지 않도록 각 레코드를 대표할수 있는 필드

- 키는 하나의 필드나 두 개 이상의 필드로 이루어 질 수 있음

 

 

 

검색 트리

1. 자료를 저장하고 검색하는데 유용한 자료구조이며 알고리즘

2. 레코드를 트리 모양으로 만들어서 자료를 저장하고 찾음

3. 각 노드가 규칙에 맞도록 하나씩의 키를 가지고 있음

4. 1:n 관계의 비선형 자료구조

5. 계층 관계로 만들어진 계층형 자료구조

 

 

 

검색 트리의 요소

- 노드 node : 트리를 구성하는 원소

- 간선 edge : 노드를 연결하는 선

- 루트 노드 root : 트리 시작 노드

- 부모 노드 parent

- 자식 노드 child

- 형제 노드 sibling : 같은 부모 노드를 가진 자식 노드

- 차수 degree : 자식 노드 수

- 레벨 level : 특정 깊이에 해당하는 노드 집합

- 리프 노드, 단말 노드 : 차수가 0인 노드

 

 

검색 트리의 종류

1. 자식 노드의 개수에 따른 분류

- 이진 검색 트리 : 최대 두 개 이상의 자식 노드

- 다진 검색 트리 : 세 개 이상의 자식 노드로 분기

 

2. 저장되는 장소에 따른 분류

2.1. 내부 검색 트리

- 메인 메모리내에 존재

- 메인 메모리에 있는 모든 키를 수용할 수 있으며 내부 검색 트리 사용

2.2 외부 검색 트리

- 검색 트리가 외부(주로 하드디스크)에 존재

- 메인 메모리에 모든 키를 수용하지 못하면 외부검색트리를 사용

- 디스크 접근 시간이 검색의 효율을 좌우함

 

 

 

 

이진 검색 트리

- 최대 두 개의 자식 노드를 갖는 검색 트리

- 각 노드는 하나씩의 키를 가짐

- 각 노드의 키 값은 다름

- 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두개의 자식을 가짐

- 임의의 노드의 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고 오른쪽 자식의 키 값보다 작음

 

 

이진 검색 트리 검색 방법

1. 키 x를 가진 노드를 검색

2. 트리에 키 x를 가진 노드가 존재하면 해당 노드를 리턴함

3. 존재하지 않으면 NIL을 리턴

 

 

treeSearch(t, x) //t : 서브 트리의 루트 노드, x 검색하고자 하는 키
{
   if (t = NIL or key[t]=x) then return t;
   if (x < key[t])
       then return treeSearch(left[t], x);
       else return treeSearch(right[t], x);

}