Optimal Binary Search Trees

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/GKCeN/problem-definition
• https://www.coursera.org/learn/algorithms-greedy/lecture/rUDLu/optimal-substructure
• https://www.coursera.org/learn/algorithms-greedy/lecture/0qjbs/proof-of-optimal-substructure
• https://www.coursera.org/learn/algorithms-greedy/lecture/3wrTN/a-dynamic-programming-algorithm-i
• https://www.coursera.org/learn/algorithms-greedy/lecture/5ERYG/a-dynamic-programming-algorithm-ii

Internal

• Dynamic Programming Algorithms
• Binary Search Trees

Overview

A balanced binary search tree exposes all its nodes via at most log n node traversals. However, if some of the search terms are more accessed than others, and we know a priori the relative access frequency, a balanced search tree might not be optimal. Instead, a tree that keeps the most frequently accessed nodes higher up in the tree offers better performance overall. An optimal search tree minimize the average search time with respect to a given set of probabilities over the keys.