hye0.log hye0.log

최적 이진 탐색 트리

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

  Computer Science/Algorithm 2021. 12. 14. 20:02

  최적 이진 탐색 트리 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때, 그 트리의 평균 탐색 비용, 즉 평균 비교 횟수를 계산하고 이를 최소화하는 탐색트리를 구축하는 문제 이진 탐색 트리 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 루트의 오른쪽 서브트리에 있는 원소의 카 값은 루트보다 큰 이진 트리 점화식 최적 이진 탐색 트리 구하기 1. A[i, j] 테이블과 k 테이블을 그려줍니다. A테이블 대각선엔, 문제에서 주어진 확률을 K테이블 대각선엔, 순서대로 초기 값을 적어줍니다. 2. 점화식을 이용하여 테이블의 값을 채워줍니다. 3. 이진 탐색 트리 그리기 - k테이블에서 1행 가장 맨 끝 값을 가져옵니다. k[1, 4] = 3 값이 3이기 때문에, 이는 3번 노드가 최상단임을 ..

  Read More