Optimal Binary Search Tree

염치 없이 돌아왔다.

이번 학기에는 자료구조 수업을 듣게 되었는데, 상당히 흥미로운 내용이 많아서 정리할 겸 블로그에 올려두려고 한다.

그 첫 시작은 바로 최적 이진탐색트리(OBST)에 관한 것!

1. 문제 정의

보통 우리가 생각하는 이진탐색트리(BST)에 관한 문제는:

• BST가 어떤 경우에서든 균일한 성능을 보이도록 최적화(AVL, Splay)
• BST의 높이, 노드 개수 등에 관한 수학적인 탐구
• BST를 어떻게 응용할 수 있는가(허프만 인코딩)

..뭐 이런 문제들이다. 근데 이번에는 다루는 문제의 결이 조금 다르다.

 

"각 노드들에 대한 방문횟수가 모두 정해져 있을 때, 탐색횟수가 가장 작은 형태의 BST는 무엇인가?"

 

즉, 이번에는 BST를 최적화한다기보다도 이론상으로 가장 최적인 BST가 무엇인지, 그 자체가 궁금하다는 것이다.

 

간단한 예시를 들어 보자. 1과 2, 2개의 숫자가 들어 있는 BST가 있다. 

만약 이 상태에서 1을 100000번, 2를 1번 탐색할 예정이라면 1이 루트에 있는 것이 탐색 횟수를 줄이는 방법일 것이다.

왜냐면 그렇지 않으면 1을 찾기 위해 2번 움직이는 수고를 10만번 해야 하니까..

 

노드가 2개면 매우 쉬운 문제지만, 노드가 1500개쯤 된다고 생각해 보자.

벌써 머리가 아파오지 않는가?

빠르게 풀어 보자.

2. 풀어보자

이를 풀기 위해 몇 가지 정의를 해야 한다.

노드의 개수를 $n$개, 각 노드를 탐색하는 횟수를 $p_i$, $i$번~$j$번 노드로 만든 OBST의 탐색 비용을 $c(i, j)$라고 하자.

이때 노드의 번호는 오름차순으로 붙인다.

 

이 상황에서, 우리가 구하고자 하는 답은 $c(1, n)$이다.

아마 PS를 조금이라도 해본 사람들은 DP식을 만들고 싶어질 것이다.

이를 위해 간단한 두 가지 관찰을 하자.

 

I) 만약 OBST의 루트가 $k$번째 노드라면, $i$번~$k-1$번 노드까지가 왼쪽 Subtree에, $k+1$번~$n$번 노드가 오른쪽 Subtree에 위치한다.

 

- 이는 BST의 성질에 의해 성립한다.

- 사실상 이 성질때문에 최적해를 $c(i, j)$라고 정의할 수 있었다. 시점과 끝점만 고려해도 되니..

 

II)  $i$~$j$번 노드까지가 한쪽 Subtree에 들어가있다 하자. 그러면, 총 탐색 횟수는 $\sum_{k=i}^{j}{p_k}$만큼 늘어난다.

 

- 한 단계씩 더 가야 하므로..

 

이제 우리는 $1$~$n$번까지의 노드로 만든 OBST의 루트가 $k$라면, 그 비용 $c(i, j)$는..

\[ c(i, j) = c(i, k-1) + c(k+1, j) + \sum_{l=i}^{j}{p_l}\]

임을 안다. 따라서..

\[c(i, j) = min_{k=i~j}(c(i, k-1) + c(k+1, j)) + \sum_{l=i}^{j}{p_l} \]

가 성립한다. 

 

이는 전형적인 파일 합치기류 DP식이며, Naive하게 계산하면 $O(n^3)$에 계산할 수 있다.

그리고 각 $c(i, j)$를 계산할 때마다 결정되는 $k$를 저장하면 쉽게 Tracking 할 수 있다.그러한 Tracking에는 총 $O(n)$의 연산량이 필요하다.

 

그리고... 위의 예시 문제와 마찬가지 방식으로 최적화 할 수 있다.

3. 최적화하기

이를 최적화하는 굉장히 유명한 방법이 바로 Knuth Optimization이다.

나는 OBST 문제를 알기 전부터 이 방법을 알고 있었는데, 사실 크누스는 OBST 문제를 최적화하기 위해 이 알고리즘을 만들었다고 한다. 진짜 천재..

$i$번~$j$번 노드까지로 만든 트리의 루트를 $r(i, j)$라고 하자.

네 정수 $i_1, i_2, j_1, j_2$에 대해 $i_1<i_2<j_1<j_2$를 만족하면,

$r(i_1, j_1) <= r(i_2, j_2)$가 성립한다는 것이 바로 Knuth's monotonicity property이다.

 

사실 이 문제에서만 성립하는 성질은 아니고, 위에서 부분 문제 뒤에 더해지는 추가비용이

I) 사각형부등식(Quadrangle Inequality) $w(i, j) +w(i', j') <= w(i', j) + w(i, j') (i<=i'<=j<=j')$ 을 만족하며, 

II) 구간의 대소를 보존할 때, 즉 $[i, j] \in [i', j']$를 만족하는 두 구간에 대해 $w(i, j) <= w(i', j')$를 만족할 때

이러한 단조성이 생긴다. 이를 증명하는 것은 꽤 귀찮고 복잡하기 때문에 일단 남겨둔다.

 

단조성을 가지는 것의 장점은, 이로 인해 탐색해야 할 범위가 확 준다는 것이다.

해를 찾을 때 루트 후보를 $i$번부터 $j$번까지 탐색하면서 어떤 것이 가장 적합한지를 알아보아야 하는데,

그 과정에서 굳이 탐색할 필요가 없는 부분이 생기기 때문이다.

그리고 이것은 자연스럽게 이 알고리즘의 시간복잡도를 Amortized $O(n^2)$로 바꾼다.

(루트가 단조증가하니까.. 스택 넣고빼기 문제마냥)

4. 결론

이 문제를 처음 봤을 때 크누스 최적화랑 관련있을 거라는 생각은 전혀 하지 못했는데, 갑작스럽게 나타나서 신기했다.

 

평소에 알던 무언가를 실제로 수업에서 만나면 괜히 기분이 좋아진다.

뭔가 내가 교수님보다 더 똑똑해진 것 같고 그렇잖아

 

하지만 절대 그렇지 않다는 것을 안다

더 열심히 공부해서 자구 A0 가보자~ (A+은 지난번 시험때 날아감)

 

**티스토리 블로그는 진짜 세상에서 제일 불안정한거 같다. 빨리 옮겨야지..