# 4. Optimal BSTs

algonotes

lecturenotes

### The Problem

- The input is a sorted array A[1, \ldots, n] of search keys and an array f[1, \ldots, n] of frequency counts, where f[i] is the number of times we will search for A[i].
- Our task is to construct a binary search tree for that set such that the total cost of all the searches is as small as possible, where the cost of a search for a key is the the number of anscestors
^{1}that the key has multiplied by its frequency.

This can be thought of as a non-linear version of the file storage problem. Food for thought: will a greedy strategy (insert in descending order of frequencies of access) work?

Heads up: Note that the optimal solution may not be balanced at all.

### The Solution

This section is coming soon.

## Footnotes

The root is the only anscestor of itself, so the cost of access is just one.↩︎