구간 트리(Interval Tree) 소개
이번 장에서는 구간 트리(Interval Tree)가 무엇인지 알아보겠습니다. 이름에서 짐작할 수 있듯이, 구간 트리는 구간(interval)과 연관된 트리 자료구조입니다. 구간 트리를 본격적으로 다루기에 앞서, 먼저 기본 구간(elementary interval)이라는 개념부터 살펴보겠습니다.
구간(interval)이란?
구간은 기본적으로 하나의 범위(range)를 의미합니다. 어떤 구간을 [a, b]로 표현했다면, 이는 범위가 a에서 시작하여 b에서 끝난다는 뜻입니다.
예제로 이해하는 구간 분할
예를 들어 [10, 20]이라는 구간이 있다고 가정해 보겠습니다. 이 구간을 기준으로 수직선은 세 개의 범위 값으로 나뉩니다.
- 첫 번째: -∞ 부터 10 까지
- 두 번째: 10 부터 20 까지
- 세 번째: 20 부터 ∞ 까지
이제 [15, 25]라는 두 번째 구간을 추가하면, 수직선은 다음과 같이 더 잘게 나뉘게 됩니다.
여기에 또 다른 구간인 [18, 22]를 추가하면 아래와 같이 됩니다.
구간과 하위 구간 정리
이렇게 여러 구간이 겹치면서 만들어진 서로 다른 구간들과 하위 구간(sub-interval)들을 정리하면 다음 표와 같습니다.
| 구간 이름 | 구간 범위 | 하위 구간 |
| 구간 1 | [10, 20] | [10, 15], [15, 18], [18, 20] |
| 구간 2 | [15, 25] | [15, 18], [18, 20], [20, 22], [22, 25] |
| 구간 3 | [18, 22] | [18, 20], [20, 22] |
구간 트리의 구성 방식
위 정보를 바탕으로 구간 트리를 만들 수 있습니다. 이때 각각의 하위 구간들은 하위 트리(sub-tree) 안에 배치됩니다.
구간 트리에서 모든 잎 노드(leaf node)는 하나의 기본 구간(elementary interval)을 대표합니다. 그리고 이 잎 노드들의 위에는 완전 이진 트리(complete binary tree)가 구축됩니다.
정리
구간 트리는 여러 구간이 겹치는 상황에서 특정 점이나 범위에 포함되는 구간을 빠르게 찾아야 할 때 유용한 자료구조입니다. 핵심은 다음과 같습니다.
- 구간들이 겹치면서 생기는 가장 작은 단위의 구간을 기본 구간으로 정의합니다.
- 각 기본 구간을 잎 노드에 저장합니다.
- 잎 노드 위에 완전 이진 트리 형태로 상위 노드를 구성하여 탐색 효율을 높입니다.