Optimal Binary Search Tree (OBST)
최적 이진 검색 트리
Definitions (정의)
Node Structure (노드의 구조)
- \(\texttt{key}\) : 검색 대상이 되는 원소로, key는 검색 가능한 Ordered Set의 원소이어야 한다.
- \(\texttt{probability}\) : 해당 노드의 key를 검색하게 될 확률이다. (\(p_{i}\) = \(Node_{i}\)를 검색할 확률)
- \(\texttt{leftChild}\) : 해당 노드의 왼쪽 자식 노드를 가리키는 주솟값이다.
- \(\texttt{rightChild}\) : 해당 노드의 오른쪽 자식 노드를 가리키는 주솟값이다.
Average Search Time (AST, 평균 검색 시간)
- \(p_{i}\) : 임의의 \(Node_{i}\)를 검색할 확률이다.
즉, n개의 노드로 구성된 트리에서는 \(\sum\limits_{i=1}^{n} p_{i} = 1\)이다.
- \(c_{i}\) : 임의의 \(Node_{i}\)를 검색하는데 수행하는 비교 연산의 횟수이다.
즉, \(c_{i} = Depth\,(Node) + 1\)
\(\therefore n\)개의 노드로 구성된 Binary Tree의 Average Search Time = \(\sum\limits_{i=1}^{n} c_{i} * p_{i}\)
- \(Tree_{k}\) : \(Node_{k}\)를 Root 노드로 하는 트리
\(\therefore Tree_{k}\)의 Average Search Time
\(= A[1][k-1] + (1 * \sum\limits_{i=1}^{k-1} p_{i}) + (1 * p_{k}) + A[k+1][n] + (1 * \sum\limits_{i=k+1}^{n} p_{i})\)
(왼쪽 서브트리의 AST) + (루트 노드 하나가 추가됨으로써 왼쪽 서브트리 노드들을 검색하는데 추가적으로 부과된 비교 횟수 1회) + (루트 노드와의 비교 횟수 1회) + (오른쪽 서브트리의 AST) + (오른쪽 서브트리 노드들검색하는데 추가적으로 부과된 비교 횟수 1회)
\(= A[1][k-1] + A[k+1][n] + \sum\limits_{i=1}^{n} p_{i}\)
\(= A[1][k-1] + A[k+1][n] + 1\)
Average Search Time of OBST (OBST의 평균 검색 시간)
- OBST : \(n\)개의 노드로 구성할 수 있는 Binary Tree중, \(\sum\limits_{i=1}^{n} c_{i} * p_{i}\)(평균 검색 시간)이 최소가 되는 Tree이다.
- \(A[i][j]\) : \(Node_{i}\)부터 \(Node_{j}\)로 구성된 OBST의 평균 검색 시간이다.
- \(A[1][n]\) : \(n\)개의 노드로 구성된 OBST의 평균 검색 시간이다. 본 알고리즘에서 구하고자 하는 궁극적인 목표이다.
\(\therefore A[1][n] = MIN_{1 \leq k \leq n}(A[1][k-1] + A[k+1][n]) + \sum\limits_{x=1}^{n}p_{x}\)
\(= MIN_{1 \leq k \leq n}(A[1][k-1] + A[k+1][n]) + 1\)
※ 내용상, \(A[1][0] = A[n+1][n] = 0\) 으로 정의된다.
- OBST를 구축하기 위해, OBST의 AST를 계산하는 과정에서 OBST의 Root 노드의 인덱스를 \(Matrix R\)에 저장한다.
- \(R[i][j]\) = \(Node_{i}\)에서 \(Node_{j}\)까지의 노드로 구성된 OBST의 Root 노드의 인덱스 값이다.
