최적 이진 탐색트리

최적 이진 탐색트리 (Optimal BST) 이진 탐색 트리 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 루트의 오른쪽 서브트리에 있는 원소의 키 값은 루트보다 큰 이진 트리 최적 이진 탐색 트리 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용, 즉, 평균 비교 횟수를 계산하고 이를 최소화하는 탐색 트리를 구축하는 문제 키 값이 일 경우, 는 이진 탐색 트리의 i부터 j 까지의 노드에 대한 최소 평균 탐색 시간 점화식 알고리즘 OptimalBST(p[], r[], n) { for (i ← 1; i ≤ n; i ← i + 1) do { A[i,i] ← p[i]; r[i,i] ← i; } for (h ← 1; h < n; h ← h + 1) do { for ..