다방향 트리란?
다방향 트리(Multiway Tree)는 하나의 노드가 두 개 이상의 자식 노드를 가질 수 있는 트리 구조를 의미합니다. 앞서 살펴본 이진 트리(Binary Tree)가 각 노드당 최대 2개의 자식만 가질 수 있는 것과 달리, 다방향 트리는 자식 노드의 개수에 제한이 없습니다.
만약 다방향 트리의 각 노드가 가질 수 있는 자식의 최대 개수가 m개라면, 이 트리를 차수(order)가 m인 다방향 트리, 즉 m-원 트리(m-way tree)라고 부릅니다.
m-원 트리의 노드 구조
기존에 학습한 다른 트리들과 마찬가지로, m-원 트리의 각 노드는 다음과 같은 요소들로 구성됩니다.
- m-1개의 키(key) 필드
- 자식 노드를 가리키는 포인터들
즉, 노드가 저장할 수 있는 키의 개수보다 자식 포인터의 개수가 항상 하나 더 많은 구조입니다.
위 그림: 차수가 5인(5-way) 다방향 트리의 예시
m-원 탐색 트리(m-way Search Tree)란?
m-원 트리를 보다 효율적으로 처리하기 위해서는 각 노드 내부의 키에 일정한 제약 조건이나 순서 규칙을 부여하는 것이 유용합니다. 이러한 규칙이 적용된 트리를 차수가 m인 다방향 탐색 트리(m-way search tree)라고 합니다.
정의에 따르면, m-원 탐색 트리는 다음 조건들을 반드시 만족해야 하는 m-원 트리입니다.
- 각 노드는 최대 m개의 자식과 m-1개의 키 필드를 가질 수 있습니다.
- 각 노드 내부의 키들은 오름차순으로 정렬되어 있어야 합니다.
- 첫 번째부터 j번째까지의 자식 서브트리에 속한 모든 키는 j번째 키보다 작아야 합니다.
- 마지막 m-j개의 자식 서브트리에 속한 모든 키는 j번째 키보다 커야 합니다.
정리
다방향 트리는 이진 트리를 확장한 개념으로, 하나의 노드가 여러 개의 키와 자식을 관리할 수 있어 데이터 검색 경로의 깊이를 줄일 수 있습니다. 이러한 구조는 특히 대용량 데이터베이스나 파일 시스템에서 활용되는 B-트리(B-tree) 등의 기반이 되는 중요한 자료구조입니다.