[Algorithm] Optimal Binary Tree (최적 이진 트리)

이번 포스팅에서는 Optimal Binary Tree 에 대해서 알아보도록 하겠습니다.

 

Optimal Binary Tree에 대한 설명에 들어가기 앞서, Binary Search Tree 에 대해 짚고 가겠습니다.

 

Binary Search Tree (BST) : Binary search 를 가이드 해주는 binary tree

Binary Search Tree 의 각 Node 에는 array 의 Element 가 대응되며, 이것을 특별히 Key라고 합니다. (Tree 안에서 key의 값은 서로 다르다 가정합시다. 즉, Element 는 모두 distinct 합니다.)

 

Non-Leaf Node k (= key 값이 k인 non-leaf node)는 다음과 같은 property 를 갖습니다.

1.  k의 left subtree 상의 모든 node 들의 key 값은 k보다 작습니다.
2.  k의 right subtree 상의 모든 node 들의 key 값은 k보다 큽니다.

property of Non-leaf node k

Binary Search Tree 를 따라 binary search 수행 시 key k의 search cost = (BST 에서 node k 의 depth) + 1

Ex) Search cost of 6 = 0 + 1 = 1, Search Cost of 7 = 1 + 1 = 2, Search Cost of 3 = 3 + 1 = 4.

 

이제 Optimal Binary Search Problem 에 대해 알아보겠습니다. Optimal Binary Search Problem 의 전제는 다음과 같습니다.

 

전제 1.  n 개의 서로 다른 key 들 k1 < k2 < k3 < ... < kn 이 있고 1<=i<=n 에 대해, BST를 이용해 Key ki 를 총 fi번 검색한다는 것을 미리 알고 있다고 가정합니다.

(위와 같이 search 의 내용을 미리 알고 있다는 가정하에 만들어진 알고리즘을 offline algorithm이라고 하고 반대로 search의 내용을 모르는 상태에서 만들어진 알고리즘은 online algorithm이라고 합니다.)

 

전제 2. BST 에서 Insertion 이나 Deletion 은 일어나지 않는다고 가정합니다.

 

이 경우, BST T에서 Key ki 의 depth를 depth(T, ki)라고 할 때, total search cost 는 Summation( (𝐝𝐞𝐩𝐭𝐡 𝐓, 𝐤𝐢) + 𝟏 ), i=1 to n 입니다.

 

Optimal Binary Search Tree Problem 은 다음을 해결하는 것입니다.

 

Optimal Binary Search Tree Problem : Total search cost 를 최소로 하는 binary search tree (= optimal BST) 구하기

 

먼저 Optimal BST 를 구하는 가장 떠올리기 쉬운 방법부터 살펴보겠습니다.

만들 수 있는 모든 BST를 고려하여 Optimal BST 찾기

위와 같은 방법으로, n개의 key를 가지는 가능한 모든 BST를 생성하여 그 중 total search cost 가 가장 작은 것을 고르면 됩니다. n개의 node를 가진 BST는 대략 O(4^n) 개 정도이므로 Time Complexity 는 적어도 Exponential Time 을 가질 것임을 예상할 수 있습니다.

 

더 빠르게 Optimal BST를 찾을 수 있는 방법은 없을까요?

 

다이나믹 프로그래밍 기법을 이용하여 Optimal BST 를 찾는 알고리즘을 디자인해봅시다.

 

Subproblem 을 다음과 같이 정의하겠습니다.

Subproblem of Optimal BST : 임의의 1 <= i <= j <= n에 대해 C(i,j)를 전체 key ki, ki+1, ..., kj 를 각각 fi, fi+1,...,fj번 검색한다 할 때, optimal BST 의 total search cost

따라서 우리가 원래 구하고자 하는 Optimal BST 의 total search cost는 C(1, n)입니다. ( = key k1 ~ key kn까지 검색할 때 search cost 의 총합)

 

이제 Subproblem 의 정의를 이용해 Recurrence Relation 을 정의해보겠습니다.

Base Case :

Case 1 (i = j 일 때) C(i, j) = fi -> 단일 node 하나를 가진 BST.

Case 2 (i > j 일 때) C(i, j) = 0 -> 성립하지 않는 BST

 

Inductive Step :

C(i, j)를 가진 optimal BST 를 어떻게 construct 할 수 있을까요? 임의의 i에서 j사이의 index k 에 대해서 다음과 같이 root node 가 k-th key인 BST를 생각해봅시다.

이 경우, BST에서 total search cost 는 다음과 같습니다.

i <= k <= j 인 index k 에 대해서 root node 가 k-th key 인 BST 중 total search cost 가 가장 작은 것이 C(i, j)가 될 것입니다.

 

따라서 C(i, j) 의 Recurrence Relation 은 다음과 같이 나타낼 수 있습니다.

이제 우리가 세운 Recurrence Relation 이 정당함을 증명해야합니다. 즉 C'(i,j)가 C(i,j)임을 보여야합니다.

 

Claim : 모든 1<=i,j<=n 에 대해 C(i,j) = C'(i,j).

Proof : Induction on j - i

Base Case. ( j-i <= 0) 인 경우 : 정의에 의해 당연하다. (trivial)

Inductive Step (C(i,j)<=C'(i,j)이고 C(i,j)>=C'(i,j)이면 C(i,j) = C'(i,j)임을 이용)

C(i, j) <= C'(i, j) : C'(i, j)는 어떤 BST 의 total search cost 를 나타내며, 이는 optimal BST의 total search cost보다 당연히 크거나 같습니다.

C(i,j) >= C'(i,j) : Optimal BST 의 root node 가 k-th Key 라 합시다. 그러면 다음이 성립합니다.

따라서 C(i,j) = C'(i,j) 입니다.

 

이제 Subproblem 들 간 Data Dependency 를 확인하겠습니다.

Data Dependecy : C(i, j)를 결정하기 위해서는 모든 i <= k <= j 에 대해 C(i,k-1)과 C(k+1, j) 를 알아야 합니다. 따라서 C(i, j)의 값을 2차원 array 에 저장한다 할 때 array 의 각 entry 를 다음과 같은 순서들 중 하나로 계산할 경우 각 index의 값을 O(n) 시간 안에 구할 수 있습니다. Array의 Entry 가 총 O(n^2) 개 있으므로, 총 수행 시간은 O(n^3)이 됩니다.

요약하면 optimal BST 를 구하는 알고리즘의 개요는 다음과 같습니다.

1. Base Case (i=j 인 경우) : C(i, i)에 대응하는 BST로 단일 node ki 를 생성합니다.

2. C(i, j) = C(i, k-1) + C(k+1, j) + summation(fp p = i to j) 인 경우, root node k-th Key 를 가지고 C(i, k-1) 과 C(k+1, j)를 각각 left subtree, right subtree로 가지는 BST를 생성하여 i<=k<=j 중 가장 total search cost 가 작은 BST를 선택.