최적 이진검색트리

강한친구·2021년 9월 13일
0

이진검색트리

Binary Search Tree는 다들 한번쯤 봤을법한 검색트리기법중 하나이다. 이번 알고리즘은 이 이진검색트리에서 평균 검색비용을 최적화하는 알고리즘을 찾는 문제이다.

우선 이진검색트리의 조건에 대해 알아보자.

  • 각 노드는 하나의 유일한 키를 가지고 있다.
  • 모든 노드가 가진 키의 값은 그 노드의 왼쪽 서브트리의 값보다 크다
  • 모든 노드가 가진 키의 값은 그 노드의 오른쪽 서브트리의 키의 값보다 작다.

정확한 정의

문제에 대한 정확한 정의를 알아보자
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 # 최소값 찾아서 반납

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

0개의 댓글