m-원 트리(m-ary Tree)의 정의
컴퓨터 과학에서 m-원 트리(m-ary tree)는 노드(node)들의 집합을 계층 구조로 표현한 트리 자료구조를 말합니다. 각 노드가 최대 m개의 자식을 가질 수 있다는 점이 핵심 특징이며, 다음과 같이 정의됩니다.
- 트리는 루트(root) 노드에서 시작합니다.
- 각 노드는 자신의 자식(child) 노드를 가리키는 포인터 목록을 유지합니다.
- 노드가 가질 수 있는 자식의 수는 m 이하입니다.
배열 기반 구현 방식
일반적인 m-원 트리 구현에서는 크기가 m인 참조(reference) 또는 포인터 배열을 사용하여 자식 노드들을 저장합니다. 여기서 m은 자식 노드 수의 상한선(upper bound)이라는 점에 유의해야 하며, 실제 자식 수는 m보다 작을 수도 있습니다.
m-원 탐색 트리(m-way Search Tree)의 조건
m-원 탐색 트리는 다음 두 조건 중 하나를 만족하는 트리입니다.
a. 트리가 비어 있거나,
b. b개(1 ≤ b < m)의 키 k₁, ... , kb와 서브트리 집합 Ta(a = 0..b)를 포함하는 루트로 구성되며, 아래 성질들을 만족합니다.
- k가 T₀에 속한 키라면, k ≤ k₁ 입니다.
- k가 Ta(0 < a < b)에 속한 키라면, ka ≤ k ≤ ka+1 입니다.
- k가 Tb에 속한 키라면, k > kb 입니다.
- 모든 Ta는 비어 있지 않은 m-원 탐색 트리이거나, 모든 Ta가 빈 트리여야 합니다.
▲ m-원 트리(m-ary tree)의 구조 예시
완전 m-원 트리의 높이
n개의 노드를 가진 완전(complete) m-원 트리의 높이는 ⌈logmn⌉, 즉 logmn의 천장값(ceiling)으로 계산됩니다. 이는 트리의 균형 정도와 탐색 효율을 분석할 때 중요한 기준이 됩니다.
B-트리(B-tree)와의 관계
차수(order)가 m인 B-트리는 m-원 트리의 대표적인 응용 형태로, 데이터베이스와 파일 시스템에서 널리 사용됩니다. B-트리는 다음 조건을 만족해야 합니다.
- 모든 리프(leaf) 노드는 같은 레벨에 위치해야 합니다.
- 루트와 리프를 제외한 모든 노드는 최소 m/2개, 최대 m개의 자식을 가집니다.
- 루트 노드는 최소 2개, 최대 m개의 자식을 가집니다.
이러한 균형 조건 덕분에 B-트리는 트리의 높이를 낮게 유지하며 안정적인 탐색·삽입·삭제 성능을 보장할 수 있습니다.