인터벌 트리(Interval Tree)는 구간(간격) 정보를 저장하기 위한 정렬된 트리 자료구조입니다. 이 자료구조의 핵심 장점은 특정 구간이나 점과 겹치는 모든 구간을 효율적으로 탐색할 수 있다는 점입니다. 일반적인 이진 탐색 트리를 확장한 형태로, 각 노드는 구간 정보와 함께 해당 서브트리 내 최댓값(max)을 추가로 관리합니다.
아래에서는 C++를 이용해 인터벌 트리를 직접 구현하는 방법을 단계별로 살펴보겠습니다.
알고리즘 개요
1. insert() — 새 노드 삽입
시작
insert() 함수는 새 노드를 트리에 삽입하는 데 사용됩니다.
트리가 비어 있다면, 새 노드가 루트가 됩니다.
루트 구간의 low 값(하한값)을 기준으로 비교합니다.
새 구간의 low 값이 루트의 low 값보다 작으면 왼쪽 서브트리로 이동합니다.
그렇지 않으면 오른쪽 서브트리로 이동합니다.
필요한 경우, 조상 노드의 max 값을 갱신합니다.
종료2. intervalFind() — 구간 검색
시작
intervalFind() 함수는 인터벌 트리에서 주어진 구간 i를 검색합니다.
트리가 비어 있으면 null을 반환합니다.
주어진 구간이 루트와 겹친다면
루트의 구간을 반환합니다.
루트의 왼쪽 자식이 존재하고, 왼쪽 자식의 max 값이
주어진 구간의 low 값보다 크거나 같다면,
왼쪽 서브트리와 겹칠 가능성이 있으므로 왼쪽을 탐색합니다.
그 외의 경우
오른쪽 서브트리만 겹칠 수 있으므로 오른쪽을 탐색합니다.
종료예제 코드
#include <iostream>
using namespace std;
// 구간(interval) 변수 선언
struct Interval {
int l, h;
};
// 노드 선언
struct ITNod {
Interval *i;
int max;
ITNod *l, *r;
};
// 새 노드 생성 함수
ITNod * newNode(Interval i) {
ITNod *t = new ITNod;
t->i = new Interval(i);
t->max = i.h;
t->l = t->r = NULL;
return t;
}
ITNod *insert(ITNod *r, Interval i) {
if (r == NULL)
return newNode(i);
int l = r->i->l;
if (i.l < l)
r->l = insert(r->l, i);
else
r->r = insert(r->r, i);
// 조상 노드의 max 값 갱신
if (r->max < i.h)
r->max = i.h;
return r;
}
// 두 구간이 겹치는지 확인하는 함수
bool Overlap(Interval i1, Interval i2) {
if (i1.l <= i2.h && i2.l <= i1.h)
return true;
return false;
}
// 주어진 구간과 겹치는 구간을 검색하는 함수
Interval *intervalFind(ITNod *root, Interval i) {
if (root == NULL)
return NULL;
if (Overlap(*(root->i), i))
return root->i;
if (root->l != NULL && root->l->max >= i.l)
return intervalFind(root->l, i);
return intervalFind(root->r, i);
}
// 중위 순회(inorder traversal) 수행
void inorder(ITNod *root) {
if (root == NULL)
return;
inorder(root->l);
cout << "[" << root->i->l << ", " << root->i->h << "]" << " max = " << root->max << endl;
inorder(root->r);
}
int main(int argc, char **argv) {
Interval ints[] = { { 5, 20 }, { 6, 7 }, { 3, 4 }, { 67, 26 }, { 3, 4 } };
int n = sizeof(ints) / sizeof(ints[0]);
ITNod *root = NULL;
for (int i = 0; i < n; i++)
root = insert(root, ints[i]);
cout << "In-order traversal of the constructed Interval Tree is\n";
inorder(root);
Interval x = { 7, 6 };
cout << "\nSearching for interval [" << x.l << "," << x.h << "]";
Interval *res = intervalFind(root, x);
if (res == NULL)
cout << "\nNo Overlapping Interval";
else
cout << "\nOverlaps with [" << res->l << ", " << res->h << "]";
}실행 결과
위 코드를 컴파일하여 실행하면 다음과 같은 출력을 확인할 수 있습니다.
In-order traversal of the constructed Interval Tree is [3, 4] max = 4 [3, 4] max = 4 [5, 20] max = 26 [6, 7] max = 26 [67, 26] max = 26 Searching for interval [7,6] Overlaps with [5, 20]
코드 해설
- newNode(): 새로운 노드를 동적으로 생성하고, 구간의 상한값(h)을 해당 노드의 초기 max 값으로 설정합니다.
- insert(): 이진 탐색 트리와 유사한 방식으로 구간을 삽입하며, 재귀 호출이 끝나는 과정에서 각 노드의 max 값을 하위 트리의 최댓값으로 갱신합니다.
- Overlap(): 두 구간이 겹치는지 판단하는 조건(
i1.l <= i2.h && i2.l <= i1.h)을 검사합니다. - intervalFind(): 왼쪽 서브트리의 max 값이 검색 구간의 하한값보다 크거나 같은 경우에만 왼쪽을 탐색함으로써, 불필요한 탐색을 줄여 검색 효율을 높입니다.
이처럼 인터벌 트리는 캘린더 일정 관리, IP 주소 대역 검사, 게임 충돌 감지 등 구간 데이터를 다루는 다양한 분야에서 활용될 수 있는 강력한 자료구조입니다.