[공학]트리에 관해서

소개글

트리에 관해서
간단하게 정리한 자료입니다. ^^*

목차

1. B트리
2. AVL 트리
3. 2-3트리

본문내용

1. B트리
(1)B-트리
인덱스를 조직하는 방법으로 가장 많이 사용되는 구조는 B-트리이다.
B-트리는 균형된 m-원 트리로서 효율적인 균형알고리즘을 제공한다.
차수가 m인 B-트리는 다음과 같은 특성을 가진 m-원 탐색 트리로 정의할수 있다.

① 루트와 리프를 제외한 모든 노드는 최소 [m/2], 최대 m개의 서브 트리를 갖는다.
② 루트는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
③ 모든 리프는 같은 레벨에 있다.
④ 리프가 아닌 노드의 키값 수는 그 노드의 서브트리 수보다 하나 적으며, 각 리프 노드는 최소[m/2]-1개, 최대 m-1개의 킷값을 갖는다.
⑤ 한 노드 안에 있는 키값들은 오름차순을 유지한다.

첫 번째 특성은 트리의 각 노드가 적어도 반 이상이 차있어야 한다는 것을 나타내고 있다. 이것은 트리의 높이가 높아져 탐색 속도가 늦어지는 것을 방지한다.
두 번째 특성은 트리가 처음부터 분기해야 한다는 것을 나타내며, 세 번째 특성은 트리가 균형을 유지해야 한다는 것을 의미하고 있다. 네 번째 특성은 각 노드의 레코드 수에 대한 제약을 나타내고 있고 마지막 다섯 번째 특성은 m-원 탐색 트리라는 것을 나타낸다.
일반적으로 차수가 m인 B-트리의 노드 구조는 m-원 탐색 트리의 노드(그림)와 같다.
노드 안에 표시된 각 킷값(Ki)은 그 래코드가 실제 저장되어 있는 데이터 파일에 대한 주소도 포함하고 있다고 이해하여야 한다.
m P₁ K₁ P₂ K₂ P₃...Pm-1Km-1Pm
차수가 m인 B-트리의 노드구조
그림은 차수가 3인 B-트리의 한 예를 표시한 것이다. 여기에서는 편의상 킷값만을

참고 자료

없음