검색어 입력폼

b_tree

저작시기 2007.05 |등록일 2008.02.25 한글파일한글 (hwp) | 44페이지 | 가격 4,000원

소개글

컴퓨터공학-파일구조 B_tree 대한 정의와 관련한 모든 내용과 소스 수록한 리포트
총 페이지 (44page)

목차

1. 문제정의

2. 입출력 설계

3. 알고리즘

4. 결과화면

5. 문제점

6. 실험 후 소감

[첨부한 소스코드]

본문내용

1. 문제정의

◎실험 주제 : B_tree

◎ B-tree의 어원
Bayer와 McCreight 두 제안자 중 한사람인 Bayer의 이름을 따서 명명되어진 B_tree는 m원 트리가 최고의 효율을 갖기 위해 균형을 유지해야 하는데, 이러한 균형 m원 트리의 한 종류를 말한다.

◎ B_tree의 정의
가. B 트리는 노드가 없거나 1이상의 높이를 갖는 m원 탐색트리이다.
나. Root 노드는 최소한 2개의 자식노드가 있다. 따라서 Root 노드는 적어도 1개의 값을 갖는다.
다. Root 노드를 제외하고 터미널 토드가 아닌, 즉 Si ≠ 0 인 노드들은 최소한 [m/2]개의 자식노드를 가지고 [m/2] - 1개의 값을 갖는다. ([x]는 x의 천청 함수의 값.)
라. 모든 단말노드, 즉 Si = 0을 만족하는 노드는 같은 레벨에 있다.

◎ B_tree 출현
가. 이진트리의 문제점
-좌우 균형이 맞지 않으면 비효율적이다.
나. Balanced TREE
- 삽입/삭제 시 필요하면 스스로 정렬
- AVL 2-3-4, Red-Black, B_TREE
- 항상 0(logN)의 검색성능

◎ B_tree 규칙 1
(1) 노드 내의 DATA가 N개 있으면 그 노드의 자식 노드의 수는 N+1
(2) 노드 내의 DATA는 정렬되어 있어야 한다.
(3) 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.
◎ B_tree 규칙 2
Root는 적어도 2개 이상의 chile를 가진다.
Root를 제외한 모든 노드는 적어도 m/2의 최소 키 값을 가진다.
ex> 5차 B-tree
- 하나의 노드 내에서 최소 2개 이상의 값을 가진다.
다운로드 맨위로