알고리즘트리구조종류
- 최초 등록일
- 2012.01.01
- 최종 저작일
- 2010.01
- 19페이지/ 한컴오피스
- 가격 3,000원
소개글
컴퓨터 공학 알고리즘 트리 3가지에 대해 명확하게 비교 분석한 글입니다. 그림과 도표까지 매우 보기 쉽게 편집되어 있습니다.
목차
없음
본문내용
Ⅲ. B-tree(Balanced Tree)
가. B-Tree의 정의
○ m-차수 트리의 한 종류로 Balance를 맞춘 Tree
- B-tree는 R.Bayer와 F.Mecreight에 의해 처음 개발되었으며, 탐색 시간의 절약을 위해서 가장
많이 사용되는 자료 구조 중의 하나
- B-트리는 균형된 (Balanced) m-원 탐색 트리로서 효율적인 균형 알고리즘을 제공
나. B-Tree의 특징
○ 루트는 단말 노드가 아니면 2에서 m개의 부분트리를 가짐
○ 중간 노드는 m/2 ~ m개의 널이 아닌(non-null) 노드를 가짐
○ Leaf 노드는 (m/2 - 1) ~ (m-1) 개의 엔트리를 가짐
- 트리에 있는 각 노드는 최대 m개, 최소 m/2개의 종속 트리를 가져야 한다. (근노드와 단노드는 제외)
- 근노드는 최소한 2개의 종속트리를 가져야 한다.(단, 트리가 루트에만 있는 경우 종속 트리가 없음)
- 모든 단 노드는 같은 레벨에 있어야 한다.
- 노드에 있는 키값 개수는 종속 트리의 개수보다 하나 적으며, 최소한 m/2 -1개, 최대 m-1개이다.
차수가 3인 B-tree를 2-3 트리라 하며, 차수가 4인 B-tree를 2-4 트리라 한다.
- 여유 공간이 없는 경우, 삽입을 하게 되면 빈번한 분할 (Split) 현상이 발생함
- 순차 접근시 트리를 Inorder (Left → Right → Root) 운행을 해야 하므로 성능이 저하됨
참고 자료
없음