[알고리즘] 최적 이진 검색 트리, Optimal Binary Search Trees | 설계 및 분석

최적 이진 검색 트리란?

  최적 이진 검색트리의 뜻을 알기위해서는 먼저 이진 검색 트리의 뜻을 알아야한다. 이진 검색 트리는 말 그대로 이진 트리를 검색 목적으로 사용하는 것이다. 왼쪽에는 같거나 더 작은 값을, 오른쪽에는 더 큰 값을 저장하고 leaf 노드들 간의  depth 차이가 1보다 클 수 없다. 여기서 '최적'이란 단어까지 붙으면 최적 이진 검색트리가 된다. 최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미한다.

  탐색시간은 원하는 키를 찾기까지 필요한 비교 횟수이다. 평균 탐색시간은 한 노드에 담긴 key_m이 찾고자하는 search key일 확률을 p_m라고 하고, key_m을 찾기까지의 비교횟수를 c_m이라고 할 때 p_m과 c_m의 곱의 합으로 나타내며 수식은 아래와 같다. 

C_m : key_m을 찾아가기 위한 비교횟수

P_m : key_m이 search key일 확률

 

<이진 트리에서 사용하는 자료구조>

① 노드를 구조체로 나타냄

//노드를 구조체로써 나타냄

struct nodetype {
  keytype key
  nodetype* left
  nodetype* right
}
Typedef nodetype* node_pointer;

② A : 최적의 평균 탐색시간 값을 담은 배열

   A[i][j] = key_i부터 key_j까지의 최적 평균 탐색시간

 

알고리즘 설계전략

① 재귀 관계식 정립

 

  root를 추가할 때 마다 기존의 트리는 그 root의 subtree가 되므로 비교횟수가 각각 한번씩(c_i(=1) x p_i) 더 늘어난다.

따라서 A[1][n] = A[1][k-1] + p₁ + ... + p_k-1 + p_k + A[k+1][1] + p_k+1 + ... + p_n

결론적으로 다음과 같은 재귀관계식이 도출된다.

② bottom-up 방식으로 해결

  왼쪽 sub tree의 노드 개수가 0개일 때부터 n-1개일 때까지를 앞의 것의 결과를 토대로 순서대로 구한다.  foundations of algorithms 교재 example 3.9에 이 과정에 대한 예시가 나와있다.

 

출처: foundations of algorithms, Richard Neapolitan, 도경구역

 

알고리즘 수도코드

  최적의 평균 탐색 시간을 찾는 코드이다.

void optsearchtree(int n, const float p[], float& minavg, index R[][]) {
  index i, j, k, diagonal;
  float A[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;
  }
  
  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;
      A[i][j] = minimum(A[i][k-1]+A[k+1][j])) + sum of pi ~ pj; //basic operation
      R[i][j] = a value of k that gave the minimum;
    }
    minavg = A[1][n];
}

//배열 R을 이용해 트리 생성
nodepointer tree(index i, j) {
  index k;
  node_pointer p;
  k = R[i][j];
  if(k==0)
    return NULL;
  else {
    p = new nodetype;
    p->key = key[k];
    p->left = tree(i,k-1);
    p->right = tree(k+1,j);
    return p;
  }
}

 

알고리즘 성능분석

basic operation : 각 k 값에 대한 덧셈, 비교연산 (A[i][j] = minimum(A[i][k-1]+A[k+1][j])) + sum of pi ~ pj;)

  최적 이진 트리 탐색도 플로이드 알고리즘과 같이 every-case이다.

  위 수도코드를 보면 j = i + diagonal이므로

  - i에 대한 for문을 수행하는 횟수 = n - diagonal

  - k에 대한 for문을 수행하는 횟수 = j-i+1 = (i+diagonal)-i+1 = diagonal+1

∴Θ(n³)