Optimal static binary search tree

How do we tailor/construct a binary search tree so that given an access pattern (how frequently certain elements are requested), we construct an optimal tree?

• Intuition is that the more often an element is accessed, the closer it should be placed to the root
• Remember that the depth of an element corresponds to the time it takes to access it in the tree.

Problem

Input: index $1,\dots ,n$ and $p_1,\dots ,p_n\in {\mathbb{R}}_{>0}$ such that $p_i$ is a measure of $i$‘s frequency of appearance.

Output: BST $T$ contains elements $1,\dots ,n$ such that

$$\min \left(\sum _{i=1}^n{p}_i\cdot \text{depth}(i,T)\right)$$

We want to minimize the expected time it takes to access a given element. This is very natural if we assume that $p_1,\dots ,p_n\in [0,1]$ and ${\sum }_{p_i\in P}{p}_i=1$, because then $P$ is just a set of probabilities for each element, and the definition of expected value follows naturally.

In reality $P$, doesn’t need to be constrained within $[0,1]$, But probability is a good intuitive representation of what each $p_i$ could represent.

Solution space: all possible BSTs made up of elements $[\mathrm{1..}n]$ Objective function: given $p_1,\dots ,p_n$ and the tree $T$ that we create, $f$ is given by

$$f(T)=\sum _{i=1}^n{p}_i\cdot \text{depth}(i,T)$$

and we would like to minimize the value of $f$.

High-level question

What should we place at the root? This is a good question because

• There are $[\mathrm{1..}n]$ possible answers
• We can consider $p_1,\dots ,p_n$ in our search to an answer of this question
• Question naturally repeats itself for subproblems, which will be the two children of the node that we eventually pick

Assume that we’ve chosen element $i$ as the root. Then according to the definition of a BST, the left child of $i$ must contain the elements $[\mathrm{1..}i-1]$, while the right child has elements $[i+\mathrm{1..}n]$.

This assumes that $[\mathrm{1..}n]$ are sorted in order.

$G$-function

Then, how do we pick the root $i$?

Given a starting index $i$ and ending index $j$ of the elements we’re considering, where $1\le i,j\le n$ and $j\ge i$, the generalized $G$-function is given by

$$\begin{array}{rl}G(i,j)& =\text{minimum }f\text{-value of BST that stores elements }[i..j]\text{ w.r.t. }{p}_i,\dots ,p_j\\ & =\{\begin{array}{ll}{p}_k& \text{if }i<j\\ {\min }_{k\in [i..j]}\left\{p_k+G(i,k-1)+{\sum }_{l=1}^{k-1}{p}_l+G(k+1,n)+{\sum }_{l=k+1}^n{p}_l\right\}& \text{otherwise, }j\ge i\end{array}\end{array}$$

We need to add ${\sum }_{l=1}^{k-1}{p}_l$ and ${\sum }_{l=k+1}^n{p}_l$ because the left and right subtrees are one level deeper than the root, so when we multiply by $\text{depth}(i,T)$, we add one more copy to account for the extra depth.

We include $p_k$ because we’ve chosen element $k$ as the root, which has a depth of $1$ (technically $0$ but whatever), so the cost it pays is just $p_k\cdot 1$. This makes sense, we’re minimizing depth!

Simplification of function

Notice that adding all the summations together gives us the consecutive range $[i..j]$ (if we also include $p_k$), so it simplifies to

$$G(i,j)=\{\begin{array}{ll}{p}_k& \text{if }i<j\\ {\sum }_{l=i}^j{p}_l+{\min }_{kin[i..j]}\left\{G(i,k-1)+G(k+1,n)\right\}& \text{otherwise, }j\ge i\end{array}$$

We can then pull out the summation because it doesn’t depend on $k$ anymore. This is important for runtime, otherwise we would be looping through $[i..j]$ for every $k$.

Runtime

$i\in [\mathrm{1..}n]$ and $j\in [\mathrm{1..}n]$, so there are $n^2$ subproblems. In addition, we have to try every possible root $k\in [i..j]$. At the top level, when $i=1$ and $j=n$, this takes $n$ time per subproblem, so total runtime is given by $O(n^2)\cdot O(n)=O(n^3)$.