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

소개

2원 탐색트리, AVL트리에 대한 14장 짜리 레포트-

목차

1.서론……………………………………………………………… 1
1. 인덱스란?
1-1 인덱스의 특징
1-2 인덱스의 종류

2.본론……………………………………………………………… 2
2. 2원 탐색트리
2-1 2원 탐색트리의 검색
2-2 2원 탐색트리의 삽입
2-3 2원 탐색트리의 삭제
2-4 2원 탐색트리의 성능

3. AVL 트리
3-1 AVL 트리, non-AVL 트리
3-2 AVL 트리의 검색과 삽입
3-3 AVL 트리의 회전

3.결론……………………………………………………………… 13
4. 인덱스에 대한 나의 생각

본문내용

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의 오른쪽 서브트리로 이동하여 계속 탐색

참고자료

· 없음