최적 이진검색트리

  • 주어진 n개의 키로 최적 이진검색트리를 구하는 문제
    → 주어진 n개의 키: K1, K2…, Kn
    → 각 키의 검색 확률 pi: 전체 검색횟수 중에서 Ki를 검색하는 확률
    → 각 키의 비교 횟수 ci: Ki를 검색하는데 필요한 키의 비교 횟수
    → 각 키의 평균 검색 시간: 검색 확률 * 비교 횟수 (pi * ci)
    → 전체 키의 평균 검색 시간: pi * ci의 총 합(n ~ i=1)

  • Dynamic Programming 방식으로 접근하기

    1. 재귀 관계식을 찾는다
    • A: 이진검색트리를 만드는데 최적 검색비용의 행렬
    • A[i][j]: Ki에서 Kj까지 이진검색트리를 만드는데 최적 검색 비용
    • Ki … Kj를 (Ki … Kk-1)Kk(Kk+1 … Kj)로 분할하는 재귀 관계식 찾기
    1. 상향식 방법으로 해답을 구하기
    • A[i][i] = pi
    • 대각선의 상향식 계산으로 A[1][n]을 구함
    1. 최적 이진검색트리의 재귀관계식
    • 트리 k: 키 Kk가 루트 노드에 있는 최적 이진검색트리
    • 키 비교 횟수: 서브 트리의 비교 횟수에 루트에서 비교 한 번 추가
    • m ≠ k 인 Km에 대해서 트리 k에 Km을 놓기 위한 비교 한 번 추가
      → A[1][n] = minimum(A[1][k-1]+A[k+1][n] + ∑(n ∼ m=1)Pm) (단, i ≤ k ≤ j)

파이썬으로 최적 이진검색트리

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def optsearchtree (p):
    n = len(p) - 1
    A = [[-1] * (n + 1) for _ in range(n + 2)] # 최소비용
    R = [[-1] * (n + 1) for _ in range(n + 2)] # 루트노드
    for i in range(1, n + 1):
        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 in range(1, n): # 대각선을 거치며 최소값 구하기
        for i in range(1, n - diagonal + 1):
            j = i + diagonal 
            # j값은 주 대각선 값(diagonal)만큼 우측에 있어야 하므로 더해준다
            A[i][j], R[i][j] = minimum(A, p, i, j)
    return A, R

# minimum 함수는 연쇄 행렬 곱셈에서 썼던것과 거의 동일
def minimum (A, p, i, j):
    minVal = INF
    minK = 0
    for k in range(i, j + 1):
        value = A[i][k - 1] + A[k + 1][j]
        for m in range(i, j + 1):
            value += p[m]
        if (minVal > value):
            minVal = value
            minK = k
    return minVal, minK

참고: 연쇄 행렬 곱셈 알고리즘

최적 이진검색트리의 노드 순서 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def tree (R, i, j):
    k = R[i][j]
    if (k == 0):
        return None
    else:
        node = BSTNode(keys[k])
        node.left = tree(R, i, k - 1)
        node.right = tree(R, k + 1, j)
        return node

class BSTNode:
    def __init__ (self, key):
        self.key = key
        self.left = None
        self.right = None

def preorder (node):
    if (node is None): return
    else: 
        print(node.key, end = ' ')
        preorder(node.left)
        preorder(node.right)

def inorder (node) :
    if (node is None): return
    else:
        inorder(node.left)
        print(node.key, end = ' ')
        inorder(node.right)

자바스크립트로 최적 이진검색트리의 노드 순서 구하기(수정 중)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const optsearchtree = p => {
    let n = p.length - 1;
    let arr = Array.from(Array(n+2), () => Array(n+1).fill(-1))
    let arr2 = [...arr]
    for (let i = 1; i < n+1; i++){
        arr[i][i-1] = 0
        arr[i][i] = p[i]
        arr2[i][i-1] = 0
        arr2[i][i] = i
    }
    arr[n+1][n] = 0
    arr2[n+1][n] = 0
    for(let diagonal = 1; diagonal < n; diagonal++) {
        for (let i = 1; i < n - diagonal + 1; i++){
            let j = i + diagonal;
            arr[i][j] = minimum(arr, p, i, j).minVal;
            arr2[i][j] = minimum(arr2, p, i, j).minK;
        }
        console.log(arr)
    }
    return { arr: arr, arr2: arr2 }
}

const minimum = (arr, p, i, j) => {
    let minVal = Infinity;
    let minK = 0
    for (let k = i; k < j+1; k++){
        let value = arr[i][k-1] + arr[k+1][j]
        for (let m = i; m < j+1; m++){
            value += p[m]
        }

        if (minVal > value) {
            minVal = value
            minK = k
        }        
    }
    return { minVal: minVal, minK: minK }
}