[알고리즘] 동적계획법 | 최적 이진 탐색 트리

이진 탐색 트리는 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고,

오른쪽 서브트리에 있는 원소의 값은 루트보다 큰 값을 가진다.

또, leaf 노드들 간의  depth 차이가 1보다 클 수 없다.

여기서 '최적'이란 단어까지 붙으면 최적 이진 검색트리가 된다.

 

최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미한다.

즉, 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용(평균 비교 횟수)를 계산하고

이를 최소화하는 탐색 트리를 구축하는 문제이다.

여기서 탐색 비용은 원하는 키를 찾기까지 필요한 비교 횟수를 뜻한다.

 

평균 탐색시간은 한 노드에 담긴 keym이 찾고자하는 search key일 확률을 pm라고 하고,

keym을 찾기까지의 비교횟수를 cm이라고 할 때 pm과 cm의 곱의 합으로 나타내며 수식은 아래와 같다. 

Cm : keym을 찾아가기 위한 비교횟수

Pm : keym이 search key일 확률

최적 이진 탐색 트리

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

최적 탐색 트리가 그래서 뭔데..?

문제에 대한 정확한 정의를 알아보자

1. 키값이 k1부터 kn까지 주어진다.
2. 각 키의 검색 확률 pi가 주어진다.
3. 각 키의 비교 횟수 ci : ki를 검색하는데 필요한 키의 횟수

이러한 조건이 주어질 때 각 키의 평균 검색 비용은 : 검색확률 pi * 비교횟수 ci
그리고 전체 키의 평균값은 이 평균값의 summation이다.

Brute-Force

• 모든 경우의 수에 대해서 계산해 보고 최적의 이진트리를 선택한다.
• 이 경우 앞서 연쇄행렬곱셈에서도 사용했던 카탈란수를 다시 사용하게 될 것이다.
  

  

그렇다면, 그림을 통해서 입력사례를 알아보도록 하겠다.

키값 [10, 20, 30] / 확률 [0.7, 0.2, 0.1]이 주어진 이진트리의 경우 총 5가지의 경우의 수가 존재하는데
이 값들을 계산해보면 5번의 이진트리가 1.4의 값으로 가장 최적의 이진트리를 가지고 있다고 할 수 있다.

재귀관계식 만들기

• 1단계: 재귀 관계식을 찾는다.

𝑨: 이진검색트리를 만드는데 최적 검색비용의 행렬

• 𝑨[𝒊][𝒋]: 𝐾𝑖에서 𝐾𝑗까지 이진검색트리를 만드는데 최적 검색 비용
• 목표: 𝐾𝑖 ⋯ 𝐾𝑗를 (𝐾𝑖 ⋯ 𝐾𝑘−1)𝐾𝑘(𝐾𝑘+1 ⋯ 𝐾𝑗)로 분할하는 재귀 관계식 찾기

• 2단계: 상향식 방법으로 해답을 구한다.

• 초기화: 𝐴[𝑖][𝑖] = 𝑝𝑖
  (주대각선을 𝑝𝑖 으로)
• 최종 목표:𝐴[1][𝑛].
• 상향식 계산: 대각선 1번, 대각선 2번, ⋯ , 대각선 𝑛 − 1번

• CMM의 Diognal 해결법과 동일하다.

최종재귀관계식은 다음과 같다

즉 이진트리에서 Kk의 최적값은 좌측노드의 최적값 + 우측노드의 최적값 + k의까지의 모든 값의 최소값이다.

𝐴[1][𝑘 − 1]+𝐴[𝑘 + 1][𝑛]

코드 작성

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 # 현재 diagonal에서 몇번째 원소인지를 결정함, 1번 대각선은 이미 자기자신으로 설정되어있음
            A[i][j], R[i][j] = minimum(A, p, i, j)
    return A, R
    
def minimum (A, p, i, j):
    minValue = 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] # summation of p[m], 즉 지금까지 모든 k 서치값의 합
        if (minValue > value):
            minValue = value
            minK = k 
    return minValue, minK # 최소값 찾아서 반납

위와 같은 코드를 통해서 파이썬으로 해당 알고리즘을 구현 해 볼 수 있다.