이진검색트리
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 # 최소값 찾아서 반납위와 같은 코드를 통해서 파이썬으로 해당 알고리즘을 구현 해 볼 수 있다.
