[알고리즘] 최적 이진 탐색 트리

최적 이진 탐색 트리

• 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때, 그 트리의 평균 탐색 비용, 즉 평균 비교 횟수를 계산하고 이를 최소화하는 탐색트리를 구축하는 문제

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

• 점화식
  

  

---

최적 이진 탐색 트리 구하기

 

1. A[i, j] 테이블과 k 테이블을 그려줍니다.

A테이블 대각선엔, 문제에서 주어진 확률을 K테이블 대각선엔, 순서대로 초기 값을 적어줍니다.

2. 점화식을 이용하여 테이블의 값을 채워줍니다.

3. 이진 탐색 트리 그리기

- k테이블에서 1행 가장 맨 끝 값을 가져옵니다. 

   k[1, 4] = 3 

값이 3이기 때문에, 이는 3번 노드가 최상단임을 의미합니다. 

C가 최상단이므로, C보다 큰 값인 D는 오른쪽 아래 노드에 위치되어집니다. ( ∵ 이진트리)

 

- 남은 노드는 A, B 즉, 1~2까지의 노드를 확인해야하므로 k[1, 2] 값을 확인합니다.

  k[1, 2] = 1

값이 1이기 때문에, 이는 1번 노드가 왼쪽아래에 위치함을 의미합니다.

A를 위치하면, 나머지 A보다 큰 값인 B는 A의 오른쪽 아래 노드에 위치되어집니다.

완성된 최적  이진 탐색 트리

 

 

궁금하신 점이나 틀린 점이 있다면, 댓글로 남겨주세요!

감사합니다.