Optimal Binary Search Trees
Explore the construction of optimal binary search trees that minimize total search time by combining recursive backtracking with divide-and-conquer. Understand how to assign tree roots to reduce search costs based on access frequencies, and analyze the exponential time complexity of a backtracking solution before optimizing it using dynamic programming techniques.
We'll cover the following...
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 ...