알고리즘트리구조종류

소개글

컴퓨터 공학 알고리즘 트리 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) 운행을 해야 하므로 성능이 저하됨

참고 자료

없음