[Algorithm Part 1] 9. Interval Search Tree (interval data)

저번 글에서는, 다차원 데이터의 range 연산을 효율적으로 처리해주는 kd 트리에 대해 살펴봤다.

 

일차원 $x_1$ 데이터와 $(x_1, y_1)$ 다차원 데이터의 차이는 차원의 개수다.

하지만 $x_1$ 데이터와 $[x_1, x_2]$ 구간 데이터의 차이는 차원의 개수가 아니라, 데이터의 개수다.

즉, 데이터는 데이터가 한 개지만, 구간 $[x_1, x_2]$ 데이터는 $x_1$부터 $x_2$까지의 데이터들을 포함하고 있다.

 

이번 글에서는, 구간 (=interval) 데이터의 range 연산 즉, interval intersection query를 효율적으로 처리해주는 interval search tree에 대해 살펴볼 것이다.

interval intersection query: given an interval (lo, hi), find all intervals (or one interval) in data structure that intersects (lo, hi).

---

Definition of interval search tree

Interval Search Tree는 BST의 2가지 성질(1. binary tree, 2. symmetric order)을 가지고 있으며,
각 노드는 3가지 정보를 저장하고 있는 트리다.

1. (lo, hi) 구간을 저장하고 있다. 이때 lo가 노드의 key다.
2. 각 노드를 root로 하는 트리의 max endpoint 즉, max hi를 저장하고 있다. 

Data Structure

노드에 (lo, hi), max endpoint를 저장하고, key가 lo인, BST를 사용한다.

Operations

1. insert

1. lo값을 이용해 BST와 같이 경로를 찾아 삽입 위치를 찾는다.
2. 경로를 이동할 때마다, 각 노드의 max endpoint를 update한다.

2. find any one interval that intersects

1. 노드와 교차하면 노드를 반환한다.
2. 왼쪽 서브 트리가 없거나, (왼쪽 서브 트리의 max endpoint) < lo인 경우,
   오른쪽 서브 트리로 이동한다. (왼쪽 서브 트리에 없다.)
3. 그렇지 않으면, 왼쪽 서브 트리로 이동한다. (왼쪽 서브 트리에 없으면, 오른쪽 서브 트리에도 없다.)

Performance

	insert interval	find interval	delete interval	find one interval	find all interval
Interval search tree	$\log N$	$\log N$	$\log N$	$\log N$	$R\log N$