Optimal Binary Search Trees

Introduction to optimal binary search trees

Our final example combines recursive backtracking with the divide-and-conquer strategy. Recall that the running time for a successful search in a binary search tree is proportional to the number of ancestors of the target node. As a result, the worst-case search time is proportional to the depth of the tree. Thus, to minimize the worst-case search time, the height of the tree should be as small as possible; by this metric, the ideal tree is perfectly balanced.

In many applications of binary search trees, however, it is more important to minimize the total cost of several searches rather than the worst-case cost of a single search. If $x$ is a more frequent search target than $y$, we can save time by building a tree where the depth of $x$ is smaller than the depth of $y$, even if that means increasing the overall depth of the tree. A perfectly balanced tree is not the best choice if some items are significantly more popular than others. In fact, a totally unbalanced tree with depth $Ω(n)$ might actually be the best choice!

Problem statement

This situation suggests the following problem. Suppose we are given a sorted array of keys $A[1 .. n]$ and an array of corresponding access frequencies $f [1 .. n]$. Our task is to build the binary search tree that minimizes the total search time, assuming that there will be exactly $f [i]$ searches for each key $A[i]$.

Recurrence relation for optimal search tree

Before we think about how to solve this problem, we should first come up with a good recursive definition of the function we are trying to optimize! Suppose we are also given a binary search tree $T$ with $n$ nodes. Let $v_1, v_2, . . . , v_n$ be the nodes of $T$, indexed in sorted order so that each node $v_i$ stores the corresponding key $A[i]$. Then ignoring constant factors, the total cost of performing all the binary searches is given by the following expression:

$$Cost(T,f[1..n]):= \underset{i=1}{\overset{n}{\sum}}f[i]. \space \text{\#ancestors of}\space v_i\space \text{in T}$$

Now suppose $v_r$ is the root of $T$; by definition, $v_r$ is an ancestor of every node in $T$. If $i < r$, then all ancestors of $v_i$ ...