[알고리즘] 최적 이진 탐색트리 (Optimal BST)

최적 이진 탐색트리 (Optimal BST)

이진 탐색 트리

• 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 루트의 오른쪽 서브트리에 있는 원소의 키 값은 루트보다 큰 이진 트리

 

최적 이진 탐색 트리

• 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용, 즉, 평균 비교 횟수를 계산하고 이를 최소화하는 탐색 트리를 구축하는 문제
• 키 값이  일 경우,  는 이진 탐색 트리의 i부터 j 까지의 노드에 대한 최소 평균 탐색 시간

 

점화식

 

알고리즘

OptimalBST(p[], r[], n) {
    for (i ← 1; i ≤ n; i ← i + 1) do {
        A[i,i] ← p[i];
        r[i,i] ← i;
    }
    for (h ← 1; h < n; h ← h + 1) do {
        for (i ← 1; i ≤ n-h; i ← i + 1) do {
            j ← i + h;
            A[i,j] ← mini≤k≤j(A[i,k-1] + A[k+1,j] + Σ P[m]);
            r[i,j] ← 최소 값을 갖는 k;
        }
    }
    return A[1,n];
} end OmtimalBST()

node_pointer BuildTree( i, j ) {
    index k;
    node_pointer p;

    k = r[i][j];
    if(k==0) return;
    else{
        p = new node_pointer;
        p -> key = Key[k];
        p -> left = BuildTree( i, k-1 );
        p -> right = BuildTree( k+1, j );
        return p;
    }
} end BuildTree()