4. Optimal BSTs

Acknowledgements

Some of this material is borrowed from Jeff Erickson’s chapters on Recursion, Backtracking, and Dynamic Programming. Check them out for a more detailed comparison between recursive and memoized implementations.

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¹ 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.

What are the fragments (AKA, what do we want to store)?

Are the fragments going to be useful (AKA, where is the final answer)?

Do we have a kickstart (AKA, what are the base cases)?

How do the fragments come together (AKA, how do we compute the values that we have agreed to store)?

Can we put the pieces together without getting stuck (AKA, are the dependencies in step #4 acyclic)?

Footnotes

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