2원 탐색트��, AVL트�� 레포트

1. 인덱스란?


1-1 인덱스의 특징
탐색 조건에 따라 파일의 레코드들에 대한
효율적 접근을 가능하게 해 준다.
(레코드 키 값, 레코드 주소(포인터))를
쌍으로 체계적으로 모아 놓은 것.


1-2 인덱스의 종류
1)키에 따른 인덱스
- 기본(primary) 인덱스: 기본 키를 포함한 인덱스
- 보조(secondary) 인덱스: 기본 인덱스 이외의 인덱스

2)파일 조직에 따른 인덱스
- 집중(clustered) 인덱스: 파일에 대한 인덱스의
- 엔트리 순서왿� 동일하게 유지하도록 구성된 인덱스
- 비 집중(unclustered index) 인덱스: 집중형태가 아닌 인덱스

3)데이터 범위에 따른 인덱스
- 밀집(dense) 인덱스: 데이터 레코드 하나에 대해 하나의
- 인덱스 엔트리가 만들어지는 인덱스. 역 인덱스라고도 부름
- 희소(sparse) 인덱스: 데이터 파일의 레코드 그룹 또는
- 데이터 블록에 하나의 엔트리가 만들어지는 인덱스

2. 2원 탐색 트리

1)이진트리(binary tree)
유한한 수의 노드를 가진 트리
왼쪽 서브트리왿� 오른쪽 서브트리로 구성


2)2원 탐색 트리
*공백이 아닌 이원 탐색 트리의 성질
1]모든 노드는 상이한 키 값을 갖는다.
2]루트 노드 Ni의 왼쪽 서브트리(Left(Ni))에 있는
모든 노드의 키 값은 루트 노드의 키 값보다 작다.
3]루트 노드 Ni의 오른쪽 서브트리(Right(Ni))에 있는
모든 노드의 키 값은 루트 노드의 키 값보다 크다.
4]왼쪽 서브트리왿� 오른쪽 서브트리는 모두 이원 탐색 트리이다.

2-1 2원 탐색트��의 검색


*루트 Ni, 키 값 K인 노드 검색 과정
1]트리가 공백: 검색은 노드를 찾지 못하고 실패, 종료
2]K=Ki: 노드 Ni가 원하는 노드
3]K<Ki: Ni의 왼쪽 서브트리를 검색
4]K>Ki: Ni의 오른쪽 서브트리를 검색

2-2 2원 탐색트��의 삽입

*루트 Ni인 이원 탐색 트리에 키 값 K인 노드를 삽입
1]트리가 공백 : K를 루트 노드로 삽입
2]K=Ki : 트리에 값은 키 값이 존재하므로 삽입을 거부
3]K<Ki : Ni의 왼쪽 서브트리로 이동하여 계속 탐색
4]K>Ki : Ni의 오른쪽 서브트리로 이동하여 계속 탐색