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,…,n$ and $p_{1},…,p_{n}∈R_{>0}$ such that $p_{i}$ is a measure of $i$‘s frequency of appearance.$min(i=1∑n p_{i}⋅depth(i,T))$

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

We want to minimize the *expected* time it takes to access a given element. This is very natural if we assume that $p_{1},…,p_{n}∈[0,1]$ and $∑_{p_{i}∈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 $[1..n]$
**Objective function:** given $p_{1},…,p_{n}$ and the tree $T$ that we create, $f$ is given by

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 $[1..n]$ possible answers
- We can consider $p_{1},…,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 $[1..i−1]$, while the right child has elements $[i+1..n]$.

This assumes that $[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≤i,j≤n$ and $j≥i$, the generalized $G$-function is given by

$G(i,j) =minimumf-value of BST that stores elements[i..j]w.r.t.p_{i},…,p_{j}={p_{k}min_{k∈[i..j]}{p_{k}+G(i,k−1)+∑_{l=1}p_{l}+G(k+1,n)+∑_{l=k+1}p_{l}} ifi<jotherwise,j≥i $We need to add $∑_{l=1}p_{l}$ and $∑_{l=k+1}p_{l}$ because the left and right subtrees are one level deeper than the root, so when we multiply by $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}⋅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)={p_{k}∑_{l=i}p_{l}+min_{kin[i..j]}{G(i,k−1)+G(k+1,n)} ifi<jotherwise,j≥i $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∈[1..n]$ and $j∈[1..n]$, so there are $n_{2}$ subproblems. In addition, we have to try every possible root $k∈[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})⋅O(n)=O(n_{3})$.