Optimal Binary Search Tree

- BST

이런 트리 형태의 자료구조.

Tree - Binary Search Tree

 

- 알고리즘 정의

데이터를 효율적으로 관리하기 위해 BST를 사용하는데,

BST의 경우에도 문제가 하나 있다. 바로 데이터 입력 순서에 따라서 트리의 모양이 달라진다는 것.

이게 왜 문제인가 라는 의문이 있을 수 있는데, 바로 이 때문에 탐색 시간의 차이가 생길 수 있기 때문이다.

 

필연적으로 데이터 중에서 특별히 많이 검색되는 데이터가 있을 것이고, 그렇지 않은 데이터도 있을 것이다.

데이터(key) i가 검색될 확률을 pi라 하고, 그 데이터를 찾기까지의 비교 횟수를 ci라 하자.

keyi의 평균 검색 시간은 다음과 같다.

위 값을 최저로 줄이는 것이 BST의 평균 탐색 시간을 줄일 수 있게 해주는데,

이 값이 최소가 되는 BST를 Optimal BST라고 한다.

 

Optimal BST를 일반적으로 구하면 최소 ^n 형태의 시간 복잡도를 갖게 된다.

따라서 Dynamic Programming 방식으로 구해야만 한다.

dp 방식으로 알고리즘을 구현하기 위해 몇가지 규칙을 만들자.

Optimal BST는 반드시 아래의 트리 모양 중 하나를 갖게 된다.

단, 반드시 key1 ~ keyn은 오름 차순이다.

• A[i][j]: keyi ~ keyj 까지의 데이터를 BST에 저장하는데 있어
              평균 검색 시간이 최소가 되도록 저장할 때, (최소) 평균 검색 시간을 저장.
• A[i][i]: keyi 의 데이터만 BST에 저장하는 경우이기 때문에
              평균 검색 시간은 pi가 된다.

 

이제 일반적인 상황으로 keyk가 root에 있는 경우를 살펴보자.

이 경우 최소 평균 탐색 시간 A[1][n]은 아래와 같이 나타낼 수 있다.

따라서 아래와 같은 관계식을 얻을 수 있다.

반드시 i < j 여야 한다. 그렇기에 [i][i-1]과 같은 BST는 없기 때문에 0으로 초기화가 된다.

2, 3번째 관계식을 통해 A배열을 초기화 하자.

목표는 A[1][n]을 얻는 것.

따라서 아래와 같은 순서로 대각선 방향으로 값을 채워나가면 된다.

 

- Pseudocode

// global: Key[]
public static float optSearchTree (int n, float[] p,
                                   index[][] R) {
    index i, j, k, diagonal;
    float[][] A = new float[1..n+1][0..n];
    
    for (i=1; i<=n; i++) {
        A[i][i-1] = 0;
        A[i][i] = p[i];
        R[i][i-1] = 0;
        R[i][i] = i;
    }
    A[n+1][n] = 0;
    R[n+1][n] = 0;
    
    for (diagonal=1; diagonal <= n-1; diagonal++)
        for (i=1; i<= n-diagonal; i++) {
            j = i + diagonal;
            // min은 내부적으로 k가 i~j 까지의 loop를 돌아야 함.
            // sum은 내부적으로 m이 1~j 까지의 loop를 돌아야 함.
            A[i][j] = min(A[i][k-1] + A[k+1][j]) + sum(p[m]);
            // A[i][j]가 결정되는 k값. 즉, 최소가 되게 하는 k값
            R[i][j] = k;
        }
    
    return A[1][n];
}

// Building Optimal BST using R(the result of optSearchTree)
// Initial Call: root = bst(1, n);
public static nodeType bst (index i, index j) {
    index k;
    nodeType p;
    
    k = R[i][j];
    if (k==0) return NULL;
    
    p = new nodeType();
    p.key = Key[k];
    p.left = bst(i, k-1);
    p.right = bst(k+1, j);
    
    return p;
}

알고리즘 설명대로 진행된다.

 

Key[]는 node의 key 값이 정렬된 상태로 들어있다.

n은 BST의 node의 갯수,

p는 Key에서 각각의 key의 사용 빈도(확률)

R은 최적의 Key값의 인덱스를 저장할 배열이다.

 

배열 A, R를 초기화 한 후diagonal을 따라 값을 업데이트한다.

A[i][j]를 업데이트 하는 방식을 시각화 하면 다음과 같다.

같은 색깔인 부분의 합은 A[i][k-1] + A[k+1][j] + sum(p[m]) 가 된다.

e.g. diagonal=n-1 -> i=1, j=n
k=1(i), A[1][0] + A[2][n] + sum(p[m])
k=2   , A[1][1] + A[3][n] + sum(p[m])
...
k=n(j), A[1][n-1] + A[n+1][n] + sum(p[m])

그 합이 최소가 되는 값을 min 함수로 알아내 A[i][j]에 넣는 것이다.

 

bst에서는 구한 R 배열을 이용해 Optimal BST를 만들게 되는데,

R[i][j]에는 keyi ~ keyj를 BST에 배열할 때 root에 들어갈 key의 인덱스를 갖고있다.

그렇기에 p.key의 값을 Key[k]로 가져오고

subTree를 k번째 인덱스를 제외하고 재귀 호출하여 생성하면 된다.

 

- Time complexity

Basic Operation: min 함수 내부의 k loop 반복 횟수

Input Size: n, sizeof Key

 

* Every case:

Within k-loop: j-i+1 = diagonal+1 times

Within i-loop: (n-diagonal)(diagonal+1) times

Within diagonal-loop: sum((n-diagonal)(diagonal+1)) (diagoanl: 1~n-1) times

=> T(n) = n(n-1)(n+4)/6 [Θ(n^3)]