위키득계정 ↗
기술

최적 이진 탐색 트리

최적 이진 탐색 트리기술
최적화 대상
탐색 확률로 가중한 평균 비교 횟수
순서 제약
왼쪽 부분 트리의 키 < 루트의 키 < 오른쪽 부분 트리의 키
성공 탐색 비용
루트 깊이를 0으로 셀 때 깊이 + 1
대표 풀이
연속 키 구간에 대한 동적 계획법
키의 탐색 확률을 반영해 평균 비교 횟수를 최소화하는 이진 탐색 트리.

최적 이진 탐색 트리는 정렬된 키와 각 키의 탐색 확률이 주어졌을 때 기대 탐색 비용을 최소화하는 이진 탐색 트리이다. 자주 찾는 키의 접근 비용을 줄이는 것이 중요하지만, 키의 대소 순서를 유지해야 하므로 탐색 확률이 가장 큰 키를 항상 루트로 선택하는 탐욕적 방법이 최적이라고 보장되지는 않는다.

평균 비교 횟수

성공한 탐색만 고려하고 각 노드에서의 키 비교를 한 번으로 세면, 루트의 비교 횟수는 1이다. 깊이가 d인 키를 찾으려면 d+1개의 노드를 방문한다. 키 i의 확률을 pᵢ, 깊이를 dᵢ라 할 때 기대 비교 횟수는 Σpᵢ(dᵢ+1)이다. 확률의 합이 1이면 이 값은 한 번 탐색할 때 필요한 비교 횟수의 가중 평균이다.

균형과 최적성의 차이

트리 높이를 작게 만드는 것과 확률을 반영한 평균 비용을 최소화하는 것은 다른 목표이다. 확률이 균등하지 않으면 높이가 같은 트리 사이에서도 평균 비용이 달라질 수 있다. 또한 이진 탐색 트리는 왼쪽 부분 트리에 작은 키, 오른쪽 부분 트리에 큰 키를 놓아야 한다. 확률순으로만 노드를 배치하면 이 순서 제약을 어길 수 있다.

구간별 동적 계획법

정렬된 키의 구간 i부터 j까지에 대한 최소 비용을 C(i,j)라 하자. 빈 구간의 비용은 0, 하나의 키만 있는 구간의 비용은 그 키의 확률이다. 후보 루트 r을 선택하면 왼쪽 구간과 오른쪽 구간의 최적 비용에 구간 전체의 확률 합을 더한다. 따라서 C(i,j)=Σpₖ+minᵣ{C(i,r−1)+C(r+1,j)}로 계산할 수 있다. 구간 전체의 확률을 더하는 것은 새 루트에서 시작하면서 각 키의 비교가 한 번씩 늘어나는 효과를 반영한다.

적용 범위

이 식은 성공 탐색만 고려한 모형이다. 존재하지 않는 키를 찾는 실패 탐색의 확률이 주어지면 키 사이 구간의 실패 비용까지 포함하는 별도의 식이 필요하다. 평균 비용을 비교할 때에는 루트의 비교를 포함하는지와 비교 한 번의 정의도 확인해야 한다. 고정된 탐색 확률을 전제로 한 정적 최적 트리와 접근 순서에 따라 구조가 변하는 동적 탐색 트리도 구분한다.